تقليل المضلع القمم

Question

ما هو خوارزمية جيدة للحد من عدد من القمم في مضلع بدون تغيير الطريقة التي تبدو كثيرا ؟

الإدخال:مضلع تمثل قائمة من النقاط ، مع الكثير من verticies:المدخلات الخام من الماوس ، على سبيل المثال.

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

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

Edit2:دوغلاس Peucker الخوارزمية هو ما كنت تريد حقا.

Answer 1

تحرير:انظروا تبسيط المضلعات

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

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

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

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

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

هذا بعد لديه بعض التفاصيل عن محدبة هال جزء.

Answer 2

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