كيفية أخذ عينة فرعية من مضلع ثنائي الأبعاد؟

Question

لدي مضلعات تحدد محيط المقاطعات في المملكة المتحدة.هذه الأشكال مفصلة للغاية (من 10 إلى 20 ألف نقطة لكل منها)، مما يجعل الحسابات ذات الصلة (هل النقطة X في المضلع P؟) باهظة الثمن من الناحية الحسابية.

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

الشيء التافه هو أن تأخذ واحدة في كل مرة N النقاط (وبالتالي أخذ عينات فرعية بواسطة عامل N)، ولكن هذا يبدو "خامًا" جدًا.أفضل أن أقوم بحساب متوسط ​​النقاط، أو شيء من هذا القبيل.أي مؤشر؟

Answer 1

يتبادر إلى ذهني حلان:

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

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

Answer 2

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

ويستخدم نهج الجيران الأقرب لحساب المنطقة.

العينات:

هنا يمكنك طلب نسخة من الورقة.

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

هث!

Answer 3

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

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