2D rectangle intersection search

2D rectangle intersection search deb, berilgan N ta to’g’ri to’rtburchaklar orasidan ustma-ust tushganlarini topishga aytiladi.

Mavzu avvalgi mavzularning davomi bo’lgani uchun, dastlab ular bilan tanishib chiqqan ma’qul:

Ustma-ust tushgan (kesishgan) to’g’ri to’rtburchaklarni topishning ikki xil usuli bor:

Brute-force algoritm – har bir chiziqdagi kesishmalarni tekshirib chiqadi. Ishlash vaqti – O(N²)
Sweep line algoritmi (nuqtalar o’rniga intervallar ishlatiladi)

Sweep line algoritmi (intervallar uchun)

Ishlash tartibi 2D line segment intersection‘ga o’xshash, ammo bu yerda biz koordinatalar o’rniga intervallarni tekshiramiz.

Dastlab biz minimum priority queue‘ga barcha to’g’ri to’rtburchaklarning chap va o’ng nuqtalari x-koordinatalarini yig’amiz.

Shuningdek, Interval search tree‘ga gorizontal to’g’ri to’rtburchaklarning vertikal (past va tepa) nuqtalari y-koordinatalarini interval ko’rinishida yig’amiz.

Algoritmning ishlash tartibi:

priority queue’dagi x-koordinatalarni ko’rib chiqishni boshlaymiz (o’sish tartibida)
Agar tekshirilayotgan nuqta gorizontal to’g’ri to’rtburchakning chap x nuqtasi bo’lsa, to’g’ri to’rtburchakning vertikal intervalini Interval search tree’ga qo’shamiz.
Agar tekshirilayotgan nuqta gorizontal to’g’ri to’rtburchakning o’ng x nuqtasi bo’lsa, to’g’ri to’rtburchakning vertikal intervalini interval search tree’dan o’chiramiz.
Agar tekshirilayotgan nuqta vertikal to’g’ri to’rtburchakka tegishli bo’lsa, demak to’g’ri to’rtburchaklar kesishgan bo’lishi mumkin. Vertikal to’g’ri to’rtburchakning vertikal intervallarini olib, interval search tree’da qidiruvni amalga oshiramiz. Qidiruv gorizontal to’g’ri to’rtburchaklar kesishgan barcha vertikal intervallarni topib beradi.

Sweep-line algoritmi (rectangles). Image credit: algs4.cs.princeton.edu

Masala

Quyida berilgan to’g’ri to’rtburchaklar kesishmalarini toping.
Masalani osonlashtirish uchun, faqat vertikal va kvadrat to’g’ri to’rtburchaklarni kesishganligiga tekshiramiz.

Kirish ma’lumotlari sifatida to’g’ri to’rtburchaklarning chap yuqori va o’ng pastki nuqtalari berilgan:

[
  [ [2,6],  [5,1]  ],
  [ [1,5],  [8,2]  ],
  [ [4,10], [13,7] ],
  [ [6,12], [7,0]  ],
  [ [9,6],  [17,3] ],
  [ [10,5], [14,1] ],
  [ [10,12],[16,8] ],
  [ [19,9], [22,5] ],
  [ [17,11],[18,7] ],
  [ [15,2], [24,0] ],
  [ [18,6], [23,3] ],
]

Berilgan rasmdan ko’rinib turibdiki, kesishmalar soni 6 ta. Lekin biz shartimizga ko’ra, faqat vertikal (yoki kvadrat) to’g’ri to’rtburchaklar kelganda ularning kesishmasini tekshiramiz. Ular 5ta.

Kod

Kod albatta Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sweep-line/rectangle-intersection-search.js

Masalani yechish davomida Interval search tree API’ga ham ba’zi foydali funksiyalar qo’shilgan. Interval search tree API bilan ham tanishib chiqish zarar qilmaydi.

* * *

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