Preseci horizontalnih i vertikalnih duži

Često se nailazi na probleme nalaženja preseka geometrijskih objekata. Nekad je potrebno pronaći preseke više objekata, a ponekad samo treba otkriti da li je presek neprazan skup. U nastavku ćemo prikazati jedan problem nalaženja preseka, koji ilustruje važnu tehniku za rešavanje geometrijskih problema. Ista tehnika može se primeniti i na druge slične probleme.

U prethodnom izlaganju fokus je bio na tome da se odredi presek duži koje se nalaze u opštem položaju. Videli smo da težina rešenja tog problema leži kako u matematičkom aparatu, tako u obradi velikog broja specijalnih slučajeva. U nastavku ćemo razmotriti problem u kom su duži uvek samo horizontalne i vertikalne, pa je za dve duži veoma jednostavno ispitati postojanje preseka, međutim, tih duži će biti puno i potrebno je upotrebiti geometrijske osobine (poredak koordinata) da bi se smanjio broj ispitivanja preseka.

Problem. Za zadati skup od \(n\) horizontalnih i \(m\) vertikalnih duži pronaći sve njihove preseke. Duži su zatvorene (sadrže i svoje krajnje tačke) i ne postoje međusobni preseci horizontalnih niti vertikalnih duži.

Ovaj problem važan je, na primer, pri projektovanju kola VLSI (integrisanih kola sa ogromnim brojem elemenata). Kolo može da sadrži na hiljade “žičica”, a projektant treba da bude siguran da ne postoje neočekivani preseci. Na problem se takođe nailazi pri eliminaciji skrivenih linija kada je potrebno zaključiti koje stranice ili delovi stranica su skriveni samim objektom ili nekim drugim objektom; taj problem je obično komplikovaniji, jer se ne radi samo o horizontalnim i vertikalnim linijama. Primer ulaza za ovaj problem prikazan je na slici 1.

Слика 1: Preseci horizontalnih i vertikalnih duži.

Ako pokušamo da problem rešimo dodavanjem jedne po jedne duži (bilo horizontalne, bilo vertikalne), onda će biti neophodno da se pronađu preseci nove duži sa svim ostalim dužima, pa se dobija algoritam sa \(O(mn)\) nalaženja preseka duži (što je zapravo algoritam grube sile). U opštem slučaju broj preseka može da bude \(O(mn)\), pa algoritam može da utroši vreme \(O(mn)\) već samo za prikazivanje svih preseka. Međutim, broj preseka može da bude mnogo manji od \(mn\). Voleli bismo da konstruišemo algoritam koji radi dobro kad ima malo preseka, a ne previše loše ako preseka ima mnogo. Dakle cilj nam je da problem rešimo korišćenjem algoritma čija složenost zavisi i od veličine ulaza i od veličine izlaza, tzv. algoritma sa izlazno zavisnom složenošću.

Redosled obrade duži može se odrediti brišućom pravom (engl. sweeping line) koja prelazi (“skenira”) ravan sleva udesno; duži se razmatraju onim redom kojim na njih nailazi pokretna (brišuća) prava. Značajni događaji (engl. events) su kada prava naiđe na neku karakterističnu tačku i algoritam se izvršava tako što se ti događaji redom obrađuju. Zamislimo vertikalnu pravu koja prelazi ravan sleva udesno i obradimo duži u redosledu u kojem prava nailazi na njih. Da bismo implementirali ovaj redosled, sortiramo sve krajeve duži prema njihovim \(x\)-koordinatama. Dve krajnje tačke vertikalne duži imaju iste \(x\)-koordinate, pa se registruje samo jedna \(x\)-koordinata. Za horizontalne duži moraju se koristiti oba kraja. Posle sortiranja krajeva, duži se razmatraju jedna po jedna utvrđenim redosledom.

Da li je bolje proveravati preseke kad se obrađuje horizontalna ili vertikalna duž? Kad posmatramo bilo levi, bilo desni kraj horizontalne duži, mi ili još nismo naišli na vertikalne duži koje je seku, ili smo ih već obradili. Dakle, bolje je preseke brojati prilikom nailaska na vertikalnu duž. Pretpostavimo da je pokretna prava trenutno preklopila vertikalnu duž \(L\) (videti sliku 1).

Brišuća prava (pa i vertikalne duži koje ona preklapa) se može seći samo sa onim horizontalnim dužima čiji se početak nalazi levo, a kraj desno od nje (pošto su duži zatvorene, u razmatranje treba uzeti i one duži čiji se levi ili desni kraj poklapa sa položajem brišuće prave ). Dakle, brišuća prava na poziciji \(x\) se može seći samo sa onim intervalima \([x_1, x_2]\) za koje važi da je \(x \in [x_1, x_2]\) tj. \(x_1 \leq x\) i \(x \leq x_2\). Stoga ćemo efikasniji algoritam dobiti ako primenimo odsecanje i iz razmatranja eliminišemo sve one horizontalne duži koje su se već “završile” (za koje je \(x_2 < x\)) i koje još nisu “počele” (za koje je \(x < x_1\)). Za horizontalne duži koje se još uvek razmatraju reći ćemo da su kandidati i podatke o njima ćemo čuvati u nekoj pogodnoj strukturi podataka. Na slici 1 ima četiri kandidata za presek sa \(L\).

U narednom apletu možete videti brišuću pravu \(L\) koja nailazi na duži i tom prilikom određuje njihove presečne tačke. Horizontalne duži koje seče prava \(L\) su obeležene crvenom, a vertikalne zelenom bojom. U trenutku kada prava naiđe na vertikalnu (zelenu duž), određuju se njeni preseci. Dovoljno je odrediti samo njene preseke sa crvenim dužima.

Kada se naiđe na vertikalnu duž \(L\), pretpostavićemo da znamo sve kandidate koje ona seče. Za nalaženje preseka sa \(L\), \(x\)-koordinate krajeva kandidata nisu od značaja, pa je dovoljno čuvati samo njihove \(y\)-koordinate. Naime, mi već znamo da kandidati imaju \(x\)-koordinate koje “pokrivaju” \(x\)-koordinatu vertikalne duži \(L\), pa je dovoljno proveriti da li su njihove \(y\)-koordiante obuhvaćene opsegom \(y\)-koordinata duži \(L\). Zato ćemo održavati strukturu podataka koja sadrži samo skup \(y\)-koordinata kandidata. Odložićemo za trenutak analizu realizacije ove strukture podataka.

Skup kandidata (tj. njihovih \(y\)-koordinata) možemo održavati induktivno: kada naiđemo na levi kraj horizontalne duži ona se dodaje u skup kandidata, a kada se naiđe na desni kraj duži, ona se izbacuje iz skupa kandidata.

Na početku je skup kandidata prazan i obrađujemo redom događaje (u sortiranom redosledu). Da bi se ispravno obradili granični slučajevi (kada se duži dodiruju u jednoj tački), pretpostavićemo da ćemo događaje sa istom \(x\)-koordinatom poređati tako da prvo idu levi krajevi horizontalnih duži, zatim vertikalne duži i na kraju desni krajevi horizontalnih duži. Na taj način postižemo da su prilikom obrade vertikalne duži u skup kandidata dodate sve duži koje počinju na njenoj \(x\)-koordinati, a još nisu uklonjene one duži koje se završavaju na toj \(x\)-koordinati.

Postoje tri mogućnosti tj. tri vrste događaja koje obrađujemo.

  1. Naišli smo na levi kraj horizontalne duži; duž se tada dodaje u skup kandidata. Pošto desni kraj duži nije dostignut, a duži su zatvorene, ona sadrži tekuću \(x\)-koordinatu i zaista treba da bude deo skupa kandidata.

  2. Naišli smo na vertikalnu duž na koordinati \(x\). Preseci sa ovom vertikalnom duži mogu se pronaći upoređivanjem \(y\)-koordinata svih horizontalnih duži iz skupa kandidata sa \(y\)-koordinatama krajeva vertikalne duži. U skupu kandidata se nalaze sve one duži koje su započele na koordinatama manjim ili jednakim \(x\), a nisu se završile na koordinatama koje su strogo manje od \(x\), pa skup kandidata zaista sadrži tačno one horizontalne duži koje sadrže koordinatu \(x\).

  3. Naišli smo na desni kraj horizontalne duži; duž se tada prosto eliminiše iz skupa kandidata. Kao što je rečeno, preseci se pronalaze pri razmatranju vertikalnih duži, a u ovom trenutku su obrađene sve vertikalne duži čija je \(x\)-koordinata manja ili jednaka tekućoj \(x\)-koordinati, pa se ni jedan od preseka ne gubi eliminacijom ove horizontalne duži (ona ne može biti više kandidat za neki budući presek).

Algoritam je sada kompletan. Broj upoređivanja će obično biti mnogo manji od \(mn\), međutim, u najgorem slučaju ovaj algoritam ipak zahteva \(O(mn)\) upoređivanja, čak i kad je broj preseka mali. Ako se, na primer, sve horizontalne duži prostiru sleva udesno (“celom širinom”), onda se mora proveriti presek svake vertikalne duži sa svim horizontalnim dužima, što implicira složenost \(O(mn)\). Ovaj najgori slučaj pojavljuje se čak i ako nijedna vertikalna duž ne seče nijednu horizontalnu duž (videti primer na slici 2).

Слика 2: Slučaj kada nema preseka duži, a broj poređenja u okviru osnovnog algoritma je O(mn).

Da bi se algoritam usavršio, potrebno je smanjiti broj upoređivanja \(y\)-koordinata vertikalne duži sa \(y\)-koordinatama horizontalnih duži u skupu kandidata. Iako je polazni problem dvodimenzionalan, nalaženje tih preseka je jednodimenzionalni problem. Neka su \(y\)-koordinate vertikalne duži koja se trenutno razmatra \(y_D\) i \(y_G\), i neka su \(y\)-koordinate horizontalnih duži iz skupa kandidata \(y_0,y_1,\ldots,y_{r-1}\). Ako pretpostavimo da su horizontalne duži u skupu kandidata sortirane prema \(y\)-koordinatama (odnosno niz \(y_0,y_1,\ldots,y_{r-1}\) je rastući), preseci se mogu pronaći izvođenjem dve binarne pretrage, jedne za \(y_D\), a druge za \(y_G\). Neka je \(y_i<y_D\le y_{i+1}\le y_j \le y_G <y_{j+1}\). Vertikalnu duž seku horizontalne duži sa koordinatama \(y_{i+1}, y_{i+2},\ldots, y_{j}\), i samo one, pa je njihov broj \(j - i\). Ako je potrebno da se navedu svi preseci, tada se može izvršiti jedna binarna pretraga za \(y_D\), a zatim prolaziti \(y\)-koordinate, dok se ne dođe do vrednosti \(y_{j+1}\) veće od \(y_G\). Ako su brojevi sortirani, onda je vreme izvršenja proporcionalno zbiru vremena traženja prvog preseka i broja pronađenih preseka. Naravno, ne možemo da priuštimo sebi sortiranje horizontalnih duži pri svakom nailasku na vertikalnu duž, već je potrebno da duži čuvamo u nekoj pogodnoj strukturi podataka.

Prisetimo se još jednom zahteva. Potrebna je struktura podataka pogodna za čuvanje kandidata, koja dozvoljava umetanje novog elementa, brisanje elementa i efikasno izvršenje binarne pretrage (tj. nalaženje prvog elementa strogo većeg ili većeg ili jednakog od date vrednosti). Na sreću, postoji više struktura podataka koje omogućuju izvršenje umetanja, brisanja i traženja elemenata složenosti \(O(\log n)\) po operaciji (gde je \(n\) broj elemenata u strukturi podataka), i linearno pretraživanje za vreme proporcionalno broju pronađenih elemenata — na primer, uređen skup implementiran pomoću uravnoteženog binarnog drveta koji je dostupan u standardnoj biblioteci većine savremeniih programskih jezika (u jeziku C++ to je struktura podataka set).

Implementaciju u jeziku C++ možemo napraviti na sledeći način.

// duz predstavljena koordinatama dve krajnje tacke
struct Duz {
  int x1, y1, x2, y2;

  Duz(int _x1, int _y1, int _x2, int _y2) {
    x1 = _x1; y1 = _y1;
    x2 = _x2; y2 = _y2;
  }

  // provera da li je duz horizontalna
  bool horizontalna() const {
    return y1 == y2;
  }
};

// ucitavamo podatke o n duzi (horizontalnih i vertikalnih)
int n;
cin >> n;
vector<Duz> duzi;
for (int i = 0; i < n; i++) {
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  duzi.emplace_back(x1, y1, x2, y2);
}

// brisuca prava obilazi duzi u neopadajucem redosledu x koordinata
// znacajni dogadjaji su kada brisuca prava naidje na levi kraj horizontalne
// duzi, desni kraj horizontalne duzi ili na vertikalnu duz
enum TipDogadjaja {LEVI_KRAJ, VERTIKALNA, DESNI_KRAJ};
// za svaki dogadaj pamtimo 
struct Dogadjaj {
  int x;
  Duz duz;
  TipDogadjaja tip;

  Dogadjaj(int _x, const Duz& _duz, TipDogadjaja _tip)
    : x(_x), duz(_duz), tip(_tip) {
  }

  // dogadjaji se porede po x-koordinatama
  // dogadaje koji imaju istu x-koordinatu poredimo po tipu
  // (prvo idu levi krajevi, pa vertikalne duzi, pa desni krajevi)
  bool operator<(const Dogadjaj& d) {
    return x < d.x || (x == d.x && tip < d.tip);
  }
};

// popisujemo sve dogadjaje i sortiramo ih
vector<Dogadjaj> dogadjaji;
for (const Duz& duz : duzi) {
  if (duz.horizontalna()) {
    dogadjaji.emplace_back(duz.x1, duz, LEVI_KRAJ);
    dogadjaji.emplace_back(duz.x2, duz, DESNI_KRAJ);
  } else
    dogadjaji.emplace_back(duz.x1, duz, VERTIKALNA);
}
sort(begin(dogadjaji), end(dogadjaji));

// skup y koordinata horizontalnih duzi koje su aktivne
// (brisuca prava je presla njihov levi, ali ne i desni kraj)
set<int> yAktivnihHorizontalnih;

// obradjujemo sve dogadjaje
for (const Dogadjaj& dogadjaj : dogadjaji) {
  if (dogadjaj.tip == LEVI_KRAJ) {
    // brisuca prava je dosla do levog kraja horizontalne duzi, pa ona
    // postaje aktivna
    yAktivnihHorizontalnih.insert(dogadjaj.duz.y1);
  } else if (dogadjaj.tip == DESNI_KRAJ) {
    // brisuca prava je dosla do desnog kraja vertikalne duzi, pa ona
    // prestaje da bude aktivna
    yAktivnihHorizontalnih.erase(dogadjaj.duz.y1);
  } else {
    // brisuca prava je dosla do vertikalne duzi
    // ispisujemo sve preseke sa aktivnim horizontalnim duzima
      
    // najniza horizontalna duz koja je iznad donjeg temena
    // vertikalne duzi
    auto start = yAktivnihHorizontalnih.lower_bound(dogadjaj.duz.y1);

    // najniza horizontalna duz koja je strogo iznad gornjeg temena
    // vertikalne duzi
    auto end = yAktivnihHorizontalnih.upper_bound(dogadjaj.duz.y2);

    // sve duzi izmedju njih se seku
    for (auto it = start; it != end; it++)
      cout << dogadjaj.duz.x1 << " " << *it << endl;
  }
}
# include <iostream> {.unnumbered .unlisted}
# include <vector> {.unnumbered .unlisted}
# include <set> {.unnumbered .unlisted}
# include <algorithm> {.unnumbered .unlisted}

using namespace std;

int main() {
  // duz predstavljena koordinatama dve krajnje tacke
  struct Duz {
    int x1, y1, x2, y2;

    Duz(int _x1, int _y1, int _x2, int _y2) {
      x1 = _x1; y1 = _y1;
      x2 = _x2; y2 = _y2;
    }

    // provera da li je duz horizontalna
    bool horizontalna() const {
      return y1 == y2;
    }
  };

  // ucitavamo podatke o n duzi (horizontalnih i vertikalnih)
  int n;
  cin >> n;
  vector<Duz> duzi;
  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    duzi.emplace_back(x1, y1, x2, y2);
  }

  // brisuca prava obilazi duzi u neopadajucem redosledu x koordinata
  // znacajni dogadjaji su kada brisuca prava naidje na levi kraj horizontalne
  // duzi, desni kraj horizontalne duzi ili na vertikalnu duz
  enum TipDogadjaja {LEVI_KRAJ, VERTIKALNA, DESNI_KRAJ};
  // za svaki dogadaj pamtimo 
  struct Dogadjaj {
    int x;
    Duz duz;
    TipDogadjaja tip;

    Dogadjaj(int _x, const Duz& _duz, TipDogadjaja _tip)
      : x(_x), duz(_duz), tip(_tip) {
    }

    // dogadjaji se porede po x-koordinatama
    // dogadaje koji imaju istu x-koordinatu poredimo po tipu
    // (prvo idu levi krajevi, pa vertikalne duzi, pa desni krajevi)
    bool operator<(const Dogadjaj& d) {
      return x < d.x || (x == d.x && tip < d.tip);
    }
  };

  // popisujemo sve dogadjaje i sortiramo ih
  vector<Dogadjaj> dogadjaji;
  for (const Duz& duz : duzi) {
    if (duz.horizontalna()) {
      dogadjaji.emplace_back(duz.x1, duz, LEVI_KRAJ);
      dogadjaji.emplace_back(duz.x2, duz, DESNI_KRAJ);
    } else
      dogadjaji.emplace_back(duz.x1, duz, VERTIKALNA);
  }
  sort(begin(dogadjaji), end(dogadjaji));

  // skup y koordinata horizontalnih duzi koje su aktivne
  // (brisuca prava je presla njihov levi, ali ne i desni kraj)
  set<int> yAktivnihHorizontalnih;

  // obradjujemo sve dogadjaje
  for (const Dogadjaj& dogadjaj : dogadjaji) {
    if (dogadjaj.tip == LEVI_KRAJ) {
      // brisuca prava je dosla do levog kraja horizontalne duzi, pa ona
      // postaje aktivna
      yAktivnihHorizontalnih.insert(dogadjaj.duz.y1);
    } else if (dogadjaj.tip == DESNI_KRAJ) {
      // brisuca prava je dosla do desnog kraja vertikalne duzi, pa ona
      // prestaje da bude aktivna
      yAktivnihHorizontalnih.erase(dogadjaj.duz.y1);
    } else {
      // brisuca prava je dosla do vertikalne duzi
      // ispisujemo sve preseke sa aktivnim horizontalnim duzima
      
      // najniza horizontalna duz koja je iznad donjeg temena
      // vertikalne duzi
      auto start = yAktivnihHorizontalnih.lower_bound(dogadjaj.duz.y1);

      // najniza horizontalna duz koja je strogo iznad gornjeg temena
      // vertikalne duzi
      auto end = yAktivnihHorizontalnih.upper_bound(dogadjaj.duz.y2);

      // sve duzi izmedju njih se seku
      for (auto it = start; it != end; it++)
        cout << dogadjaj.duz.x1 << " " << *it << endl;
    }
  }
  
  return 0;
}

Kao što je već rečeno, uopštenje ovog algoritma na proizvoljni skup duži poznato je kao Bentli-Otmanov algoritam. U tom algoritmu, pored početaka i krajeva duži, značajan događaj je i kada vertikalna prava naiđe na presek dve duži. U uređenom drvetu se čuvaju duži sortirane po visini. Prava može naići isključivo na presek dve susedne duži i nakon što prođe presek, njihov međusobni redosled se menja. Pošto niz događaja više nije statički (ne može se u startu odrediti, jer su događaji i preseci duži koji se određuju tokom rada algoritma), događaji se ne čuvaju u sortiranom nizu, već u redu sa prioritetom. Detaljni opis i implementacija ovog algoritma neće biti data u ovom udžbeniku.

<<Prethodno
>>Sledeće