بناء محيط مضلع (ولا سيما في التثليث)

Question

وكيف لي أن التوجه نحو بناء محيط مضلع 2D الذي يتكون من مثلثات فقط، وأنه يمكن أن يكون الثقوب وكفاف الخارجي يمكن أن تكون مقعرة / محدب والثقوب يمكن أيضا أن تكون مقعرة / محدب.

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

هل octrees / quadtrees موافقة إلى هذا؟

Answer 1

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

Answer 2

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

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

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