كيف تحدد ما إذا كانت النقطة على الجانب الأيمن أو الأيسر من الخط
https://stackoverflow.com/questions/1560492
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي مجموعة من النقاط. أريد فصلها إلى مجموعتين متميزتين. للقيام بذلك ، اخترت نقطتين (أ و ب) ورسم خط وهمي بينهما. الآن أريد أن أحصل على جميع النقاط المتبقية من هذا الخط في مجموعة واحدة وتلك التي هي مباشرة من هذا الخط في المجموعة الأخرى.
كيف يمكنني أن أقول لأي نقطة معينة ض سواء كان ذلك في اليسار أو في المجموعة اليمنى؟ حاولت حساب الزاوية بين AZB - زوايا أصغر من 180 على الجانب الأيمن ، أكبر من 180 على الجانب الأيسر - ولكن بسبب تعريف ARCCOs ، تكون الزوايا المحسوبة أصغر دائمًا من 180 درجة. هل هناك صيغة لحساب زوايا أكبر من 180 درجة (أو أي صيغة أخرى لاختيار الجانب الأيمن أو الأيسر)؟
المحلول
استخدم علامة محدد المتجهات (AB,AM), ، أين M(X,Y) هي نقطة الاستعلام:
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
أنه 0 على الخط ، و +1 على جانب واحد، -1 على الجانب الآخر.
نصائح أخرى
جرب هذا الرمز الذي يستخدم المنتوج الوسيط:
public bool isLeft(Point a, Point b, Point c){
return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0;
}
أين أ = نقطة الخط 1 ؛ ب = نقطة الخط 2 ؛ ج = نقطة للتحقق ضد.
إذا كانت الصيغة تساوي 0 ، فإن النقاط هي colinear.
إذا كان الخط أفقيًا ، فهذا يعود صحيحًا إذا كانت النقطة أعلى من الخط.
تنظر إلى علامة المحدد
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
سيكون إيجابيًا بالنسبة للنقاط من جانب ، وسلبية من جهة أخرى (والصفر للنقاط على الخط نفسه).
المتجه (y1 - y2, x2 - x1) عمودي على الخط ، ويشير دائمًا إلى اليمين (أو يشير دائمًا إلى اليسار ، إذا كان اتجاه الطائرة مختلفًا عني).
يمكنك بعد ذلك حساب منتج DOT لهذا المتجه و (x3 - x1, y3 - y1) لتحديد ما إذا كانت النقطة تكمن على نفس الجانب من خط المتجه العمودي (منتج DOT> 0) أم لا.
لقد قمت بتطبيق هذا في Java وقمت بإجراء اختبار الوحدة (المصدر أدناه). لا شيء من الحلول المذكورة أعلاه يعمل. هذا الرمز يجتاز اختبار الوحدة. إذا وجد أي شخص اختبار وحدة لا يمر ، فيرجى إبلاغي بذلك.
الرمز: ملاحظة: nearlyEqual(double,double) إرجاع صحيح إذا كان الرقمين قريبا جدا.
/*
* @return integer code for which side of the line ab c is on. 1 means
* left turn, -1 means right turn. Returns
* 0 if all three are on a line
*/
public static int findSide(
double ax, double ay,
double bx, double by,
double cx, double cy) {
if (nearlyEqual(bx-ax,0)) { // vertical line
if (cx < bx) {
return by > ay ? 1 : -1;
}
if (cx > bx) {
return by > ay ? -1 : 1;
}
return 0;
}
if (nearlyEqual(by-ay,0)) { // horizontal line
if (cy < by) {
return bx > ax ? -1 : 1;
}
if (cy > by) {
return bx > ax ? 1 : -1;
}
return 0;
}
double slope = (by - ay) / (bx - ax);
double yIntercept = ay - ax * slope;
double cSolution = (slope*cx) + yIntercept;
if (slope != 0) {
if (cy > cSolution) {
return bx > ax ? 1 : -1;
}
if (cy < cSolution) {
return bx > ax ? -1 : 1;
}
return 0;
}
return 0;
}
هذا اختبار الوحدة:
@Test public void testFindSide() {
assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1));
assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14));
assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6));
assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6));
assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1));
assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1));
assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14));
assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1));
assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20));
assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20));
assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10));
assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10));
assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0));
assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0));
assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0));
assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0));
assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0));
assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0));
assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9));
assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9));
assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2));
assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2));
assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0));
assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0));
assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2));
assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2));
assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2));
assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2));
assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0));
assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0));
assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2));
assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0));
assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2));
}
باستخدام معادلة الخط أب, ، احصل على الإحداثيات X على الخط في نفس الإحداثيات Y مثل النقطة التي سيتم فرزها.
- إذا كانت خط Point's X> خط X ، فإن النقطة هي على يمين الخط.
- إذا كانت Point's X <Line's X ، فإن النقطة هي على يسار الخط.
- إذا كانت Point's X == Line's X ، فستكون النقطة على الخط.
تحقق أولا إذا كان لديك خط عمودي:
if (x2-x1) == 0
if x3 < x2
it's on the left
if x3 > x2
it's on the right
else
it's on the line
ثم ، احسب المنحدر: m = (y2-y1)/(x2-x1)
ثم ، قم بإنشاء معادلة للخط باستخدام نموذج منحدر النقطة: y - y1 = m*(x-x1) + y1. من أجل تفسيري ، قم بتبسيطه على نموذج مفهوم المنحدر (ليس ضروريًا في الخوارزمية): y = mx+b.
الآن قم بتوصيل (x3, y3) ل x و y. إليكم بعض الرمز الكاذب الذي يوضح ما يجب أن يحدث:
if m > 0
if y3 > m*x3 + b
it's on the left
else if y3 < m*x3 + b
it's on the right
else
it's on the line
else if m < 0
if y3 < m*x3 + b
it's on the left
if y3 > m*x3+b
it's on the right
else
it's on the line
else
horizontal line; up to you what you do
في الأساس ، أعتقد أن هناك حلًا أسهل بكثير ومباشر للأمام ، لأي مضلع معين ، يتيح أن نقول يتكون من أربع رؤوس (P1 ، P2 ، P3 ، P4) ، ابحث عن الرؤوس المعاكسة الشديدة في المضلع ، في آخر الكلمات ، ابحث على سبيل المثال القمة اليسرى أعلى (دعنا نقول P1) والقمة المعاكسة التي تقع في أسفل اليمين على الأكثر (دعنا نقول). وبالتالي ، بالنظر إلى نقطة الاختبار C (X ، Y) ، عليك الآن إجراء فحص مزدوج بين C و P1 و C و P4:
إذا كان cx> p1x و cy> p1y ==> يعني أن c أقل وإلى يمين p1 التالي إذا كان cx <p2x و cy <p2y ==> يعني أن C أعلى وإلى يسار p4
الخلاصة ، C داخل المستطيل.
شكرًا :)
على افتراض أن النقاط هي (AX ، AY) (bx ، by) و (cx ، cy) ، تحتاج إلى حساب:
(Bx - Ax) * (Cy - AY) - (بواسطة - AY) * (CX - AX)
سيساوي هذا الصفر إذا كانت النقطة C على الخط الذي تم تشكيله بواسطة النقطتين A و B ، وسيكون لها علامة مختلفة حسب الجانب. أي جانب يعتمد هذا على اتجاه إحداثيات (X ، Y) ، ولكن يمكنك توصيل قيم الاختبار لـ A و B و C في هذه الصيغة لتحديد ما إذا كانت القيم السلبية موجودة إلى اليسار أو إلى اليمين.
@AVB إجابة في Ruby
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
لو det إيجابية لها أعلاه ، إذا كانت سلبية أدناه. إذا 0 ، على الخط.
إليك نسخة ، مرة أخرى باستخدام منطق المنتج المتقاطع ، المكتوب في Clojure.
(defn is-left? [line point]
(let [[[x1 y1] [x2 y2]] (sort line)
[x-pt y-pt] point]
(> (* (- x2 x1) (- y-pt y1)) (* (- y2 y1) (- x-pt x1)))))
مثال الاستخدام:
(is-left? [[-3 -1] [3 1]] [0 10])
true
وهذا يعني أن النقطة (0 ، 10) هي على يسار الخط المحدد بواسطة (-3 ، -1) و (3 ، 1).
ملاحظة: يحل هذا التنفيذ مشكلة لا يفعلها أي من الآخرين (حتى الآن)! أمر المسائل عند إعطاء النقاط التي تحدد الخط. أي ، إنه "خط موجه" ، بمعنى ما. لذلك مع الكود أعلاه ، ينتج هذا الاحتجاج أيضًا نتيجة true:
(is-left? [[3 1] [-3 -1]] [0 10])
true
هذا بسبب هذا المقتطف من الكود:
(sort line)
أخيرًا ، كما هو الحال مع الحلول الأخرى القائمة على المنتجات ، فإن هذا الحل يعيد منطقية ، ولا يعطي نتيجة ثالثة للتشكيلات الخطية. لكنه سيعطي نتيجة منطقية ، على سبيل المثال:
(is-left? [[1 1] [3 1]] [10 1])
false
كنت أرغب في توفير حل مستوحى من الفيزياء.
تخيل قوة مطبقة على طول الخط وأنت تقيس عزم دوران القوة حول هذه النقطة. إذا كان عزم الدوران إيجابيًا (عكس اتجاه عقارب الساعة) ، فإن النقطة هي "اليسار" للخط ، ولكن إذا كان عزم الدوران سلبيًا ، فإن النقطة هي "يمين" الخط.
لذلك إذا كان متجه القوة يساوي نطاق النقطتين الذي يحدد الخط
fx = x_2 - x_1
fy = y_2 - y_1
تقوم باختبار جانب النقطة (px,py) بناءً على علامة الاختبار التالي
var torque = fx*(py-y_1)-fy*(px-x_1)
if torque>0 then
"point on left side"
else if torque <0 then
"point on right side"
else
"point on line"
end if
تتمثل طريقة بديلة للحصول على إحساس بالحلول التي توفرها Netters في فهم بعض الآثار الهندسية.
يترك PQR= [P ، Q ، R] هي نقاط تشكل طائرة مقسمة إلى جانبين على الخط P ، R. يجب أن نكتشف ما إذا كانت نقطتين PQR الطائرة ، أ ، ب ، على نفس الجانب.
أي نقطة ر على طائرة PQR يمكن تمثيلها مع 2 متجهات: الخامس = PQ و ش = RQ ، كما:
t '= tq = أنا * V + ي * ش
الآن تداعيات الهندسة:
- i+j = 1: t على خط العلاقات العامة
- i+j <1: t على sq
- i+j> 1: t على SNQ
- i+j = 0: t = q
- i+j <0: t على sq وما بعده Q.
i+j: <0 0 <1 =1 >1
---------Q------[PR]--------- <== this is PQR plane
^
pr line
على العموم،
- I+J هو مقياس لمدى الابتعاد عن Q أو الخط [P ، R, ، و
- علامة أنا+J-1 يورط ثنائية تي.
أهمية الهندسة الأخرى أنا و ي (غير مرتبط بهذا الحل) هي:
- أنا,ي هي العدادات لـ T في نظام إحداثيات جديد حيث الخامس ، ش هي المحاور الجديدة و س هو الأصل الجديد.
- أنا, ي يمكن أن ينظر إليها على أنها قوة السحب ل ص ، ص, ، على التوالى. الأكبر أنا, ، أبعد t بعيدا عن ص (سحب أكبر من ص).
قيمة ال اي جاي يمكن الحصول عليها عن طريق حل المعادلات:
i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z
لذلك حصلنا على نقطتين ، أ ، ب على متن الطائرة:
A = a1 * v + a2 * u
B = b1 * v + b2 * u
إذا كانت A ، B على نفس الجانب ، فسيكون هذا صحيحًا:
sign(a1+a2-1) = sign(b1+b2-1)
لاحظ أن هذا ينطبق أيضًا على السؤال: هي A ، B في نفس الجانب من الطائرة [P ، Q ، R, ، بحيث:
t = أنا * P + ي * س + ك * ص
و i+j+k = 1 يعني أن T على متن الطائرة [P ، Q ، R] وعلامة i+j+k-1 ينطوي على جانبه. من هذا: لدينا:
A = a1 * P + a2 * Q + a3 * R
B = b1 * P + b2 * Q + b3 * R
و A ، B على نفس الجانب من الطائرة [P ، Q ، R] إذا
sign(a1+a2+a3-1) = sign(b1+b2+b3-1)
