كيف يمكنني تحديد ما إذا كان اثنين محدبة المضلعات التداخل ؟

Question

لنفترض أن هناك عدد من المضلعات المحدبة الطائرة ربما الخريطة.هذه المضلعات يمكن أن يرفعه ضد بعضهم البعض وتبادل ميزة, ولكن لا يمكن أن تتداخل.

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

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

قد لا بشكل صحيح تعداد الحالات ؟ أي اقتراحات من أجل اختبار هذه الحالات ؟

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

Answer 1

يمكنك استخدام خوارزمية الاصطدام هذه:

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

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

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

فكيف هذا يساعدنا بشكل ملموس في تحديد ما إذا كان المضلع A و B interersect؟ حسنا، نحن نذهب فقط إلى كل جانب من كل مضلع وتحقق مما إذا كان يشكل محورا منفصلا. للقيام بذلك، سنكون نستخدم بعض الرياضيات المتجهات الأساسية لاسكواخ جميع نقاط المضلعات على خط عمودي على خط الفصل المحتمل (انظر الشكل 2). الآن المشكلة بأكملها هي مريح 1 الأبعاد. يمكننا تحديد المنطقة التي تتميز فيها النقاط لكل كذبة مضلع، وهذا الخط محور منفصل إذا لم تتداخل هذه المناطق.

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

Answer 2

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

• للقضاء على الحواف ، تبدأ مع المضلع على اليسار.تأخذ شريحة خط من مركز المضلع الذي هو عمودي على خط الجزء السابق رصاصة و يلمس جانبي المضلع.نسمي هذا جزء من خط p, مع الذروات p1 و p2.ثم لجميع الذروات إذا الإحداثي x أقل من p1.x و p2.x vertex يمكن أن تذهب في "آمنة دلو".

• إذا لم يكن لديك للتحقق للتأكد من أنها على "آمنة" الجانب الآخر من الخط (فقط التحقق y إحداثيات جدا)

-إذا كان جزء من خط في المضلع كل الذروات في "آمنة دلو" يمكنك تجاهله.

-عكس قطبية حتى أنت "الحق" الموجهة الثاني المضلع.

Answer 3

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

للاختبار، أود فقط أن أتأكد من اختبار كل مزيج محتمل. واحد مفقود أعلاه من ما أراه هو حافة واحدة مشتركة، ولكن بولي واحد موجود في الآخر. أود أيضا إضافة اختبارات لبعض أشكال بولي أكثر تعقيدا، من TRI -> العديد منها، تماما كإجراء وقائي.

أيضا، إذا كان لديك بولي على شكل حرف يو تحيط تماما بولي، لكنني لم يتداخل، وأعتقد أن قضيتك ستتعامل مع ذلك، لكنني سأضيف ذلك كشيك، كذلك.

Answer 4

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

Answer 5

gjk. الاصطدام كشف ينبغي الشغل.

Answer 6

إليك فكرة:

• العثور على نقطة المركز لكل مضلع

• ابحث عن نقطتين من كل مضلع الأقرب إلى النقطة المركزية للآخر. سيكونون نقاطا مجاورة في مضللي محدب. هذه تحديد أقرب حافة لكل مضلع، دعونا نسمي النقاط {a، b} و {y، z}

• العثور على تقاطع الخطوط AB و YZ. إذا تعبر قطاعات الخط (تقاطع AB بين A و B)، تتقاطع المضلعات الخاصة بك. إذا كانت AB و XY متوازية تجاهل هذه الحالة، فستتحمل الخطوة التالية المشكلة.

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

Answer 7

هناك عدة طرق للكشف عن التقاطع و / أو الاحتواء بين مضللي محدب. كل هذا يتوقف على مدى كفاءة الخوارزمية. النظر في اثنين من مضلع المحدبة R و B مع رؤوس R و B على التوالي:

1. خط الاجتياح خوارزمية مقرها. كما ذكرت أنه يمكنك إجراء إجراء خط الاجتياح والحفاظ على الفواصل الزمنية الناتجة عن تقاطع المضلعات مع خط كاسح. إذا تداخل فترات الزملاء في أي وقت، فتقاطع المضلعات. التعقيد هو O ((R + B) سجل (r + b)).
2. الدورية لل callipers. خوارزمية مقرها. يرى هنا و هنا لمزيد من التفاصيل. التعقيد هو O (R + B) الوقت.
3. يمكن العثور على الأساليب الأكثر كفاءة هنا و هنا. وبعد تأخذ هذه الخوارزميات O (سجل R + سجل ب).