كيف يمكنني تحديد ما إذا كانت 2D نقطة داخل المضلع?
https://stackoverflow.com/questions/217578
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحاول خلق سريع 2D نقطة داخل المضلع الخوارزمية ، للاستخدام في ضرب الاختبار (مثلا ، Polygon.contains(p:Point)).اقتراحات تقنيات فعالة سيكون موضع تقدير.
المحلول
بالنسبة للرسومات أنا بالأحرى لا تفضل الاعداد الصحيحه.العديد من أنظمة استخدام الاعداد الصحيحه واجهة المستخدم اللوحة (بكسل رجات بعد كل شيء) ، ولكن ماك على سبيل المثال يستخدم تطفو على كل شيء.ماك فقط يعرف نقطة و نقطة يمكن أن تترجم إلى بكسل واحد, ولكن اعتمادا على رصد القرار ، فإنه قد تترجم إلى شيء آخر.على شاشات شبكية العين نصف نقطة (0.5/0.5) هو بكسل.لا يزال, لم ألحظ هذا ماك معهد اليونسكو للإحصاء هي أبطأ بكثير من غيرها من معهد اليونسكو للإحصاء.بعد كل شيء 3D واجهات برمجة التطبيقات (OpenGL أو Direct3D) يعمل أيضا مع المجسمات والرسومات الحديثة المكتبات في كثير من الأحيان الاستفادة من تسريع GPU.
الآن قلت السرعة هو الشاغل الرئيسي الخاص بك, حسنا, دعنا نذهب بسرعة.قبل تشغيل أي الخوارزمية المعقدة أول إجراء اختبار بسيط.إنشاء المحور الانحياز المربع المحيط حول المضلع.هذا من السهل جدا وسريعة يمكن بالفعل آمنة لك الكثير من العمليات الحسابية.كيف يعمل هذا ؟ تكرار عبر كل نقاط المضلع و العثور على مين/ماكس قيم X و Y.
E. g.لديك نقطة (9/1), (4/3), (2/7), (8/2), (3/6).وهذا يعني Xmin هو 2 ، Xmax هي 9 ، Ymin هو 1 و Ymax هو 7.نقطة خارج مستطيل مع حواف اثنين (2/1) و (9/7) لا يمكن أن يكون داخل المضلع.
// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
// Definitely not within the polygon!
}
هذا هو الاختبار الأول لتشغيل على أي نقطة.كما ترون, هذا الاختبار بسرعة فائقة لكنه أيضا الخشن جدا.التعامل مع النقاط التي هي داخل مستطيل إحاطة ، نحن بحاجة إلى المزيد من خوارزميات متطورة.وهناك زوجين من الطرق كيف يمكن أن تكون محسوبة.الطريقة التي يعمل أيضا يعتمد على حقيقة إذا كان المضلع يمكن أن يكون ثقوب أو سوف دائما تكون صلبة.وإليك أمثلة من تلك الصلبة (محدبة واحد ، واحد مقعر):
وهنا واحد مع وجود ثقب:
الأخضر واحد له حفرة في الوسط!
أسهل الخوارزمية التي يمكن التعامل مع جميع الحالات الثلاث أعلاه و هو لا يزال سريع جدا هو اسمه راي الصب.فكرة الخوارزمية بسيطة جدا:رسم الظاهري راي من أي مكان خارج المضلع إلى نقطة تحسب كيف غالبا ما يضرب جانب المضلع.إذا كان عدد الزيارات حتى إنه خارج المضلع ، إذا كان الغريب انه في الداخل.
على لف عدد الخوارزمية سيكون بديل ، هو أكثر دقة للحصول على نقاط كونها قريبة جدا من المضلع الخط لكنه أيضا أبطأ بكثير.راي الصب قد تفشل للحصول على نقاط قريبة جدا مضلع الجانب بسبب محدودية النقطة العائمة الدقة و التقريب القضايا ، ولكن في الواقع هذه ليست مشكلة ، كما لو كان نقطة تقع قريبة من الجانب ، فإنه غالبا ما يكون بصريا حتى يمكن للمشاهد أن يتعرف إذا كان بالفعل داخل أو لا يزال خارج.
لا يزال لديك إحاطة المربع أعلاه ، أتذكر ؟ مجرد اختيار نقطة خارج المربع المحيط واستخدامه بمثابة نقطة انطلاق الخاصة بك راي.E. g.نقطة (Xmin - e/p.y) هو خارج المضلع بالتأكيد.
ولكن ما هو e?حسنا ، e (في الواقع ابسيلون) يعطي المربع المحيط بعض الحشو.كما قلت راي اقتفاء الأثر فشل إذا بدأنا قريبة جدا المضلع خط.منذ المربع المحيط قد قدم المساواة المضلع (إذا كان المضلع هو محور الانحياز المستطيل ، المربع المحيط يساوي المضلع نفسها!), نحن بحاجة الى بعض الحشو لجعل هذه آمنة, هذا كل شيء.كيف كبيرة يجب عليك أن تختار e?ليست كبيرة جدا.ذلك يعتمد على نظام الإحداثيات نطاق استخدام الرسم.إذا كان الخاص بك بكسل عرض الخطوة هو 1.0, ثم مجرد اختيار 1.0 (بعد 0.1 قد عملت كذلك)
الآن أن لدينا راي مع بداية ونهاية الإحداثيات المشكلة التحولات من "هو نقطة داخل المضلع"إلى "كيف في كثير من الأحيان لا راي يتقاطع مضلع الجانب".ولذلك لا يمكننا العمل مع نقاط المضلع كما كان من قبل, الآن نحن بحاجة الفعلية الجانبين.الجانب دائما على تحديد نقاط.
side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:
تحتاج إلى اختبار راي ضد جميع الأطراف.النظر في راي أن يكون ناقل كل جانب إلى أن ناقلات.راي قد ضرب كل جانب بالضبط مرة واحدة أو لا على الإطلاق.لا يمكن أن تصل إلى نفس الجانب مرتين.خطين في 2D الفضاء سوف تتقاطع دائما بالضبط مرة واحدة ، ما لم يتم بالتوازي مع ذلك ، وفي هذه الحالة لا تتقاطع أبدا.ومع ذلك منذ ناقلات محدودة الطول ، المتجهان قد لا تكون متوازية لا تتقاطع لأنها قصيرة جدا من أي وقت مضى للقاء بعضهم البعض.
// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
// Test if current side intersects with ray.
// If yes, intersections++;
}
if ((intersections & 1) == 1) {
// Inside of polygon
} else {
// Outside of polygon
}
حتى الآن جيد جدا, ولكن كيف يمكنك اختبار ما إذا كان المتجهان التداخل ؟ هنا بعض التعليمات البرمجية C (لم تختبر), التي ينبغي أن تفعل خدعة:
#define NO 0
#define YES 1
#define COLLINEAR 2
int areIntersecting(
float v1x1, float v1y1, float v1x2, float v1y2,
float v2x1, float v2y1, float v2x2, float v2y2
) {
float d1, d2;
float a1, a2, b1, b2, c1, c2;
// Convert vector 1 to a line (line 1) of infinite length.
// We want the line in linear equation standard form: A*x + B*y + C = 0
// See: http://en.wikipedia.org/wiki/Linear_equation
a1 = v1y2 - v1y1;
b1 = v1x1 - v1x2;
c1 = (v1x2 * v1y1) - (v1x1 * v1y2);
// Every point (x,y), that solves the equation above, is on the line,
// every point that does not solve it, is not. The equation will have a
// positive result if it is on one side of the line and a negative one
// if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
// 2 into the equation above.
d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
d2 = (a1 * v2x2) + (b1 * v2y2) + c1;
// If d1 and d2 both have the same sign, they are both on the same side
// of our line 1 and in that case no intersection is possible. Careful,
// 0 is a special case, that's why we don't test ">=" and "<=",
// but "<" and ">".
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// The fact that vector 2 intersected the infinite line 1 above doesn't
// mean it also intersects the vector 1. Vector 1 is only a subset of that
// infinite line 1, so it may have intersected that line before the vector
// started or after it ended. To know for sure, we have to repeat the
// the same test the other way round. We start by calculating the
// infinite line 2 in linear equation standard form.
a2 = v2y2 - v2y1;
b2 = v2x1 - v2x2;
c2 = (v2x2 * v2y1) - (v2x1 * v2y2);
// Calculate d1 and d2 again, this time using points of vector 1.
d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
d2 = (a2 * v1x2) + (b2 * v1y2) + c2;
// Again, if both have the same sign (and neither one is 0),
// no intersection is possible.
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// If we get here, only two possibilities are left. Either the two
// vectors intersect in exactly one point or they are collinear, which
// means they intersect in any number of points from zero to infinite.
if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;
// If they are not collinear, they must intersect in exactly one point.
return YES;
}
قيم الإدخال هي النهاية اثنين من ناقلات 1 (v1x1/v1y1 و v1x2/v1y2) و ناقلات 2 (v2x1/v2y1 و v2x2/v2y2).بحيث يكون لديك 2 ناقلات ، 4 نقطة ، 8 الإحداثيات. YES و NO واضحة. YES يزيد من التقاطعات ، NO لا يفعل شيئا.
ماذا عن خط واحد?يعني كل ناقلات تقع على نفس خط لانهائي ، اعتمادا على طول, لا تتقاطع في كل أو أنها تتقاطع في عدد لا نهاية له من النقاط.أنا لست متأكدة من كيفية التعامل مع هذه الحالة لا تحسب أنها تقاطع في كلتا الحالتين.حسنا, هذه الحالة نادر في الممارسة العملية على أي حال بسبب النقطة العائمة التقريب الأخطاء ؛ أفضل رمز ربما ليس اختبار == 0.0f ولكن بدلا من ذلك على شيء مثل < epsilon, حيث ابسيلون هو بدلا من ذلك عدد قليل.
إذا كنت بحاجة لاختبار أكبر عدد من النقاط, يمكنك بالتأكيد تسريع كل شيء قليلا عن طريق الحفاظ على معادلة خطية النماذج القياسية المضلع الجانبين في الذاكرة ، لذلك لم يكن لديك إلى إعادة حساب هذه في كل مرة.هذا سيوفر لك اثنين الضرب النقطة العائمة و ثلاثة النقطة العائمة الطرح على كل اختبار في مقابل تخزين ثلاث قيم النقطة العائمة في المضلع الجانب في الذاكرة.انها نموذجية الذاكرة مقابل حساب الوقت مقايضة.
وأخيرا وليس آخرا:إذا كنت قد تستخدم الأجهزة 3D لحل هذه المشكلة ، هناك بديل للاهتمام.فقط اسمحوا GPU تفعل كل عمل لك.إنشاء سطح اللوحة الذي هو خارج الشاشة.ملء تماما مع اللون الأسود.الآن دعونا OpenGL أو Direct3D الطلاء الخاص بك المضلع (أو حتى كل من المضلعات إذا كنت ترغب فقط لاختبار إذا كان الموضوع في أي منها ، ولكن كنت لا تهتم لأي واحد) وملء المضلع(s) مع لون مختلف ، مثلالأبيض.للتحقق مما إذا نقطة داخل المضلع ، والحصول على لون من هذه النقطة من سطح الرسم.هذا هو مجرد O(1) الذاكرة الجلب.
بالطبع هذه الطريقة يمكن استخدامها فقط إذا كان سطح الرسم لا يجب أن تكون ضخمة.إذا كان لا يمكن أن تنسجم مع GPU الذاكرة ، هذا الأسلوب هو أبطأ من القيام بذلك على وحدة المعالجة المركزية.إذا كان يجب أن تكون ضخمة و الجرافيك الخاص بك يدعم الحديثة تظليل ، لا يزال بإمكانك استخدام GPU من خلال تنفيذ راي الصب كما هو مبين أعلاه GPU تظليل التي الاطلاق هو ممكن.أكبر عدد المضلعات أو عدد كبير من النقاط إلى اختبار هذا سيؤتي ثماره ، النظر في بعض وحدات معالجة الرسومات سوف تكون قادرة على اختبار 64 إلى 256 نقطة في نفس الوقت.ومع ذلك لاحظ أن نقل البيانات من وحدة المعالجة المركزية إلى GPU و العودة دائما مكلفة ، وذلك من أجل اختبار فقط بضع نقاط ضد بضعة بسيطة المضلعات ، حيث إما نقطة أو المضلعات هي ديناميكية تتغير كثيرا ، GPU النهج نادرا ما دفع قبالة.
نصائح أخرى
أعتقد أن الجزء التالي من التعليمات البرمجية هو أفضل حل (مأخوذة من هنا):
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
الحجج
- nvert:عدد من القمم في المضلع.إذا كان لتكرار أول قمة في النهاية تم مناقشتها في المقالة المشار إليها أعلاه.
- vertx, verty:المصفوفات التي تحتوي على x و y إحداثيات المضلع في القمم.
- testx, نكد:X و y إحداثيات نقطة الاختبار.
انها على حد سواء قصيرة وفعالة تعمل على حد سواء محدبة و مقعرة المضلعات.كما اقترح من قبل, يجب أن تحقق مستطيل إحاطة الأولى وعلاج المضلع الثقوب بشكل منفصل.
الفكرة من وراء هذا هو بسيط جدا.يصف المؤلف على النحو التالي:
تشغيل شبه لانهائية راي أفقيا (زيادة x ثابت y) من نقطة الاختبار ، و عد كم حواف يعبر.في كل عبور شعاع التبديل بين الداخل والخارج.وهذا ما يسمى في الاردن منحني نظرية.
المتغير c هو التحول من 0 إلى 1 و 1 إلى 0 في كل مرة الأفقي راي يعبر أي الحافة.ذلك أساسا هو تتبع ما إذا كان عدد من حواف عبرت هي الفردية أو الزوجية.0 يعني حتى و 1 يعني الغريب.
وهنا هو C # نسخة من الإجابة التي قدمها nirg، والتي تأتي من <لأ href = "HTTP: / /www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html "يختلط =" noreferrer "> هذا RPI أستاذ . لاحظ أن استخدام رمز من هذا المصدر RPI يتطلب الإسناد.
وتمت إضافة خانة الاختيار المحيط في الأعلى. ومع ذلك، كما يشير جيمس براون خارج، رمز الرئيسي هو تقريبا بأسرع ما تحقق من المربع المحيط نفسه، وبالتالي فإن الاختيار المربع المحيط يمكن أن يبطئ في الواقع مجمل العملية، في حالة أن معظم النقاط التي يتم التحقق هي داخل المربع المحيط . لذلك يمكن أن يترك المربع المحيط تحقق من، أو أن يكون بديلا لprecompute مربعات إحاطة من المضلعات إذا كانوا لا تغيير شكل كثير من الأحيان.
public bool IsPointInPolygon( Point p, Point[] polygon )
{
double minX = polygon[ 0 ].X;
double maxX = polygon[ 0 ].X;
double minY = polygon[ 0 ].Y;
double maxY = polygon[ 0 ].Y;
for ( int i = 1 ; i < polygon.Length ; i++ )
{
Point q = polygon[ i ];
minX = Math.Min( q.X, minX );
maxX = Math.Max( q.X, maxX );
minY = Math.Min( q.Y, minY );
maxY = Math.Max( q.Y, maxY );
}
if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
{
return false;
}
// http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
bool inside = false;
for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
{
if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
{
inside = !inside;
}
}
return inside;
}
وهنا هو البديل جافا سكريبت من الإجابة من طرف M. كاتز على أساس نهج Nirg ل:
function pointIsInPoly(p, polygon) {
var isInside = false;
var minX = polygon[0].x, maxX = polygon[0].x;
var minY = polygon[0].y, maxY = polygon[0].y;
for (var n = 1; n < polygon.length; n++) {
var q = polygon[n];
minX = Math.min(q.x, minX);
maxX = Math.max(q.x, maxX);
minY = Math.min(q.y, minY);
maxY = Math.max(q.y, maxY);
}
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
return false;
}
var i = 0, j = polygon.length - 1;
for (i, j; i < polygon.length; j = i++) {
if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
isInside = !isInside;
}
}
return isInside;
}
وحساب مجموع الموجهة من الزوايا بين ع نقطة وكل من قمم المضلع. إذا كانت الزاوية الموجهة الإجمالية 360 درجة، وهذه النقطة هي في الداخل. إذا كان مجموع 0، وهذه النقطة هي خارج.
وأنا أحب هذه الطريقة أفضل لأنه أكثر قوة وأقل اعتمادا على الدقة العددية.
والطرق التي حساب التوزيع المتساوي للعدد من التقاطعات تقتصر أنه يمكنك 'ضرب' لقمة خلال حساب عدد من التقاطعات.
وتحرير: وبالمناسبة، يعمل هذا الأسلوب مع المضلعات المقعرة والمحدبة
.تحرير: لقد وجدت مؤخرا ويكيبيديا المقالة حول هذا الموضوع
.اريك هاينز المقالة التي استشهد بها bobobobo ممتاز حقا. مثيرة للاهتمام بشكل خاص هي الجداول المقارنة بين أداء الخوارزميات. طريقة زاوية الجمع سيئة حقا مقارنة بالآخرين. المثير للاهتمام أيضا هو أن تحقيق أمثلية مثل استخدام شبكة البحث لزيادة تقسيم المضلع إلى "في" والقطاعات "خارج" يمكن أن تجعل من اختبار سريع بشكل لا يصدق حتى على المضلعات مع> 1000 الجانبين.
وعلى أي حال، فإنه من الأيام الأولى ولكن تصويتي يذهب إلى أسلوب "المعابر"، وهو تقريبا ما يصف Mecki على ما أعتقد. ومع ذلك وجدت أنه أكثر succintly وصف ومقننة من قبل ديفيد بورك . أنا أحب أن ليس هناك علم المثلثات الحقيقي المطلوب، وكان يعمل لمحدب ومقعر، وينفذ بشكل معقول كما يزيد عدد الجانبين.
وبالمناسبة، وهنا واحدة من جداول الأداء من المقالة اريك هاينز "للاهتمام، واختبار على المضلعات عشوائية.
number of edges per polygon
3 4 10 100 1000
MacMartin 2.9 3.2 5.9 50.6 485
Crossings 3.1 3.4 6.8 60.0 624
Triangle Fan+edge sort 1.1 1.8 6.5 77.6 787
Triangle Fan 1.2 2.1 7.3 85.4 865
Barycentric 2.1 3.8 13.8 160.7 1665
Angle Summation 56.2 70.4 153.6 1403.8 14693
Grid (100x100) 1.5 1.5 1.6 2.1 9.8
Grid (20x20) 1.7 1.7 1.9 5.7 42.2
Bins (100) 1.8 1.9 2.7 15.1 117
Bins (20) 2.1 2.2 3.7 26.3 278
وهذا السؤال هو للاهتمام. لدي فكرة قابلة للتطبيق آخر يختلف عن إجابات أخرى من هذا المنصب.
والفكرة هي استخدام مجموع الزوايا لتقرر ما إذا كان الهدف هو داخل أو خارج. إذا كان الهدف هو داخل المنطقة، فإن مجموع شكل زاوية بواسطة هدف وكل نقطتين الحدود سيكون 360. إذا كان الهدف هو خارج، فإن المبلغ لن تكون 360. زاوية ديها الاتجاه. إذا كانت الزاوية الذهاب الى الوراء، وزاوية واحدة سلبية. هذا هو تماما مثل حساب لف عدد .
والرجوع إلى هذه الصورة للحصول على فهم أساسي للفكرة:
وبلدي خوارزمية تفترض في اتجاه عقارب الساعة هو اتجاه إيجابي. هنا هو إدخال المحتملين:
[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]
وفيما يلي هو رمز الثعبان التي تطبق فكرة:
def isInside(self, border, target):
degree = 0
for i in range(len(border) - 1):
a = border[i]
b = border[i + 1]
# calculate distance of vector
A = getDistance(a[0], a[1], b[0], b[1]);
B = getDistance(target[0], target[1], a[0], a[1])
C = getDistance(target[0], target[1], b[0], b[1])
# calculate direction of vector
ta_x = a[0] - target[0]
ta_y = a[1] - target[1]
tb_x = b[0] - target[0]
tb_y = b[1] - target[1]
cross = tb_y * ta_x - tb_x * ta_y
clockwise = cross < 0
# calculate sum of angles
if(clockwise):
degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
else:
degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
if(abs(round(degree) - 360) <= 3):
return True
return False
ونسخة سويفت من الإجابة التي كتبها nirg :
extension CGPoint {
func isInsidePolygon(vertices: [CGPoint]) -> Bool {
guard !vertices.isEmpty else { return false }
var j = vertices.last!, c = false
for i in vertices {
let a = (i.y > y) != (j.y > y)
let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x)
if a && b { c = !c }
j = i
}
return c
}
}
وفعلت بعض العمل على هذا مرة عندما كنت باحثا تحت ميتشايل ستونبراكر - أنت تعرف، الأستاذ الذي جاء مع إينغرس و <لأ href = "HTTP : //en.wikipedia.org/wiki/PostgreSQL "يختلط =" نوفولو noreferrer "> كيو ، الخ
.ولقد أدركنا أن أسرع وسيلة كانت أن نقوم به أولا مربع إحاطة لأنه سريع سوبر. لو كان خارج المربع المحيط، انها خارج. خلاف ذلك، يمكنك القيام بعمل أصعب ...
إذا كنت ترغب في خوارزمية كبيرة، ونتطلع إلى مشروع مفتوح المصدر كيو الكود لعمل الجغرافية ...
وأنا أريد أن أشير إلى أننا لم يحصل أي نظرة ثاقبة الحق ضد الطغيان الأيسر (التعبير عنه أيضا باسم "الداخلية" مقابل مشكلة "الخارجية" ...
وUPDATE
وقدمت وصلة BKB عددا لا بأس به من خوارزميات معقولة. كنت أعمل على مشاكل علوم الأرض، وبالتالي هناك حاجة إلى الحل الذي يعمل في خطوط العرض / الطول، ولها مشكلة غريبة من الطغيان - هي منطقة داخل منطقة صغيرة أو مساحة أكبر؟ والجواب هو أن "الاتجاه" من الأمور verticies - انها إما أعسر أو الحق الوفاض، وبهذه الطريقة يمكنك أن تشير إلى أي منطقة بأنها "داخل" أي مضلع معين. على هذا النحو، عملي يستخدم حل ثلاث تعداد في تلك الصفحة.
وبالإضافة إلى ذلك، تستخدم عملي وظائف منفصلة ل "على الخط" الاختبارات.
... منذ سأل أحدهم: نحن أحسب أن إحاطة اختبارات مربع كانت أفضل عندما ارتفع عدد verticies وراء بعض رقم - القيام اختبار سريع جدا قبل القيام اختبار أطول إذا لزم الأمر ... يتم إنشاء المربع المحيط من قبل مجرد اتخاذ أكبر س، x أصغر، أكبر y و أصغر ذ ووضعها معا لجعل أربع نقاط من مربع ...
وآخر نصيحة لتلك التي تتبع: نحن لم كلنا أكثر تطورا و "ضوء يعتم" الحوسبة في مساحة الشبكة في كل نقطة إيجابية على متن طائرة ثم إعادة المتوقعة ظهر في "الحقيقي" خط الطول / العرض، وبالتالي تجنب الأخطاء المحتملة للالتفاف حول عندما عبرت خط واحد 180 من خطوط الطول وعند التعامل مع المناطق القطبية. عمل عظيم!
وحقا وكأنه الحل المرسلة بواسطة Nirg وتحريرها من قبل bobobobo. أنا فقط جعلت من جافا سكريبت ودية وأكثر من ذلك بقليل مقروءة للاستخدام الخاص بي:
function insidePoly(poly, pointx, pointy) {
var i, j;
var inside = false;
for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;
}
return inside;
}
والجواب ديفيد Segond هي الى حد كبير إجابة عامة القياسية، وريتشارد T هو الأمثل الأكثر شيوعا، على الرغم من therre بعض الآخرين. وتستند تحسينات قوية أخرى على حلول أقل العامة. على سبيل المثال إذا كنت تسير على تحقق نفس المضلع مع الكثير من النقاط، تثليث المضلع يمكن تسريع الامور بشكل كبير كما أن هناك عددا من خوارزميات سريعة جدا تين البحث. آخر هو إذا كان المضلع ونقاط هم على متن طائرة محدودة في دقة منخفضة، أقول شاشة عرض، يمكنك رسم مضلع على تعيين الذاكرة عازلة العرض في لون معين، والتحقق من لون بكسل نظرا لمعرفة ما اذا كان يكذب في المضلعات.
وعلى غرار العديد من التحسينات، وتعتمد هذه على معينة بدلا من القضايا العامة، وbeneifits العائد على أساس الوقت المطفأة بدلا من استخدام واحد.
العمل في هذا المجال، وجدت Joeseph O'Rourkes "الحساب الهندسة في C" ISBN 0-521-44034-3 أن يكون عونا كبيرا.
تافهة حل هو تقسيم المضلع إلى مثلثات و ضرب اختبار مثلثات كما هو موضح هنا
إذا كان المضلع محدب قد يكون هناك طريقة أفضل على الرغم من.انظر المضلع مجموعة لانهائية خطوط.كل خط تقسيم المساحة إلى قسمين.كل نقطة فإنه من السهل أن أقول إذا كان على جانب واحد أو الجانب الآخر من الخط.إذا كانت النقطة على الجانب نفسه من جميع الخطوط ثم هو داخل المضلع.
وأنا أدرك هذا هو القديم، ولكن هنا هو خوارزمية راي صب تنفيذها في الكاكاو، في حالة أي شخص مهتم. غير متأكد من أنه هو أنجع وسيلة لفعل الأشياء، لكنها قد تساعد شخص ما.
- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
BOOL result;
float aggregateX = 0; //I use these to calculate the centroid of the shape
float aggregateY = 0;
NSPoint firstPoint[1];
[currentPath elementAtIndex:0 associatedPoints:firstPoint];
float olderX = firstPoint[0].x;
float olderY = firstPoint[0].y;
NSPoint interPoint;
int noOfIntersections = 0;
for (int n = 0; n < [currentPath elementCount]; n++) {
NSPoint points[1];
[currentPath elementAtIndex:n associatedPoints:points];
aggregateX += points[0].x;
aggregateY += points[0].y;
}
for (int n = 0; n < [currentPath elementCount]; n++) {
NSPoint points[1];
[currentPath elementAtIndex:n associatedPoints:points];
//line equations in Ax + By = C form
float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;
float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);
float _A_BAR = olderY - points[0].y;
float _B_BAR = points[0].x - olderX;
float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);
float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
if (det != 0) {
//intersection points with the edges
float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
if (olderX <= points[0].x) {
//doesn't matter in which direction the ray goes, so I send it right-ward.
if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {
noOfIntersections++;
}
} else {
if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
noOfIntersections++;
}
}
}
olderX = points[0].x;
olderY = points[0].y;
}
if (noOfIntersections % 2 == 0) {
result = FALSE;
} else {
result = TRUE;
}
return result;
}
والكائنات C نسخة من الجواب nirg مع أسلوب العينة للحصول على نقاط الاختبار. الجواب Nirg وعملت بشكل جيد بالنسبة لي.
- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test {
NSUInteger nvert = [vertices count];
NSInteger i, j, c = 0;
CGPoint verti, vertj;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue];
vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue];
if (( (verti.y > test.y) != (vertj.y > test.y) ) &&
( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) )
c = !c;
}
return (c ? YES : NO);
}
- (void)testPoint {
NSArray *polygonVertices = [NSArray arrayWithObjects:
[NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)],
[NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)],
[NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)],
[NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)],
[NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)],
[NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)],
nil
];
CGPoint tappedPoint = CGPointMake(23.0, 70.0);
if ([self isPointInPolygon:polygonVertices point:tappedPoint]) {
NSLog(@"YES");
} else {
NSLog(@"NO");
}
}
وC # نسخة من الجواب nirg هو هنا: سوف أشارك فقط رمز. قد إنقاذ شخص بعض الوقت.
public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) {
bool result = false;
int j = polygon.Count() - 1;
for (int i = 0; i < polygon.Count(); i++) {
if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) {
if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) {
result = !result;
}
}
j = i;
}
return result;
}
وليس هناك شيء أكثر beutiful من تعريف حثي على وجود مشكلة. من أجل اكتمال هنا لديك إصدار في برولوج التي قد أيضا توضيح thoughs وراء <م> راي صب :
واستنادا إلى محاكاة الخوارزمية البساطة في HTTP: // www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
وبعض المسندات المساعد:
exor(A,B):- \+A,B;A,\+B.
in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).
inside(false).
inside(_,[_|[]]).
inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) + X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).
get_line(_,_,[]).
get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).
ومعادلة خط معين 2 نقطة A و B (الخط (A، B)) هو:
(YB-YA)
Y - YA = ------- * (X - XA)
(XB-YB)
ومن المهم أن اتجاه دوران الخط ستيد إلى الساعة الحكيم للحدود ومعاداة مدار الساعة الحكيمة لالثقوب. نحن نذهب للتحقق ما إذا كانت النقطة (X، Y)، أي بمعنى نقطة اختبار هو في اليسار نصف طائرة من خطنا (هو مسألة ذوق، فإنه يمكن أيضا أن يكون الجانب الأيمن، ولكن ايضا في اتجاه خطوط الحدود يجب أن يتغير في هذه الحالة)، وهذا هو المشروع شعاع من نقطة إلى اليمين (أو اليسار) ونعترف تقاطع مع الخط. لقد اخترنا لمشروع شعاع في الاتجاه الأفقي (مرة أخرى هو مسألة ذوق، فإنه يمكن أيضا أن يتم في رأسي مع قيود مماثلة)، لذلك لدينا:
(XB-XA)
X < ------- * (Y - YA) + XA
(YB-YA)
والآن نحن بحاجة إلى معرفة ما إذا كانت النقطة هي في اليسار (أو اليمين) من القطعة المستقيمة فقط، وليس طائرة بأكملها، لذلك نحن بحاجة إلى تقييد البحث فقط في هذا الجزء، ولكن هذا أمر سهل منذ أن يكون داخل قطاع نقطة واحدة فقط في خط يمكن أن يكون أعلى من Y في المحور الرأسي. لأن هذا هو تقييد أقوى عليه يجب أن يكون أولا للتحقق، لذلك نحن نأخذ أولا فقط تلك الخطوط تلبية هذا الشرط ومن ثم تحقق possition لها. من الأردن منحنى نظرية أي راي المتوقع أن المضلع يجب أن تتقاطع في ل حتى عدد من الخطوط. لذلك نحن القيام به، ونحن سوف رمي راي ل اليمين ومن ثم في كل مرة أنه يتقاطع خط، تبديل حالته. ومع ذلك تنفيذا لدينا ونحن goint للتحقق من الأدني ل حقيبة من الحلول تلبية قيود معينة، وتقرر innership عليه. لكل خط في المضلع هذا يتعين القيام به.
is_left_half_plane(_,[],[],_).
is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] = [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA));
is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).
in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon), in_range(Y,YA,YB).
all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line), in_y_range_at_poly(Coordinate,Line,Polygon), Lines).
traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).
% This is the entry point predicate
inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).
وجافا الإصدار:
public class Geocode {
private float latitude;
private float longitude;
public Geocode() {
}
public Geocode(float latitude, float longitude) {
this.latitude = latitude;
this.longitude = longitude;
}
public float getLatitude() {
return latitude;
}
public void setLatitude(float latitude) {
this.latitude = latitude;
}
public float getLongitude() {
return longitude;
}
public void setLongitude(float longitude) {
this.longitude = longitude;
}
}
public class GeoPolygon {
private ArrayList<Geocode> points;
public GeoPolygon() {
this.points = new ArrayList<Geocode>();
}
public GeoPolygon(ArrayList<Geocode> points) {
this.points = points;
}
public GeoPolygon add(Geocode geo) {
points.add(geo);
return this;
}
public boolean inside(Geocode geo) {
int i, j;
boolean c = false;
for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
(geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
c = !c;
}
return c;
}
}
وميناء صافي:
static void Main(string[] args)
{
Console.Write("Hola");
List<double> vertx = new List<double>();
List<double> verty = new List<double>();
int i, j, c = 0;
vertx.Add(1);
vertx.Add(2);
vertx.Add(1);
vertx.Add(4);
vertx.Add(4);
vertx.Add(1);
verty.Add(1);
verty.Add(2);
verty.Add(4);
verty.Add(4);
verty.Add(1);
verty.Add(1);
int nvert = 6; //Vértices del poligono
double testx = 2;
double testy = 5;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((verty[i] > testy) != (verty[j] > testy)) &&
(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
c = 1;
}
}
VBA الإصدار:
ملاحظة:تذكر أنه إذا كان المضلع هو مساحة في خريطة خط العرض/خط الطول هي Y/X القيم بدلا من X/Y (خط العرض = Y, خط الطول = X) بسبب ما فهمت التاريخية المترتبة من طريق العودة عندما الطول لم يكن قياس.
فئة الوحدة النمطية:CPoint
Private pXValue As Double
Private pYValue As Double
'''''X Value Property'''''
Public Property Get X() As Double
X = pXValue
End Property
Public Property Let X(Value As Double)
pXValue = Value
End Property
'''''Y Value Property'''''
Public Property Get Y() As Double
Y = pYValue
End Property
Public Property Let Y(Value As Double)
pYValue = Value
End Property
الوحدة النمطية:
Public Function isPointInPolygon(p As CPoint, polygon() As CPoint) As Boolean
Dim i As Integer
Dim j As Integer
Dim q As Object
Dim minX As Double
Dim maxX As Double
Dim minY As Double
Dim maxY As Double
minX = polygon(0).X
maxX = polygon(0).X
minY = polygon(0).Y
maxY = polygon(0).Y
For i = 1 To UBound(polygon)
Set q = polygon(i)
minX = vbMin(q.X, minX)
maxX = vbMax(q.X, maxX)
minY = vbMin(q.Y, minY)
maxY = vbMax(q.Y, maxY)
Next i
If p.X < minX Or p.X > maxX Or p.Y < minY Or p.Y > maxY Then
isPointInPolygon = False
Exit Function
End If
' SOURCE: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
isPointInPolygon = False
i = 0
j = UBound(polygon)
Do While i < UBound(polygon) + 1
If (polygon(i).Y > p.Y) Then
If (polygon(j).Y < p.Y) Then
If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
isPointInPolygon = True
Exit Function
End If
End If
ElseIf (polygon(i).Y < p.Y) Then
If (polygon(j).Y > p.Y) Then
If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
isPointInPolygon = True
Exit Function
End If
End If
End If
j = i
i = i + 1
Loop
End Function
Function vbMax(n1, n2) As Double
vbMax = IIf(n1 > n2, n1, n2)
End Function
Function vbMin(n1, n2) As Double
vbMin = IIf(n1 > n2, n2, n1)
End Function
Sub TestPointInPolygon()
Dim i As Integer
Dim InPolygon As Boolean
' MARKER Object
Dim p As CPoint
Set p = New CPoint
p.X = <ENTER X VALUE HERE>
p.Y = <ENTER Y VALUE HERE>
' POLYGON OBJECT
Dim polygon() As CPoint
ReDim polygon(<ENTER VALUE HERE>) 'Amount of vertices in polygon - 1
For i = 0 To <ENTER VALUE HERE> 'Same value as above
Set polygon(i) = New CPoint
polygon(i).X = <ASSIGN X VALUE HERE> 'Source a list of values that can be looped through
polgyon(i).Y = <ASSIGN Y VALUE HERE> 'Source a list of values that can be looped through
Next i
InPolygon = isPointInPolygon(p, polygon)
MsgBox InPolygon
End Sub
لقد قدم الثعبان تنفيذ nirg هو c++ رمز:
المدخلات
- bounding_points: العقد التي تشكل المضلع.
bounding_box_positions: المرشح يشير إلى التصفية.(في تنفيذ خلق من المربع المحيط.
(المدخلات هي قوائم الصفوف في الشكل:
[(xcord, ycord), ...])
يعود
- جميع النقاط التي تكون داخل المضلع.
def polygon_ray_casting(self, bounding_points, bounding_box_positions):
# Arrays containing the x- and y-coordinates of the polygon's vertices.
vertx = [point[0] for point in bounding_points]
verty = [point[1] for point in bounding_points]
# Number of vertices in the polygon
nvert = len(bounding_points)
# Points that are inside
points_inside = []
# For every candidate position within the bounding box
for idx, pos in enumerate(bounding_box_positions):
testx, testy = (pos[0], pos[1])
c = 0
for i in range(0, nvert):
j = i - 1 if i != 0 else nvert - 1
if( ((verty[i] > testy ) != (verty[j] > testy)) and
(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):
c += 1
# If odd, that means that we are inside the polygon
if c % 2 == 1:
points_inside.append(pos)
return points_inside
مرة أخرى, فكرة مأخوذة من هنا
وهيريس نقطة في اختبار المضلع في C التي لا تستخدم أشعة الصب. ويمكن أن تعمل لتداخل المناطق (التقاطعات النفس)، راجع حجة use_holes.
/* math lib (defined below) */
static float dot_v2v2(const float a[2], const float b[2]);
static float angle_signed_v2v2(const float v1[2], const float v2[2]);
static void copy_v2_v2(float r[2], const float a[2]);
/* intersection function */
bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
const bool use_holes)
{
/* we do the angle rule, define that all added angles should be about zero or (2 * PI) */
float angletot = 0.0;
float fp1[2], fp2[2];
unsigned int i;
const float *p1, *p2;
p1 = verts[nr - 1];
/* first vector */
fp1[0] = p1[0] - pt[0];
fp1[1] = p1[1] - pt[1];
for (i = 0; i < nr; i++) {
p2 = verts[i];
/* second vector */
fp2[0] = p2[0] - pt[0];
fp2[1] = p2[1] - pt[1];
/* dot and angle and cross */
angletot += angle_signed_v2v2(fp1, fp2);
/* circulate */
copy_v2_v2(fp1, fp2);
p1 = p2;
}
angletot = fabsf(angletot);
if (use_holes) {
const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);
angletot -= nested * (float)(M_PI * 2.0);
return (angletot > 4.0f) != ((int)nested % 2);
}
else {
return (angletot > 4.0f);
}
}
/* math lib */
static float dot_v2v2(const float a[2], const float b[2])
{
return a[0] * b[0] + a[1] * b[1];
}
static float angle_signed_v2v2(const float v1[2], const float v2[2])
{
const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);
return atan2f(perp_dot, dot_v2v2(v1, v2));
}
static void copy_v2_v2(float r[2], const float a[2])
{
r[0] = a[0];
r[1] = a[1];
}
ملحوظة: هذه هي واحدة من أساليب أقل الأمثل لأنه يتضمن الكثير من المكالمات إلى atan2f، ولكن قد تكون ذات فائدة للمطورين قراءة هذا الموضوع (في بلدي التجارب لها ~ 23X أبطأ ثم باستخدام طريقة تقاطع خط).
للكشف عن ضرب على المضلع نحن بحاجة إلى اختبار أمرين:
- إذا نقطة داخل المضلع المنطقة.(يمكن أن يتحقق من خلال راي الصب الخوارزمية)
- إذا كانت النقطة على المضلع الحدود(يمكن أن يتحقق عن طريق نفس الخوارزمية التي تستخدم نقطة الكشف على شكل متعدد الخطوط(الخط)).
للتعامل مع الحالات الخاصة التالية في راي صب الخوارزمية:
- راي التداخل واحد المضلع الجانب.
- النقطة داخل المضلع و راي يمر عبر قمة الرأس المضلع.
- نقطة خارج المضلع و راي فقط اللمسات أحد مضلع زاوية.
تحقق تحديد ما إذا كانت نقطة داخل مجمع المضلع.المادة يوفر وسيلة سهلة لحلها لذلك لن يكون هناك معاملة خاصة المطلوبة في الحالات المذكورة أعلاه.
ويمكنك القيام بذلك عن طريق فحص إذا كانت المنطقة التي شكلتها يربط بين نقطة المطلوب إلى القمم المضلع مباريات مجال المضلع نفسها.
وأو هل يمكن معرفة ما اذا كان مجموع الزوايا الداخلية من وجهة نظرك إلى كل زوج اثنين من القمم المضلع متتالية لالشيك مبالغ نقطة إلى 360، ولكن لدي شعور أن الخيار الأول هو أسرع لأنها لا تنطوي على انقسامات ولا حسابات معكوس الدوال المثلثية.
وأنا لا أعرف ماذا يحدث إذا المضلع لديه حفرة داخله ولكن يبدو لي أن الفكرة الرئيسية ويمكن أن تتكيف مع هذا الوضع
ويمكنك إضافة فضلا السؤال في مجتمع الرياضيات. أراهن لديهم واحد مليون وسائل للقيام بذلك
إذا كنت تبحث عن مكتبة جافا سكريبت هناك جوجل جافا سكريبت خرائط تمديد V3 لفئة مضلع لاكتشاف ما إذا كان أو لم يكن نقطة يتواجد داخلها.
var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3);
var isWithinPolygon = polygon.containsLatLng(40, -90);
عند استخدام كيو تي (كيو تي 4.3+) ، يمكن للمرء استخدام QPolygon وظيفة containsPoint
والجواب يعتمد على إذا كان لديك المضلعات بسيطة أو معقدة. يجب أن لا يكون مضلع بسيط أي تقاطعات القطعة المستقيمة. حتى يتمكنوا من الثقوب ولكن خطوط لا يمكن أن يعبر كل منهما الآخر. يمكن المناطق المعقدة لديها تقاطعات خط - حتى يتمكنوا من المناطق المتداخلة، أو المناطق التي تلامس بعضها البعض تماما بفارق نقطة واحدة
لمضلع بسيط أفضل الخوارزمية راي الصب (عدد معبر) الخوارزمية. للمضلعات معقدة، هذه الخوارزمية لا يكشف النقاط التي هي داخل المناطق المتداخلة. وذلك لالمضلعات المعقدة لديك لاستخدام لف عدد الخوارزمية.
وهنا مقالة ممتازة مع تنفيذ C كل من الخوارزميات. حاولت لهم وأنها تعمل بشكل جيد.
وسكالا نسخة من الحل عن طريق nirg (يفترض إحاطة المستطيل يتم قبل الاختيار على حدة):
def inside(p: Point, polygon: Array[Point], bounds: Bounds): Boolean = {
val length = polygon.length
@tailrec
def oddIntersections(i: Int, j: Int, tracker: Boolean): Boolean = {
if (i == length)
tracker
else {
val intersects = (polygon(i).y > p.y) != (polygon(j).y > p.y) && p.x < (polygon(j).x - polygon(i).x) * (p.y - polygon(i).y) / (polygon(j).y - polygon(i).y) + polygon(i).x
oddIntersections(i + 1, i, if (intersects) !tracker else tracker)
}
}
oddIntersections(0, length - 1, tracker = false)
}
وهنا هو الإصدار golang الإجابةnirg (مستوحاة C # رمز التي كتبهاM-كاتز)
func isPointInPolygon(polygon []point, testp point) bool {
minX := polygon[0].X
maxX := polygon[0].X
minY := polygon[0].Y
maxY := polygon[0].Y
for _, p := range polygon {
minX = min(p.X, minX)
maxX = max(p.X, maxX)
minY = min(p.Y, minY)
maxY = max(p.Y, maxY)
}
if testp.X < minX || testp.X > maxX || testp.Y < minY || testp.Y > maxY {
return false
}
inside := false
j := len(polygon) - 1
for i := 0; i < len(polygon); i++ {
if (polygon[i].Y > testp.Y) != (polygon[j].Y > testp.Y) && testp.X < (polygon[j].X-polygon[i].X)*(testp.Y-polygon[i].Y)/(polygon[j].Y-polygon[i].Y)+polygon[i].X {
inside = !inside
}
j = i
}
return inside
}
فاجأ أحد إلى هذا الموضوع في وقت سابق, ولكن البراغماتيين تتطلب قاعدة البيانات:MongoDB ممتازة دعم الجغرافية الاستفسارات بما في ذلك هذا واحد.
ما تبحث عنه هو:
db.الأحياء.findOne({ هندسة:{ $geoIntersects:{ $هندسة:{ نوع:"نقطة" ، إحداثيات:[ "الطول", "latitude" ] } } } })
Neighborhoods هو المجموعة التي متجر واحد أو أكثر من المضلعات في معيار GeoJson الشكل.إذا كان الاستعلام بإرجاع null ليس تتقاطع وإلا فمن.
موثقة بشكل جيد جدا هنا:https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/
أداء أكثر من 6000 نقطة المصنفة في 330 مضلع غير منتظم الشبكة كان أقل من دقيقة واحدة بدون الأمثل في كل وقت تحديث الوثائق مع كل مضلع.
