حاوية شريحة خط لتقاطع الأشعة السريع؟ (2D)

Question

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

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

رابط إلى مقال مناسب جيد، رمز C ++ هو أفضل. شكرا! :)

ملاحظة: شرائح الخط هي في الواقع حواف مضلع غير ذاتي الذاتي، مرتبة في طلب CCW ... ولكن أعتقد أنه قد يكون هناك بعض ميزة فرزها بطريقة مختلفة؟

هذا هو كل 2D.

---

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

Answer 1

يمكنك أن تأخذ صندوقا محيطا من المضلع (إحداثيات MIN-MAX X، Y) وبناء شبكة داخل الصندوق. ثم، لكل خلية، تذكر جميع الخطوط التي تعبر الخلية.

العثور على intesection مثل هذا:

• معرفة أي خلية يضرب راي أولا (O (1))
• يستخدم خوارزمية اجتياز الشبكة إلى "رسم" أشعة من خلال الشبكة. عندما تضغط على خلية غير فارغة، تحقق من كل خطوطها، تحقق مما إذا كانت التقاطع داخل الخلية واختر أقرب تقاطع. إذا كانت جميع التقاطعات خارج الخلية، فتابع (هذا س (طول الشبكة)).

يمكنك أيضا جعل الشبكة الهرمية (أي. quadtree - شجرة كنت تسأل)، والمشي باستخدام نفس الخوارزمية. يتم ذلك في Raytracing في 3D والوقت التعقيد هو O (SQRT (N)).

---

أو، استخدم النهج الذي فعلته في بلدي RayTracer:

• القيام بالبناء quadtree تحتوي على الخطوط (بناء Quadtree) في المقالة) - قمت بتقسيم العقد (= المناطق) إذا كانت تحتوي على الكثير من الأشياء في 4 عقود فرعية (المناطق الفرعية)

• اجمعها كلها العقد ورقة من Quadtree التي ضربتها الأشعة:

  حساب راي المستطيل تقاطع (غير صعبة) للجذر. إذا كان الجذر يضربه Ray، فانتقل إلى أطفاله بشكل متكرر.

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

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

هذا هو O (SQRT (N)).

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

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

Answer 2

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

Answer 3

ضع في اعتبارك أن الفرز هو عملية O (N تسجيل الدخول N) في أحسن الأحوال. قد تكون أفضل حالا فقط التحقق من كل فردي.

Answer 4

كيف حالك من المؤكد أنك ستضرب أي منها؟ إذا كانت خطوط، فمن غير المرجح.

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

ربما أسيء فهم ما تفعله بالفعل.

بشكل عام يتسارع التقاطعات ذات الأرقام المعقدة تتم مع التقسيم المكاني (ثم تقنيات مثل علبة البريد، إذا كانت اختباراتك مكلفة).

تحديث: أنا أسيء قراءة النية الأصلية] لا يزال بإمكانك استخدام التقسيم المكاني (2D) ولكن قد لا يستحق النفقات العامة. الاختبار الفردي رخيص، إذا لم تكن بولزك معقدة، فقد يكون من أرخص فقط امشي لهم. من الصعب القول من الوصف.

Answer 5

طلب التوضيح، هل هذا صحيح؟

• لديك مجموعة ديناميكية من قطاعات الخط ل.
• الاستعلام: معين أي النقطة (س، ص) و أي اتجاه الأشعة من هذه النقطة، تريد تحديد خط الأقرب في ل (لو اي) ؟

لذلك النقطة (X، Y) ليست إصلاح؟ (قد يكون أي نقطة، وأي اتجاه؟)