2D line segment intersection. Sweep line algoritmi

Masala. N ta gorizontal va vertikal chiziqlar berilgan. Chiziqlarning kesishgan nuqtalarini topish kerak. Har bir chiziqning chap va o’ng – boshlanish va tugash nuqtalari ma’lum.

Nuqtalar quyidagicha ko’rinishda ifodalangan:

[
  [ [1,2], [5,2] ], 
  [ [2,4], [2,8] ], 
  [ [3,1], [9,1] ],
  [ [4,4], [6,4] ],
  [ [5,3], [5,6] ],
  [ [8,0], [8,3] ],
  [ [9,3], [9,6] ]
]

Ushbu masalani yechish usullari ikkita:

Brute-force algoritmi har bir juft koordinatani tekshirib chiqadi. Ishlash vaqti O(N²).
Sweep line algoritmi.

Sweep line algoritmi

Dastlab biz gorizontal chiziqlarning boshlanish va tugash nuqtalari hamda vertikal chiziqlarning x nuqtalari uchun minimum priority queue‘ni ishlatamiz.

Keyin Y koordinatalarni binary search tree‘ga yig’amiz.

Ishlash tartibi:

x-koordinatalarni o’sish tartibida priority queue’ga yig’amiz
Agar x-koordinata gorizontal chiziqning boshlanish nuqtasi bo’lsa, nuqtaning y-koordinatasini binary search tree’ga qo’shamiz
Agar x-koordinata gorizontal chiziqning tugash nuqtasi bo’lsa, nuqtaning y-koordinatasini binary search tree’dan o’chiramiz.
Agar nuqta vertikal chiziqqa tegishli bo’lsa, kesishuv bo’lishi mumkin. Chiziqning tepa va pastki Y-koordinatalarini olib binary search tree ustida range search amalini bajaramiz. Range search gorizontal liniyani kesgan barcha nuqtalarni topib beradi.

Tahlil

Barcha kesishuvlarni topish uchun ishlash vaqti – O(R + N log N). R – barcha kesishuvlar soni, N – chiziqlar soni.

x-koordinatalarni priority queue’ga yig’ish -> O(N log N)
y-koordinatalarni binary search tree’ga yig’ish -> O(N log N)
y-koordinatalarni binary search tree’dan o’chirish -> O(N log N)
binary search tree’da range search – O(R + N log N)

Xulosa. Sweep line algoritmi 2D chiziqlar kesishuvi uchun 1D oraliq qidiruvni qo’llash imkonini beradi.

Kod

Kodda ifodalash uchun Binary Search tree’dan foydalanmadim, sababi baribir intervyu vaqtida binary search tree API dan foydalanish imkoni bo’lmaydi. Shu sababli kod yuqoridagi algoritmdan biroz farq qiladi.

UPDATE: Quyidagi kodda Array.some() hisobiga worst case O(N²) bo’lib ketadi. Ya’ni quyidagi kod Brute-force metodiga yaqinroq. Quyida tree orqali ishlangan variantining linki ham mavjud.

* * *

Kod Githubda:

Brute-force: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sweep-line/sweep-line.js

Sweep line: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sweep-line/line-segment-intersection.js

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.