بالنظر إلى مجموعة كبيرة من القمم في مضلع غير محبط ، كيف يمكنني العثور على الحواف؟

Question

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

العديد من القمم في A زائدة عن الحاجة لأنها داخل الشكل ، أريد التخلص من هذه القمم.

سؤالي مشابه ل أفضل خوارزمية للعثور على حواف (مضلع) من القمم لكنني في حاجة إليها للعمل في حالة مضلعة غير محفورة.

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

لديّ مجموعة من القمم داخل وعلى حدود المضلع: [[X1 ، Y1] ، [X2 ، Y2] ...] أريد تقليل المجموعة بحيث تكون القمم مجرد الخطوط العريضة للحدود.

Answer 1

يبدو أن هذا موضوع ساخن ..https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

يبدو أن هذه الورقة هي الأفضل.Duckham ، M. ، Kulik ، L. ، Worboys ، MF ، Galton ، A. (2008) جيل فعال من المضلعات البسيطة لتوصيف شكل مجموعة من النقاط في الطائرة. التعرف على الأنماط V41 ، 3224-3236

Answer 2

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

(يتم تقديم هذه الإجابة أيضًا في السؤال الذي ترتبط به والذي يبدو أنه حالة خاصة لسؤالك)

Answer 3

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

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

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

Answer 4

المصطلح الذي تبحث عنه بدن مقعر.

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

أحد أبسط النهج هو أنك تستخدم خوارزمية تغليف الهدايا ولكن بدلاً من النظر في جميع النقاط في كل خطوة تفكر فيها فقط ك-جيران في قمة الرأس الحالية.

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

---

فيما يلي بعض الروابط ذات الصلة:

• https://github.com/mapbox/concaveman
• https://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for-concave-hull
• بدن مقعر: نهج الجيران K-nearest لحساب المنطقة التي تشغلها مجموعة من النقاط (حلقة الوصل)