متوازي الأضلاع يحتوي على نقطة

Question

ما هي الطريقة الأسرع من يقرر إذا كانت نقطة داخل متوازي الاضلاع/المعيني?

Answer 1

ومرحبا مرة أخرى وشكرا لجميع إجاباتك. في هذه الأثناء وأنا شخصيا قد حان حتى مع شيء وأعتقد أن تكون سريعة إلى حد ما:

وتخيل لدينا متوازي الاضلاع التي امتدت من PQ والعلاقات العامة، حيث PQ والعلاقات العامة وناقلات (P، Q و R هي زوايا). وعلاوة على ذلك قمنا النقطة التي تريد أن تحقق يسمى A.

ونحن نعلم أن ناقلات PA يمكن تقسيمها إلى متجهين موازية لPQ والعلاقات العامة:

PA=n*PQ+m*PR

والآن نحن نعلم أن ن م ويجب أن تكون في الفترة [0؛ 1]، ونحن في حل ن وم:

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

وأين ديت (PA، PQ) هو المحدد للناقلات السلطة الفلسطينية وPQ:

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

وإذا كانت النقطة (أ) هو داخل متوازي الاضلاع ثم 0 <= ن <= 1 و 0 <= م <= 1، وهذا يعطينا شبة الكود:

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}

Answer 2

وتخيل أشعة الصادرة من وجهة نظرك في اتجاه واحد. إذا كان هذا راي يعبر خطوط الشكل الخاص بك على عدد فردي من المرات، انها داخل الشكل. اذا اجتازت عدد زوجي من المرات، انها خارج الشكل.

وهكذا في البرنامج كنت مجرد إنشاء خط غير مرئي، ونرى كيف غالبا ما يعبر. أكشن ربما قد بنيت في وظيفة للقيام بذلك، وأنا أتصور.

والآن، إذا كنت قد حصلت على نصف طن من الأشياء ونقطة يمكن أن يكون إلا في واحدة، يمكنك تسريع الامور باستخدام <لأ href = "http://en.wikipedia.org/wiki/Binary_space_partitioning" يختلط = "نوفولو noreferrer"> ثنائي التقسيم الفضاء لتخزين المواقع من الكائنات. وبهذه الطريقة، لم يكن لديك لمقارنة وجهة نظرك مع كل كائن واحد، فقط تلك القريبة منها.

Answer 3

وانظر جوابي على هذا السؤال ، التي هي مشابهة جدا. هناك، وأعطي ما أعتقد هو اختبار سهل جدا في حالة أن متوازي الاضلاع لديها واحد من أركانها في (0,0) لأنه يجعل التفسير الأسهل لننظر، ولكن ليس من الصعب جدا لتعديله للعمل بشكل عام.

وتحرير: منذ المالك السؤال هو مألوف مع ناقلات، سوف يعيد كتابة أساسا جوابي في تلك اللغة. لنفترض أن امتدت متوازي الاضلاع من قبل ناقلات PQ وPR، حيث P، Q، وR هي الزوايا. سوف * رمز دلالة المنتج نقطة. اختيار q نقطة بحيث PQ عمودي على Pq (أي Pq*PQ=0) وPR*Pq>0 (على سبيل المثال، يمكن أن تحصل q عن طريق تناوب Q حول P من 90 درجة). أيضا اختيار r نقطة بحيث PR*Pr=0 وPQ*Pr>0. ثم A نقطة في الداخل إذا وفقط إذا (0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR).

Answer 4

يصف طريقة لتحديد مكان شعاع و تتقاطع الرباعي. ويمكن أن تكون مبسطة أكثر إذا الرباعي هو متوازي الاضلاع.

إذا كان لديك متوازي مع الجانبين المجاورة التي وصفها ناقلات <م> AB و <م> AC . أي نقطة في الطائرة من متوازي الاضلاع يمكن وصفها من قبل ناقلات التالي

T(a, b) = A + a * AB + b * AC

ويمكن وصف أي راي باعتبارها أصل <م> O والتوجيه <م> D

R(t) = O + t * D

وتقاطع 2 هو عندما T(a, b) == R(t)

O + t * D = A + a * AB + b * AC

وحل هذا لa وb وتحقق من أن كلاهما بين 0 و 1. انظر شبة الكود في نهاية ورقة عن كيفية تنفيذ ذلك.

Answer 5

وتعطى المعادلة القياسية من خط كما الفأس + ب س + ج = 0 .. ولكن المثير للاهتمام، إذا كنت تأخذ هذا التعبير الفأس + ب س + ج، وتقييم نقاط س، ص نظرا لأ، ب، ج ل ك خط معين، وسوف تجد أن التعبير تقسيم الطائرة إلى نصفين، نصف حيث كان التعبير أكبر من الصفر، والنصف الآخر حيث هو أقل من ذلك.

والآن، إذا كنت تأخذ أربع نقاط من متوازي الاضلاع الخاص بك، وحساب أ، ب، معاملات ج لكل خط التي تشكل جانب من متوازي الاضلاع، يمكنك تقييم كل تعبير لx و y في السؤال والبحث من أي جانب من كل سطر هذه النقطة هي جرا. و<م> داخل من متوازي الاضلاع ستكون منطقية ومن الجانبين معينة.

وأي بمعنى، مرة واحدة لديك أ، ب، ج ولكل واحد من أربعة أسطر، يمكنك إجراء اختبار <م> شيء مثل

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

و.. خدعة الكائن الوحيد المتبقي لديك لتحديد "قطبية" من كل اختبار علامة، أي أكبر أو أقل من الصفر. طريقة سهلة للقيام بذلك هي لتقييم 0،0، ومعرفة ما إذا كان على الجانب الذي تريد، والذي يصل إلى القول إن علامة 'ج' يخبرك الطريقة التي لاختبار.

وباعتراف الجميع، انها نوع من طريقة القوة الغاشمة للقيام بذلك، ولكن يمكن أن تمتد إلى العمل من أجل أي مضلع محدب .. أو إزالة نقطة وكان يعمل لمثلثات، أيضا.

Answer 6

وقائي الاول الملاحظة حول هذه المشكلة هي أن مستطيل (تتماشى مع محاور) هو حالة منحطة بسيطة. إذا ركنين من هذا المستطيل هي: (X1، Y1) و (X2، Y2) فإنك ببساطة اختبار، نظرا نقطة (X3، Y3)، التي دقيقة (X1، X2)

وهذا قد يكون أيضا الأمثل مفيد. وإذا وجدنا الانحياز محور المحيط مستطيل متوازي الاضلاع لدينا بعد ذلك يمكننا أن نبدأ مع اختبار سريع في أي لحظة معينة ضد ذلك.

إذا التشابه لدينا منحدر غير الصفر ثم نحسب التقاطعات محور خطوط المحيط بنا وتقاطع الخطوط التي تمر عبر نقطة في المسألة في تلك المنحدرات. إذا كان كل من التقاطعات وجهة نظرنا في (المعرفة من قبل كل من المنحدرات) تقع بين لنا تقاطعات خطوط إحاطة لدينا بعد ذلك نحن فيه. إذا كان أي من هذه خارج هذه النطاقات ثم نحن لسنا.

وليس لدي الوقت لرمز يصل مثالا لكن الحوسبة هذه المنحدرات والتقاطعات هي أول الجبر العام.

[إضافات]

وأرى الآن أن أول وظيفة (بخصوص راي من وجهة لفحصها ويمتد على طول المنحدر أي التعسفي) هو إشارة إلى حل عام لهذه المشكلة لأي مضلع مستو مغلقة ... أو، في الواقع، ل أي منحنى مستو مغلقة. ويمكن أيضا أن تمتد إلى ثلاثة أبعاد للأسطح مغلقة.

وهناك، ولكن، واحد التحذير ينطبق على متوازيات الأضلاع ولا لأشباه المعين. في حالة مضلع مقعر (أو بعض منحنيات أخرى) إذا كان راي يضرب أي قمة (الزاوية) ثم فمن الممكن أن الاختبار بإرجاع عدد زوجي من المعابر "الخط". وبعبارة أخرى أي جزء من "منحنى" التي في نفس الوقت تدرج في عدة "الجانبين" المضلع يمكن إرجاع إيجابية كاذبة.

واثنين من حلول لهذه ستكون كما يلي: اختبار صراحة على التقاطعات في حدود القطعة المستقيمة (الزاوية / الحصان) أو علاج كل قطعة مستقيمة كما يحدها من طرف واحد من قبل (نقطة + إبسيلون) (بحيث الحسابية لدينا لا تجد أي لحظة من القواسم المشتركة بين أي الجانبين).

وفكرتي في العثور على المستطيل المحيط لا تزال اختبار سريع مفيد ولا تمتد بشكل عام على جميع المضلعات. نجد دقيقة () وماكس () س للعثور على الجانبين الأيسر والأيمن المحيط ودقيقة () ووالحد الأقصى () ص للعثور على أسفل وأعلى ساق. كما يمكن تمديد هذه لثلاثة أبعاد ... وصديق يقول لي أن المكتبات الرسومات القياسية تستخدم هذا على نطاق واسع لكشف التصادم في معظم الواقع وومنتديات الظاهري، وما إلى ذلك عند الاصطدامات تجد في إحاطة المربعات ثم يفعلون الحسابية أكثر غرامة الحبيبات على المضلعات التي يتم الواردة فيه.

Answer 7

إذا متوازي الاضلاع هو محدب (ونظرا لتعريف متوازي الاضلاع يجب أن يكون الانجاز)، ثم اي خوارزمية لاختبار ما اذا كان في حدوده ينبغي القيام به، يمكنك تحسين كفاءة الفتح حلقة، لأنك تعرف أن هناك فقط 4 القمم ، على سبيل المثال.

وهنا هو خوارزمية بسيطة أن يختبر نقطة يجري على نفس الجانب من جميع القطاعات، على أساس الحق في قاعدة اليد المنتج اتجاهي (يمكنك تحسين ذلك أيضا عن طريق استبدال تقسيم لتطبيع ناقلات مع اختبار افتة بسيطة ):

<وأ href = "https://stackoverflow.com/questions/1119627/how-to-test-if-a-point-is-inside-of-a-convex-polygon-in-2d-integer- تنسق / 1119673 # 1119673 "> كيفية معرفة ما إذا كانت نقطة داخل مضلع محدب في 2D عدد صحيح الإحداثيات؟

وثمة خيار آخر، إذا كنت تنوي القيام به الكثير من المقارنات ضد نفس متوازي الاضلاع هو تطبيع إلى ساحة، يجب الحصول على المصفوفة التي لا تحول، وفي كل مرة تحصل على نقطة لاختبار، اضربها في مصفوفة ومن ثم معرفة ما اذا كان نقطة تحول هي داخل المربع تطبيع (الذي يجب أن يكون أسهل من ذلك بكثير).

Answer 8

1. الحصول على كفاف المضلع
2. تحقق مما إذا كانت النقطة تقع في countour

dist1 = cv2.pointPolygonTest(contours[0], (50, 70), True)

dist يعود واحد من الثلاثة التالية:

• قيمة إيجابية إذا كان الموضوع داخل محيط
• قيمة سالبة إذا كان الموضوع خارج محيط
• صفر إذا كانت النقطة على كفاف

كيف للتحقق مما إذا كان يتم وضع نقطة داخل محيط?

Answer 9

ووذ تنسيق هو أبسط، لذلك تبدأ مع ذلك. إذا ذ تنسيق من نقطة ما بين الجزء العلوي والسفلي من الشكل، انتقل إلى العاشر تنسيق. حساب العاشر تنسيق من الجانبين الأيمن والأيسر من شكل في ذ تنسيق من هذه النقطة، ومعرفة ما اذا كان س تنسيق نقطة بينهما.

وتحرير:

ونظرا لإحداثيات أربعة من أعلى اليسار، أعلى يمين، أسفل اليمين والزوايا السفلية اليسرى:

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}