ما هي أسرع طريقة للعثور على أقصر مسافة ديكارتية بين مضلعين؟

https://stackoverflow.com/questions/84034

01-07-2019
|

سؤال

أملك 1 مضلع أحمر قل و 50 مضلعًا أزرقًا تم وضعهم بشكل عشوائي - تقع جغرافيا مساحة ثنائية الأبعاد.ما هي الخوارزمية الأسرع/الأسرع للعثور على أقصر مسافة بين المضلع الأحمر وأقرب مضلع أزرق له؟

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

لذا في النهاية - يجب أن تعيد الإجابة أقرب مضلع أزرق إلى المضلع الأحمر المفرد.

هذا أصعب مما يبدو!

المحلول

أشك في وجود حل أفضل من حساب المسافة بين اللون الأحمر وكل اللون الأزرق وفرزها حسب الطول.

فيما يتعلق بالفرز، عادةً ما يكون من الصعب التغلب على QuickSort في الأداء (وهو أداء محسّن، يمنع التكرار إذا انخفض الحجم إلى أقل من 7 عناصر ويتحول إلى شيء مثل InsertionSort، وربما ShellSort).

وبالتالي أعتقد أن السؤال هو كيفية حساب المسافة بين مضلعين بسرعة، بعد كل شيء تحتاج إلى إجراء هذا الحساب 50 مرة.

سيعمل الأسلوب التالي مع العرض ثلاثي الأبعاد أيضًا، ولكنه ربما لا يكون الأسرع:

الحد الأدنى لمسافة المضلع في الفضاء ثنائي الأبعاد

السؤال هو، هل أنت على استعداد لمقايضة الدقة بالسرعة؟على سبيل المثاليمكنك تجميع كل المضلعات في مربعات محيطة، حيث تكون جوانب المربعات موازية لمحاور نظام الإحداثيات.تستخدم الألعاب ثلاثية الأبعاد هذا الأسلوب في كثير من الأحيان.لذلك تحتاج إلى العثور على القيم القصوى والدنيا لكل إحداثي (x، y، z) لإنشاء المربع المحيط الافتراضي.يعد حساب المسافات بين هذه المربعات المحيطة مهمة تافهة جدًا.

فيما يلي صورة نموذجية للمربعات المحيطة الأكثر تقدمًا، والتي لا تكون موازية لمحاور نظام الإحداثيات:

المربعات المحيطة الموجهة - OBB

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

تُظهر الصورة التالية مربعًا محيطًا بمحاذاة المحاور:

المربع المحيط بمحاذاة المحاور - AABB

OOBs أكثر دقة، وAABBs أسرع.ربما ترغب في قراءة هذا المقال:

تقنيات الكشف عن الاصطدام المتقدمة

يفترض هذا دائمًا أنك على استعداد لمقايضة الدقة بالسرعة.إذا كانت الدقة أكثر أهمية من السرعة، فقد تحتاج إلى تقنية أكثر تقدمًا.

نصائح أخرى

قد تتمكن من تقليل المشكلة، ثم إجراء بحث مكثف على مجموعة صغيرة.

قم بمعالجة كل مضلع أولاً من خلال إيجاد:

مركز المضلع
الحد الأقصى لنصف قطر المضلع (أي نقطة على الحافة/السطح/قمة المضلع الأبعد عن المركز المحدد)

الآن يمكنك جمع، على سبيل المثال، أقرب 5 إلى 10 مضلعات من المضلع الأحمر (ابحث عن المسافة من المركز إلى المركز، واطرح نصف القطر، وفرز القائمة واحصل على أعلى 5 مضلعات) ثم قم بإجراء روتين أكثر شمولاً.

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

لكل قمة في المقبض الأحمر ، قم بحساب المسافة إلى كل قمة في المضلعات الزرقاء وابحث عن الأقرب (تلميح ، قارن المسافة^2 حتى لا تحتاج إلى SQRT ()) ابحث عن الأقرب ، ثم تحقق من القمة على كل جانب من القمة الحمراء والأزرق التي تم العثور عليها لتحديد مقاطع الخطوط الأقرب ومن ثم العثور على النهج الأقرب بين قسمين خطين.

يرى http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (من السهل ببساطة بالنسبة للحالة الثانية)

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

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

بالطبع يمكنك إضافة طريقة تقريبية مثل المربعات المحيطة لتحديد المضلعات الزرقاء التي لا يمكن أن تتقاطع مع المنطقة الحمراء بسرعة.

ربما مسافة Frechet هي ما تبحث عنه؟

حساب مسافة فريشيه بين منحنيين متعددي الأضلاع
حساب مسافة فريشيه بين المضلعات البسيطة

أعلم أنك قلت "أقصر مسافة" لكنك تقصد حقًا الحل الأمثل أم أن الحل "جيد/جيد جدًا" مناسب لمشكلتك؟

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

لذلك، إذا كان لديك عدد قمة يجعل هذا المربع رقمًا مخيفًا وكان الحل "جيد/جيد جدًا" مناسبًا لك، فابحث عن حل إرشادي أو تقريبي.

قد ترغب في إلقاء نظرة على Voronoi Culling.الورق والفيديو هنا:

http://www.cs.unc.edu/~geom/DVD/

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

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

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

نأمل أن يساعد

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

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

يمكن أن يكون لاختيارك للدوائر/المربعات المحاذاة محوريًا، أو المربعات الموجهة تأثيرًا كبيرًا على أداء الخوارزمية، اعتمادًا على التخطيط الفعلي لمضلعات الإدخال.

لحساب الحد الأدنى الفعلي للمسافة، يمكنك استخدام طريقة Yang et al'sخوارزمية سريعة جديدة لحساب المسافة بين مضلعين محدبين منفصلين اعتمادا على مخطط فورونوي' وهو O (log n + log m).

يجب أن أركض إلى جنازة في ثانية واحدة، ولكن إذا قمت بتقسيم المضلعات الخاصة بك إلى مناطق فرعية محدبة، فهناك بعض التحسينات التي يمكنك القيام بها.يمكنك إجراء عمليات بحث ثنائية على كل بولي للعثور على أقرب قمة، ثم I يعتقد يجب أن تكون أقرب نقطة هي تلك القمة أو الحافة المجاورة.هذا يعني أنه يجب أن تكون قادرًا على القيام بذلك log(log m * n) حيث m هو متوسط عدد الرؤوس على المضلع، و n هو عدد المضلعات.هذا نوع من التسرع، لذلك قد يكون خطأ.سأقدم المزيد من التفاصيل لاحقا إذا رغبت في ذلك.

يمكنك البدء بمقارنة المسافة بين المربعات المحيطة.يعد اختبار المسافة بين المستطيلات أسهل من اختبار المسافة بين المضلعات، ويمكنك على الفور إزالة أي مضلعات تكون أكثر من أقرب_مستقيم + قطري (ربما يمكنك تحسين ذلك أكثر).وبعد ذلك، يمكنك اختبار المضلعات المتبقية للعثور على أقرب مضلع.

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

أعتقد أن ما تبحث عنه هو خوارزمية A*، المستخدمة في تحديد المسار.

الطريقة الساذجة هي إيجاد المسافة بين الجسم الأحمر و50 جسمًا أزرقًا - لذا فأنت تنظر إلى 50 عملية حسابية فيثاغورسية ثلاثية الأبعاد + الفرز للعثور على الإجابة.هذا من شأنه أن يعمل فقط على إيجاد المسافة بين النقاط المركزية.

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

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

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

لا تنتمي إلى StackOverflow