مسند القرب الهندسي السريع

Question

لدي 3 نقاط (A وB وX) ومسافة (د).أحتاج إلى إنشاء دالة تختبر ما إذا كانت النقطة X أقرب من المسافة d إلى أي نقطة على القطعة المستقيمة AB.

السؤال هو أولاً هل الحل الذي قدمته صحيح ومن ثم التوصل إلى حل أفضل (أسرع).

تمريرتي الأولى هي على النحو التالي

AX = X-A
BX = X-B
AB = A-B

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag)
If d^2 > AX.mag^2  return true

    // closer than d to B
If d^2 > BX.mag^2 return true

    // "beyond"  B
If (dot(BX,AB) < 0) return false

    // "beyond"  A
If (dot(AX,AB) > 0) return false

    // find component of BX perpendicular to AB
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2

سيتم تشغيل هذا الرمز في نهاية المطاف لمجموعة كبيرة من P's ومجموعة كبيرة من A/B/d الثلاثية بهدف العثور على جميع P التي تمر لـ A/B/d واحد على الأقل لذا أظن أن هناك طريقة لتقليل التكلفة الإجمالية بناءً على ذلك ولكني لم أبحث في ذلك بعد.

(بالمناسبة:أدرك أن بعض عمليات إعادة الترتيب وبعض القيم المؤقتة وبعض الهويات الجبرية يمكن أن تقلل من تكلفة ما سبق.لقد حذفتها فقط من أجل الوضوح.)

---

يحرر:هذه مشكلة ثنائية الأبعاد (لكن الحل الذي يتم تعميمه على الأبعاد الثلاثية سيكون رائعًا

يحرر:وبعد مزيد من التفكير، أتوقع أن يصل معدل النجاح إلى حوالي 50%.يمكن تشكيل النقطة X في تسلسل هرمي متداخل، لذا أتوقع أن أكون قادرًا على تقليم الأشجار الفرعية الكبيرة كنجاح كامل وفشل كامل.سيكون تحديد A/B/d للتوائم الثلاثة بمثابة خدعة أكبر.

يحرر:d بنفس حجم AB.

---

يحرر:نشر Artelius حلاً لطيفًا.لست متأكدًا من أنني أفهم بالضبط ما يريده عندما خرجت من الظل قبل أن أفهمه تمامًا.على أية حال خطرت في بالي فكرة أخرى نتيجة لذلك:

• أولاً، قم بتجميع مصفوفة مسبقًا من شأنها أن تضع AB في مركز الأصل ومحاذاة مع المحور السيني.(2 إضافة، 4 نقاط، 2 إضافة)
• أضعاف كل شيء في الربع الأول (2 القيمة المطلقة)
• مقياس في X&Y لتحويل الجزء المركزي من المنطقة إلى مربع وحدة (2 مول)
• اختبار ما إذا كانت النقطة في هذا المربع (اختبار 2) يتم إنهاء ذلك
• اختبر الحد الأقصى (ارجع إلى القيم غير المقاسة
  • ترجمة في x لوضع النهاية في الأصل (إضافة واحدة)
  • مربع وإضافة (2 مول، 1 إضافة)
  • قارن بـ d^2 (1 سم)

أنا متأكد تمامًا من أن هذا يتفوق على الحل الخاص بي.

(إذا لم يأتي أي شيء أفضل، فسيحصل أرتيليوس على "الجائزة" :)

Answer 1

إذا كانت مجموعتك من (A، B، d) ثابتة، فيمكنك حساب زوج من المصفوفات لكل منها لترجمة النظام الإحداثي، بحيث يصبح الخط AB هو المحور X، ونقطة منتصف AB هي الأصل.

أنا يفكر هذه طريقة بسيطة لبناء المصفوفات:

trans = - ((A + B) / 2)        // translate midpoint of AB to origin

rot.col1 = AB / AB.mag         // unit vector in AB direction

                        0 -1    
rot.col2 = rot.col1 * (      ) // unit vector perp to AB
                        1  0 

rot = rot.inverse()            // but it needs to be done in reverse

ثم تأخذ كل X وتفعلها rot * (X + trans).

المنطقة المعنية هي في الواقع متناظرة في كل من المحورين x وy الآن، لذا يمكنك حساب القيمة المطلقة للإحداثي x والإحداثي y.

ثم تحتاج فقط إلى التحقق:

y < d && x < AB.mag/2            //"along" the line segment
|| (x - AB.mag/2)^2 + y^2 < d^2  // the "end cap".

يمكنك القيام بخدعة أخرى؛يمكن تقليص المصفوفة بعامل AB.mag/2 (تذكر أن المصفوفات يتم حسابها مرة واحدة فقط لكل (أ، ب) مما يعني أنه من الأفضل أن يكون العثور عليها أبطأ من التحقق الفعلي نفسه).وهذا يعني أن الشيك الخاص بك يصبح:

y < 2*d/AB.mag && x < 1
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2

بعد استبدال حالتين من AB.mag/2 بالثابت 1، قد يكون الأمر أسرع بلمسة واحدة.وبالطبع يمكنك إجراء حساب مسبق 2*d/AB.mag و (2*d/AB.mag)^2 أيضًا.

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

Answer 2

هممممممم ....ما هو معدل الإصابة؟كم مرة تلبي النقطة "X" متطلبات القرب؟

أعتقد أن الخوارزمية الحالية لديك جيدة، وأي تحسينات إضافية ستأتي من ضبط البيانات الحقيقية.على سبيل المثال، إذا كانت النقطة "X" تستوفي اختبار القرب بنسبة 99% من الوقت، فأعتقد أن استراتيجية التحسين الخاصة بك يجب أن تكون مختلفة تمامًا عما إذا نجحت في الاختبار بنسبة 1% فقط من الوقت.

---

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

مشكلتك أكثر تعقيدًا قليلاً من أقرب جار أساسي (لأنك تتحقق من القرب من مقطع خط بدلاً من مجرد القرب من نقطة ما) ولكني ما زلت أعتقد أن KDTree سيكون مفيدًا.

Answer 3

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

في هذه الحالة لديك كرة في الموقع X نصف قطرها d، وتحاول معرفة ما إذا كان الخط AB يتقاطع مع الكرة.الاختلاف الوحيد في تتبع الشعاع هو أنه في هذه الحالة يكون لديك خط محدد AB، بينما في تتبع الشعاع يتم تعميم الشعاع عادةً كما يلي: origin + distance * direction, ، ولا يهمك مدى طول الخط اللانهائي AB+ إنها.

في كود زائف من جهاز تتبع الشعاع الخاص بي (استنادًا إلى الخوارزمية الواردة في "مقدمة لتتبع الشعاع" (ed.جلاسنر):

Vector v = X - A
Vector d = normalise(B - A)  // unit direction vector of AB
double b = dot(v, B - A)
double discrim = b^2 - dot(v, v) + d^2
if (discrim < 0)
     return false            // definitely no intersection

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

discrim = sqrt(discrim)
double t2 = b + discrim
if (t2 <= 0)
    return false             // intersection is before A

double t1 = b  - discrim

result = (t1 < length(AB) || (t2 < length(AB))

Answer 4

سيتم تشغيل هذا الرمز في نهاية المطاف لمجموعة كبيرة من P's ومجموعة كبيرة من A/B/d الثلاثية بهدف العثور على جميع P التي تمر لـ A/B/d واحد على الأقل لذا أظن أن هناك طريقة لتقليل التكلفة الإجمالية بناءً على ذلك ولكني لم أبحث في ذلك بعد.

في حالة d ~ AB، بالنسبة لنقطة معينة X، يمكنك أولاً اختبار ما إذا كانت X تنتمي إلى واحدة من المجالات العديدة لنصف القطر d والمركز Ai أو Bi.انظر الى الصورة:

     ......        .....
  ...........   ...........
 ...........................
.......A-------------B.......
 ...........................
  ...........   ...........
     .....         .....

أول اختبارين

If d^2 > AX.mag^2 return true
If d^2 > BX.mag^2 return true

هم الأسرع، وإذا كان d ~ AB هم أيضًا الأكثر احتمالية للنجاح (نظرًا لنجاح الاختبار على الإطلاق).بالنظر إلى X، يمكنك إجراء جميع "اختبارات المجال" أولاً، ثم جميع الاختبارات النهائية:

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 

Answer 5

إذا كان عدد مجموعات A/B/d كبيرًا، وكنت بالتأكيد في وضع ثنائي الأبعاد، ففكر في استخدامه أشجار R (أو ما يعادلها مثمنة) حيث يكون كل إدخال في شجرة R هو الحد الأدنى للمربع المحيط بالثلاثية A/B/d.سيتيح لك ذلك التخلص من الاضطرار إلى اختبار الكثير من ثلاثية A/B/d وتركيز طاقة وحدة المعالجة المركزية الخاصة بك فقط على النقاط القليلة حيث تكون كل نقطة X داخل المربعات المحيطة بثلاثية A/B/d.ثم قم بإجراء اختبار أكثر تفصيلاً مثل الذي ذكرته.