تبحث عن خوارزمية فعالة العثور بسرعة على أقرب خط (التي يحددها مسافة عمودية) إلى نقطة التعسفي

Question

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

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

وأنا لم أرى هذا:خوارزمية أقرب الكشف عن الحافة فيما يتعلق نقطة (في جميع الاتجاهات)

ولكن ذلك يعتمد على طريقة الاجتياح و عدد قليل من خطوط محدودة الطول.

Answer 1

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

هناك العديد من الطرق preprocess مستو وحداتها من أجل حل موقع نقطة المشكلة مع لوغاريتمي الوقت التعقيد.بعض البيانات الهرمية هيكل يتم عادة وضعها ، والتي يمكن اجتيازه للحصول على أي استفسار نقطة ، إنه أثبت أن طول اجتياز مسار محدود $O(log(N))$, حيث $N$ هو عدد من المناطق.كما @مستعار ذكر في التعليقات يمكنك أيضا استخدام ثنائي تقسيم مساحة (BSP) لبناء BSP الشجرة - كما انها البيانات الهرمية هيكل (شجرة ثنائية) ، والتي سوف تسمح لك أن بكفاءة العثور على المنطقة التي تحتوي على استعلام نقطة.يبدو أن مشكلتك تناسب بشكل جيد لهذا BSP النهج.

آسف أن أقول ، يمكنك الحصول على المناطق $O(n)$ الحدود شرائح/الأشعة ، حيث $n$ عدد الخطوط.للتغلب على هذه الصعوبة يمكنك أيضا تقسيم كل منطقة إلى Voronoi الرسم البياني, المعمم على الحدود قطاعات الأشعة.فإنه من السهل أن نرى أن إجمالي عدد هذه المكرر المناطق سوف تكون محدودة $O(n^2)$, التي لا تزال يعطيك لوغاريتمي تعقيد الوقت لأقرب خط البحث.ومع ذلك في متوسط الحال هذه المناطق مع العديد من الحدود شرائح/أشعة سوف يشكلون جزء صغير من جميع المناطق في المتوسط كنت لا تزال وسوف تكون قادرة على بسرعة تحديد أقرب الحدود الجزء/راي فقط من خلال حلقات على حدود المنطقة.

---

إذا كنت تريد أن تعرف المزيد عن الخصائص العامة الهندسية هيكل كنت تعمل مع - فمن المنطقي أن قراءة هذا صفحة ويكي.

Answer 2

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