خوارزمية البحث عن المقاطع المتداخلة الخط

Question

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

في الفن ASCII أعلاه، هناك أربعة المضلعات (P1، P2، P3، P4) مع شرائح خط متداخلة تماما. على سبيل المثال، P2 المضلع (التي شكلتها شرائح الخط الفاصل بين العقد N3، 10، 9، 12، 15، 14، 13، 8، 7، 6، و 2) وP1 (N1، 2، 5، و 6) التداخل في شريحة الخط الفاصل بين N2 و N6.

ما هي أسرع طريقة للعثور على أجزاء الخط التي تتداخل بالضبط؟

Answer 1

إذا كل شكل لائحة من حواف ثم:

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

O لها (حواف)، والخاص لن نفعل ما هو أفضل من ذلك. هذا الحل قد لا يكون مرضيا اعتمادا على ما تريد القيام به على الرغم وجه التحديد.

Answer 2

وشرائح ونظرا خط N، في أسوأ الحالات يمكن أن يكون هناك O (ن ^ 2) التقاطعات. مجرد التفكير في الحالة التي يكون فيها لديك N المضلعات حيث يشارك كل مضلع نفس الحافة. ما لم يكن هناك عقبة إضافية لمنع هذه الحالة من الحدوث (أنك أغفلت إضافة) ثم أفضل خوارزمية يمكنك الخروج مع ستكون O (N ^ 2) في أسوأ الأحوال، لأن مجرد سرد التقاطعات هي O (N ^ 2).

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

ويمكن أن تجد وصفا لازالت الخوارزمية التي تحتاج إليها في <لأ href = "http://books.google.ca/books؟id=NLngYyWFl_YC&dq=cormen+intro+to+algo&printsec=frontcover&source=bn&hl=en&ei= 5COvSs6ACoj2sQPFupTNCw وسا = X & منظمة اوكسفام الدولية = book_result وط = يؤدي وresnum = 4 # ت = onepage وف = & F = كاذبة "يختلط =" نوفولو noreferrer "> مقدمة إلى الخوارزميات التي كتبها توماس H Cormen في القسم الخاص الهندسة الحسابية.

Answer 3

وخوارزمية twolfe18 لتبدو جيدة. قد تكون هناك مضاعفات وأضاف، ومع ذلك، إذا لم يتم وصفها حواف مطابقة مماثل. في المثال الخاص بك، P1 و P2 على حد سواء حصة حافة N2-N6. ولكن حافة P2 ويمكن وصفه من قبل قطاع N2-N7 بدلا من ذلك (إذا N2-N6 وN6، N7 هم colinear). بعد ذلك سيكون عليك طريقة التجزئة أكثر تعقيدا لتحديد ما إذا تتداخل الحدين. يمكنك معرفة ما إذا كان اثنين من حواف تتداخل قبل شرائح رسم الخرائط على خطوط، وتبحث حتى سطر في جدول هاش، ثم اختبار ما إذا جزأين على خط تتقاطع باستخدام شجرة الفاصلة في الفضاء المعلمة على الخط.