هل توجد خوارزمية فعالة لإنشاء هيكل مقعر ثنائي الأبعاد؟

https://stackoverflow.com/questions/83593

01-07-2019
|

سؤال

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

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

المحلول

هذا ورقة تناقش توليد فعال للمضلعات البسيطة لوصف شكل مجموعة من النقاط في المستوى ويوفر الخوارزمية.يوجد أيضًا تطبيق Java صغير يستخدم نفس الخوارزمية هنا.

نصائح أخرى

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

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

توفر هذه الورقة بعض المراجع الإضافية التي يمكنك متابعتها.

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

وهنا أ مجموعة جيدة من المراجع يتضمن ما سبق وقد يقودك إلى إيجاد نهج أفضل.

قد تظل الإجابة مثيرة للاهتمام لشخص آخر:يمكن للمرء أن يطبق أ اختلاف خوارزمية مربع المسيرة, ، يتم تطبيقه (1) داخل الهيكل المقعر، و(2) ثم على (على سبيل المثال.3) مختلفة مقاييس أن بلدي يعتمد على متوسط كثافة النقاط.يجب أن تكون المقاييس مضاعفات حقيقية لبعضها البعض، بحيث يمكنك إنشاء شبكة يمكنك استخدامها لأخذ العينات بكفاءة.يتيح ذلك العثور بسرعة على العينات الفارغة=المربعات، والعينات الموجودة بالكامل ضمن "مجموعة/سحابة" من النقاط، وتلك الموجودة بينهما.يمكن بعد ذلك استخدام الفئة الأخيرة لتحديد الخط المتعدد الذي يمثل جزءًا من الهيكل المقعر بسهولة.

كل شيء خطي في هذا النهج، ولا حاجة إلى التثليث، ولا يستخدم أشكال ألفا ويختلف عن العرض التجاري/براءة الاختراع كما هو موضح هنا ( http://www.concavehull.com/ )

الحل البسيط هو التجول حول حافة المضلع.نظرًا لوجود حافة حالية عند نقاط الاتصال الحدودية P0 وP1، فإن النقطة التالية على الحدود P2 ستكون النقطة ذات أصغر A ممكن، حيث

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

ثم قمت بتعيين

P0 <- P1
P1 <- P2

وكرر ذلك حتى تعود من حيث بدأت.

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

سؤال جيد!لم أجرب هذا على الإطلاق، لكن أول تجربة لي ستكون هذه الطريقة التكرارية:

أنشئ مجموعة N ("غير متضمنة")، وأضف جميع النقاط في مجموعتك إلى N.
اختر ثلاث نقاط من N عشوائيًا لتكوين المضلع الأولي P.أخرجهم من N.
يستخدم بعض خوارزمية النقطة في المضلع وإلقاء نظرة على النقاط في N.لكل نقطة في N، إذا كانت موجودة الآن بواسطة P، فقم بإزالتها من N.بمجرد العثور على نقطة في N لا تزال غير موجودة في P، تابع إلى الخطوة 4.إذا أصبح N فارغًا، فقد انتهيت.
اتصل بالنقطة التي وجدتها A.ابحث عن السطر P الأقرب إلى A وأضف A في منتصفه.
ارجع إلى الخطوة 3

أعتقد أنها ستنجح طالما أنها تؤدي أداءً جيدًا بما فيه الكفاية - قد يكون من المفيد الحصول على إرشاد جيد لنقاطك الثلاث الأولية.

حظ سعيد!

يمكنك القيام بذلك في QGIS باستخدام هذا المكون الإضافي؛https://github.com/detlevn/QGIS-ConcaveHull-Plugin

اعتمادًا على كيفية تفاعلك مع بياناتك، ربما يستحق التحقق من كيفية القيام بذلك هنا.

يحتوي Bing Maps V8 SDK التفاعلي على خيار هيكل مقعر ضمن عمليات الشكل المتقدمة.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

في ArcGIS 10.5.1، يحتوي ملحق 3D Analyst على أداة الحد الأدنى لحجم الحدود مع أنواع الأشكال الهندسية للهيكل المقعر، أو الكرة، أو المغلف، أو الهيكل المحدب.ويمكن استخدامه على أي مستوى الترخيص.

توجد خوارزمية بدن مقعرة هنا: https://github.com/mapbox/concaveman

الحل التقريبي السريع (مفيد أيضًا للأجسام المحدبة) هو إيجاد الحدود الشمالية والجنوبية لكل عنصر صغير من الشرق إلى الغرب.

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

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

كمرجع معتمد على نطاق واسع، يبدأ PostGIS بهيكل محدب ثم يغطسه، يمكنك رؤيته هنا.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow