10.2 Mnogouglovi

Objekti koji se najčešće razmatraju u računarskoj geometriji su tačke, prave i duži i mnogouglovi. Prilikom računarske obrade svi objekti se predstavljaju analitički.

• Prava je najčešće predstavljena parom različitih tačaka \(P\) i \(Q\) koje joj pripadaju.

• Duž se najčešće zadaje parom tačaka \(P\) i \(Q\) koje predstavljaju krajeve te duži, i označavaćemo je sa \(PQ\).

• Put \(P\) je niz tačaka \(P_1\), \(P_2,\ldots,P_k\) i duži \(P_1P_2\), \(P_2P_3,\ldots,P_{k-1}P_k\) koje ih povezuju. Duži koje čine put su njegove stranice (ivice). Primetimo da je u opštem slučaju dopušteno da tačke na putu budu i kolinearne.

• Zatvoreni put je put čija se poslednja tačka poklapa sa prvom i nazivamo ga mnogougao ili poligon. Tačke koje definišu mnogougao su njegova temena.

  Na primer, trougao je mnogougao sa tri temena. Mnogougao se predstavlja nizom, a ne skupom tačaka, jer je bitan redosled kojim se tačke zadaju; promenom redosleda tačaka iz istog skupa u opštem slučaju dobija se drugi mnogougao.

• Prost mnogougao je onaj kod koga odgovarajući put nema preseka sa samim sobom; drugim rečima, jedine stranice koje imaju zajedničke tačke su susedne stranice sa svojim zajedničkim temenom. Prost mnogougao deli ravan na dve oblasti: unutrašnjost i spoljašnost. Na slici 1 prikazan je jedan prost mnogougao, dok je na slici 2 prikazan jedan mnogougao koji nije prost (tj. mnogougao koji je samopresecajući).

  

  

  Ako ne postoji mogućnost zabune, nekada se termin mnogougao može upotrebiti i da označi mnogougaonu površ tj. skup tačaka unutrašnjosti mnogougla. Ako je mnogougao zatvoren smatra se da mu pored tačaka u unutrašnjosti pripadaju i tačke na stranicama.

• Konveksni mnogougao je mnogougao čija unutrašnjost sa svake dve tačke koje sadrži, sadrži i sve tačke duži koje te tačke određuju (ekvivalentno, mnogougao je konveksan ako su mu svi unutrašnji uglovi manji ili jednaki \(180^\circ\) tj. \(\pi\) radijana). Konveksni put je put sastavljen od tačaka \(P_1\), \(P_2,\ldots,P_k\) takav da je mnogougao \(P_1P_2\ldots P_k\) konveksan. Mnogougao na slici 1 je konveksan, dok je mnogougao na slici 3 nekonveksan.

  

10.2.1 Konstrukcija prostog mnogougla

Skup tačaka u ravni definiše veći broj različitih mnogouglova, zavisno od izabranog redosleda tačaka. Razmotrićemo sada pronalaženje prostog mnogougla sa zadatim skupom temena.

Postoji više metoda za konstrukciju traženog prostog mnogougla; uostalom, jasno je da u opštem slučaju problem nema jednoznačno rešenje (slika 4).

Prirodna ideja je da se tačke obilaze nekako u krug. Neka je \(C\) neki krug sa centrom u tački \(O\), čija unutrašnjost sadrži sve tačke. Površina \(C\) može se “prebrisati” (pregledati) rotirajućom polupravom kojoj je početak centar kruga \(C\) i tačke se mogu povezati u mnogougao u redosledu u kojem poluprava na njih nailazi.

Očekujemo da ćemo spajanjem tačaka onim redom kojim poluprava nailazi na njih dobiti prost mnogougao. Pokušajmo da to dokažemo. Pretpostavimo za trenutak da rotirajuća poluprava u svakom trenutku sadrži najviše jednu tačku. Označimo tačke, uređene u skladu sa redosledom nailaska poluprave na njih, sa \(P_1,P_2,\ldots,P_n\) (prva tačka bira se proizvoljno). Poluprave koje spajaju tačku \(O\) sa ovim tačkama dele krug na \(n\) međusobno disjunktnih kružnih isečaka. Temena svake duži \(P_iP_{i+1}\) pripadaju ivicama tih isečaka. Ako su svi isečci konveksni (ako im je centralni ugao manji od \(\pi\)), tada je to što temena duži \(P_iP_{i+1}\) pripadaju isečku dovoljno da bi moglo da se garantuje da cela duž pripada tom isečku. Dakle, ako bi svi isečci bili konveksni, dobijeni mnogougao bi morao da bude prost (što je i slučaj na slici 5).

Primetimo, međutim, da ugao između polupravih kroz neke dve uzastopne tačke \(P_i\) i \(P_{i+1}\) može da bude veći od \(\pi\). Tada isečak koji sadrži duž \(P_iP_{i+1}\) sadrži više od pola kruga i nije konveksna figura, a duž \(P_iP_{i+1}\) ne pripada tom isečku, već prolazi kroz druge isečke kruga, pa može da seče druge stranice mnogougla.

Da bi se uočeni problem rešio, krug je potrebno odabrati tako da ne postoji prava koja prolazi kroz centar tako da se sve tačke nalaze sa iste strane te prave. Jedna prirodna ideja je da se tačka bira tako bude “na sredini” datog skupa tačaka. Mogu se, na primer, fiksirati proizvoljne tri tačke iz skupa, a za centar kruga izabrati neka tačka \(O\) unutar njima određenog trougla (na primer težište, koje se lako izračunava). Ovakav izbor garantuje da ni jedan od dobijenih sektora kruga neće imati ugao veći od \(\pi\).

Tačke sortiramo prema položaju u krugu sa centrom \(O\). Preciznije, tačke \(P_i\) se sortiraju na osnovu veličine ugla između \(x\)-ose i poluprave \(OP_i\). Ako dve ili više tačaka imaju isti ugao, one se dalje sortiraju rastuće (ili opadajuće) prema rastojanju od tačke \(O\). Na kraju, tačke povezujemo u skladu sa dobijenim uređenjem, po dve uzastopne. Osnovna komponenta vremenske složenosti ovog algoritma potiče od sortiranja tačaka, te je složenost algoritma \(O(n\log n)\).

Ugao \(\phi\) koji prava \(OP_i\) zahvata sa \(x\) osom jednak je vrednosti \(\mathrm{atan2}(P_{iy} - O_y, P_{ix} - O_x)\). Primetimo i da kad dve tačke imaju isti nagib nije neophodno računati njihova rastojanja od tačke \(O\) – dovoljno je izračunati kvadrate rastojanja. Dakle, nema potrebe za izračunavanjem kvadratnih korenova.

Prethodni algoritam se može implementirati na sledeći način:

double ugao(double x0, double y0, double x, double y) {
  // ako su tacke t0=(x0, y0) i t=(x, y) racunamo
  // ugao koji vektor t0t zaklapa sa negativnim smerom x ose
  return atan2(y - y0, x - x0);
}

bool kolinearne(const Tacka& t1, const Tacka& t2, const Tacka& t3) {
  return abs(ugao(t1.x, t1.y, t2.x, t2.y) - ugao(t1.x, t1.y, t3.x, t3.y)) < EPS;
}

void prostMnogougao(vector<Tacka>& tacke) {
  // pronalazimo centar kruga kao teziste neke 3 nekolinearne tacke
  int i = 2;
  while (kolinearne(tacke[0], tacke[1], tacke[i]))
    i++;
  double x0 = (tacke[0].x + tacke[1].x + tacke[i].x) / 3.0;
  double y0 = (tacke[0].y + tacke[1].y + tacke[i].y) / 3.0;

  // sortiramo tacke na osnovu ugla
  sort(begin(tacke), end(tacke),
       [x0, y0](const Tacka& t1, const Tacka& t2) {
         // ugao koji vektor t0t1 zaklapa sa negativnim smerom x ose
         double ugao1 = ugao(x0, y0, t1.x, t1.y);
         // ugao koji vektor t0t2 zaklapa sa negativnim smerom x ose
         double ugao2 = ugao(x0, y0, t2.x, t2.y);

         if (ugao1 < ugao2 - EPS)
           return true;
         
         if (ugao2 < ugao1 - EPS)
           return false;

         // razlika uglova je u intervalu [-EPS, EPS] pa tacke smatramo kolinearnim
         return kvadratRastojanja(x0, y0, t1.x, t1.y) <
                kvadratRastojanja(x0, y0, t2.x, t2.y);
       });
  // obrcemo redosled tacaka na poslednjoj pravoj
  auto it = prev(end(tacke));
  while (kolinearne(*prev(it), *it, tacke[0]))
    it = prev(it);
  reverse(it, end(tacke));
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
};

// ako je razlika uglova u intervalu [-EPS, EPS] smatraćemo da su
// tacke kolinearne
const double EPS = 1e-12;

double ugao(double x0, double y0, double x, double y) {
  // ako su tacke t0=(x0, y0) i t=(x, y) racunamo
  // ugao koji vektor t0t zaklapa sa negativnim smerom x ose
  return atan2(y - y0, x - x0);
}

bool kolinearne(const Tacka& t1, const Tacka& t2, const Tacka& t3) {
  return abs(ugao(t1.x, t1.y, t2.x, t2.y) - ugao(t1.x, t1.y, t3.x, t3.y)) < EPS;
}

double kvadratRastojanja(double x1, double y1, double x2, double y2) {
  double dx = x1 - x2, dy = y1 - y2;
  return dx*dx + dy*dy;
}

void prostMnogougao(vector<Tacka>& tacke) {
  // pronalazimo centar kruga kao teziste neke 3 nekolinearne tacke
  int i = 2;
  while (kolinearne(tacke[0], tacke[1], tacke[i]))
    i++;
  double x0 = (tacke[0].x + tacke[1].x + tacke[i].x) / 3.0;
  double y0 = (tacke[0].y + tacke[1].y + tacke[i].y) / 3.0;

  // sortiramo tacke na osnovu ugla
  sort(begin(tacke), end(tacke),
       [x0, y0](const Tacka& t1, const Tacka& t2) {
         // ugao koji vektor t0t1 zaklapa sa negativnim smerom x ose
         double ugao1 = ugao(x0, y0, t1.x, t1.y);
         // ugao koji vektor t0t2 zaklapa sa negativnim smerom x ose
         double ugao2 = ugao(x0, y0, t2.x, t2.y);

         if (ugao1 < ugao2 - EPS)
           return true;
         
         if (ugao2 < ugao1 - EPS)
           return false;

         // razlika uglova je u intervalu [-EPS, EPS] pa tacke smatramo kolinearnim
         return kvadratRastojanja(x0, y0, t1.x, t1.y) <
                kvadratRastojanja(x0, y0, t2.x, t2.y);
       });
  // obrcemo redosled tacaka na poslednjoj pravoj
  auto it = prev(end(tacke));
  while (kolinearne(*prev(it), *it, tacke[0]))
    it = prev(it);
  reverse(it, end(tacke));
}


int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;
  prostMnogougao(tacke);
  for (const Tacka& t : tacke)
    cout << t.x << " " << t.y << endl;
  return 0;
}

Umesto težišta trougla određenog sa neke tri nekolinearne tačke iz skupa, za centar kruga \(O\) može se uzeti i jedna ekstremna tačka tačka iz skupa – na primer, tačka sa najvećom \(x\)-koordinatom (i sa najmanjom \(y\)-koordinatom, ako ima više tačaka sa najvećom \(x\)-koordinatom)¹. Ovakve tačke se često koriste prilikom rešavanja geometrijskih problema. Ekstremnu tačku povezujemo sa svim ostalim tačkama datog skupa i tačke sortiramo rastuće u odnosu na ugao koji poluprava od tačke \(O\) kroz tu tačku zahvata sa polupravom iz temena \(O\) koja je paralelna sa \(x\)-osom (a taj je ugao isti kao ugao koji poluprava od tačke \(O\) kroz tu tačku zahvata sa \(x\)-osom, jer su to uglovi sa paralelnim kracima). Tačke označene u ovom redosledu su prikazane na slici 7.

Pošto sve tačke leže levo od tačke \(O\), ugao između polupravih kroz dve uzastopne tačke ne može biti veći od \(\pi\), te do degenerisanog slučaja o kome je bilo reči ne može doći. Ako dve ili više tačaka zahvataju isti ugao, one se dalje sortiraju prema rastojanju od tačke \(O\) i to na sledeći način: ukoliko prvih nekoliko tačaka zahvataju isti ugao, njih sortiramo u rastućem redosledu rastojanja od tačke \(O\), ukoliko je poslednjih dve ili više tačaka kolinearno sa tačkom \(O\) njih sortiramo u opadajućem redosledu rastojanja od tačke \(O\), dok je za ostale tačke koje su kolinearne sa tačkom \(O\) svejedno da li ćemo ih sortirati rastuće ili opadajuće. Primetimo i to da je umesto računanja uglova moguće razmatrati orijentaciju tačaka. Naime, za potrebe sortiranja skupa tačaka prema uglu koji zahvataju sa horizontalnom pravom kroz tačku \(O\) iskoristićemo činjenicu da tačka \(P_i\) zahvata manji ugao od tačke \(P_j\) ako je orijentacija trojke tačaka \(P_j,O,P_i\) pozitivna (slika 8).

Prethodni algoritam se može implementirati na sledeći način:

void prostMnogougao(vector<Tacka>& tacke) {
  // trazimo tacku sa maksimalnom x koordinatom,
  // u slucaju da ima vise tacaka sa maksimalnom x koordinatom
  // biramo onu sa najmanjom y koordinatom
  auto max = max_element(begin(tacke), end(tacke),
                         [](const Tacka& t1, const Tacka& t2) {
                           return t1.x < t2.x ||
                                  (t1.x == t2.x && t1.y > t2.y);
                         });
  // dovodimo je na početak niza - ona predstavlja centar kruga
  swap(*begin(tacke), *max);
  const Tacka& t0 = tacke[0];

  // sortiramo ostatak niza (tačke sortiramo na osnovu ugla koji
  // zaklapaju u odnosu vertikalnu polupravu koja polazi naviše iz
  // centra kruga), a kolinearne na osnovu rastojanja od centra kruga
  sort(next(begin(tacke)), end(tacke),
       [&t0](const Tacka& t1, const Tacka& t2) {
         Orijentacija o = orijentacija(t0, t1, t2);
         if (o == KOLINEARNE)
           return kvadratRastojanja(t0, t1) <= kvadratRastojanja(t0, t2);
         return o == POZITIVNA;
       });

  // obrcemo redosled tacaka na poslednjoj pravoj
  auto it = prev(end(tacke));
  while (orijentacija(*prev(it), *it, t0) == KOLINEARNE)
    it = prev(it);
  reverse(it, end(tacke));
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
};

enum Orijentacija { POZITIVNA, NEGATIVNA, KOLINEARNE };

Orijentacija orijentacija(const Tacka& t0, const Tacka& t1, const Tacka& t2) {
  int d = (t1.x-t0.x)*(t2.y-t0.y) - (t2.x-t0.x)*(t1.y-t0.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

int kvadratRastojanja(const Tacka& t1, const Tacka& t2) {
  int dx = t1.x - t2.x, dy = t1.y - t2.y;
  return dx*dx + dy*dy;
}

void prostMnogougao(vector<Tacka>& tacke) {
  // trazimo tacku sa maksimalnom x koordinatom,
  // u slucaju da ima vise tacaka sa maksimalnom x koordinatom
  // biramo onu sa najmanjom y koordinatom
  auto max = max_element(begin(tacke), end(tacke),
                         [](const Tacka& t1, const Tacka& t2) {
                           return t1.x < t2.x ||
                                  (t1.x == t2.x && t1.y > t2.y);
                         });
  // dovodimo je na početak niza - ona predstavlja centar kruga
  swap(*begin(tacke), *max);
  const Tacka& t0 = tacke[0];

  // sortiramo ostatak niza (tačke sortiramo na osnovu ugla koji
  // zaklapaju u odnosu vertikalnu polupravu koja polazi naviše iz
  // centra kruga), a kolinearne na osnovu rastojanja od centra kruga
  sort(next(begin(tacke)), end(tacke),
       [&t0](const Tacka& t1, const Tacka& t2) {
         Orijentacija o = orijentacija(t0, t1, t2);
         if (o == KOLINEARNE)
           return kvadratRastojanja(t0, t1) <= kvadratRastojanja(t0, t2);
         return o == POZITIVNA;
       });

  // obrcemo redosled tacaka na poslednjoj pravoj
  auto it = prev(end(tacke));
  while (orijentacija(*prev(it), *it, t0) == KOLINEARNE)
    it = prev(it);
  reverse(it, end(tacke));
}


int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;

  prostMnogougao(tacke);
  for (const Tacka& t : tacke)
    cout << t.x << " " << t.y << endl;
  return 0;
}

10.2.2 Površina prostog mnogougla

Slično kao što je u poglavlju 10.1.5 pokazano za trougao i mnogougao se može rastaviti na trapeze, tako da se označena površina prostog mnogougla može dobiti sabiranjem označenih površina pojedinačnih trapeza. Transformacijom tako dobijene formule dobija se ponovo formula pertle kojom se izračunava površina prostog mnogougla zadatog tačkama \((x_1, y_1)\), \((x_2, y_2)\), \(\ldots\), \((x_n, y_n)\).

\[P = \frac{1}{2}\sum_{i=1}^{n}\left(x_iy_{i+1} - x_{i+1}y_i\right)\]

Pri tom se podrazumeva da je \((x_{n+1}, y_{n+1}) = (x_1, y_1)\).

10.2.3 Ispitivanje pripadnosti tačke unutrašnjosti prostog mnogougla

Zadatak geokodiranja jeste proces koji za zadato mesto ili adresu vraća njegove geografske koordinate. Jednako važan zadatak je i njemu inverzan, kojim se za date koordinate određuje mesto – grad, država ili neka oblast kojoj tačka sa tim koordinatama pripada. Ovaj problem se svodi na ispitivanje da li tačka sa datim koordinatama pripada unutrašnjosti mnogougla koji ograničava neku oblast.

U prethodnom odeljku razmotrili smo na koji način možemo utvrditi da li se tačka nalazi unutar datog trougla. Razmotrimo kako se ovo može uopštiti na proizvoljni prost mnogougao.

Problem na prvi pogled izgleda jednostavno, ali ako se razmatraju složeni nekonveksni mnogouglovi, kao onaj prikazan na slici 9, vidi se da to nije uvek slučaj. Intuitivni pristup je pokušati nekako “izaći napolje”, polazeći od zadate tačke \(Q\). Posmatrajmo proizvoljnu polupravu sa temenom \(Q\). Vidi se da je dovoljno prebrojati preseke sa stranicama mnogougla. U primeru na slici 9, idući na severoistok² od date tačke (prateći isprekidanu liniju), nailazimo na šest preseka sa mnogouglom. Pošto nas poslednji presek pre izlaska izvodi iz mnogougla, a pretposlednji nas vraća u mnogougao, i tako dalje, tačka \(Q\) je van mnogougla. Dakle, možemo zaključiti da je tačka \(Q\) u mnogouglu ako i samo ako je broj preseka poluprave iz \(Q\) sa stranicama mnogougla neparan.

Razmotrimo kako se ovaj algoritam može implementirati ako je mnogougao zadat nizom koordinata temena, što je uobičajeni scenario. Kada se problem rešava vizuelno, lako je naći dobar put (polupravu sa malo preseka) i nije potrebno razmatrati stranice mnogougla koje su daleko od tog puta. U slučaju mnogougla datog nizom koordinata, to nije jednostavno i najveći deo vremena troši se na ispitivanje postojanja preseka poluprave i stranica mnogougla, jer se ne vidi način da se izbegne obrada svih stranica. Ispitivanje preseka stranice i poluprave se može uprostiti ako je poluprava paralelna jednoj od osa — na primer \(y\)-osi i recimo usmerena nadole (kao na slici 10).

Naime, presek vertikalne poluprave kroz tačku \(Q\) sa stranicom \(P_iP_{i+1}\) mnogougla postoji ako se \(x\)-koordinata tačke \(Q\) nalazi između vrednosti \(x\)-koordinata temena \(P_i\) i \(P_{i+1}\) i ako je \(y\)-koordinata presečne tačke poluprave kroz \(Q\) i prave \(P_iP_{i+1}\) manja od \(y\)-koordinate tačke \(Q\). Pretpostavimo, jednostavnosti radi, da je \(x_{P_i} < x_{P_{i+1}}\) (ako nije, možemo razmeniti te dve tačke). Presečna tačka prave \(x=x_Q\) i prave \(P_iP_{i+1}\) čija je jednačina \(y-y_{P_i}=\frac{y_{P_{i+1}}-y_{P_i}}{x_{P_{i+1}}-x_{P_i}}(x-x_{P_i})\) je tačka čija je \(x\)-koordinata \(x_Q\), a \(y\)-koordinata je jednaka:

\[y=y_{P_i}+\frac{y_{P_{i+1}}-y_{P_i}}{x_{P_{i+1}}-x_{P_i}}(x_Q-x_{P_i}).\]

Dakle, potrebno je da važi \(y \leq y_Q\), što se, kada se izraz transformiše da bi se izbeglo deljenje (imenilac razlomka je pozitivan), svodi na:

\[y_{P_i}(x_{P_{i+1}}-x_{P_i}) + (y_{P_{i+1}}-y_{P_i})(x_Q-x_{P_i}) \leq y_Q(x_{P_{i+1}}-x_{P_i})\]

tj.

\[(y_{P_i} - y_Q)(x_{P_{i+1}}-x_{P_i}) \leq (y_{P_{i+1}}-y_{P_i})(x_{P_i} - x_Q)\]

Do ovog izraza se može doći i ako se proveri orijentacija trojke tačaka \(P_iP_{i+1}Q\).

Kao što je već pomenuto, obično postoje neki specijalni slučajevi koje treba posebno razmotriti. Neka je \(S\) tačka van mnogougla i pretpostavimo da umesto poluprave iz \(Q\) razmatramo duž \(QS\). Cilj je utvrditi da li tačka \(Q\) pripada unutrašnjosti mnogougla \(P\) na osnovu broja preseka duži \(QS\) sa stranicama mnogougla \(P\). Prvi specijalni slučaj je kada duž \(QS\) sadrži neko teme \(P_i\) mnogougla. Na slici 11 (a) prikazan je slučaj kad presek duži \(QS\) u temenu ne treba brojati, a na slici 11 (b) slučaj kad taj presek treba brojati. Postoji više načina za utvrđivanje da li neki ovakav presek treba brojati ili ne. Navedimo dva:

• ako su dva temena mnogougla susedna temenu \(P_i\) sa iste strane prave kojoj pripada duž \(QS\), presek se ne računa (oba susedna temena na slici 11 (a) su sa leve strane duži \(QS\)). U protivnom, ako su temena susedna temenu \(P_i\) sa različitih strana ove prave, presek se broji (na 11 (b) jedno susedno teme je sa leve, a drugo sa desne strane duži \(QS\)). Ovo u većini slučajeva rešava problem, međutim, ostaje problematičan slučaj kada neka od te dve tačke leži na pravoj \(QS\).

• s obzirom na to da razmatramo pravu koja je paralelna sa \(y\) osom, za svaku stranicu mnogougla trebalo bi računati preseke sa levim temenom, a ne sa desnim (temena neke stranice mnogougla klasifikujemo kao levo i desno u odnosu na vrednosti \(x\)-koordinate temena). Na taj način nećemo računati presek nalik onom na slici 11 (a) jer je za obe stranice mnogougla susedne temenu \(P_i\) presek kroz desno teme (i slično dva puta bismo računali presek sa temenom koje je levi ekstremum i opet se ne bi promenila parnost brojača). Za presek prikazan na slici 11 (b) ubrajamo jedan presek, jer je za jednu od stranica koje se sustiču u tom temenu to levo teme, a za drugu desno.

Drugi specijalan slučaj se javlja kada se duž \(QS\) delom preklapa sa nekim stranicama mnogougla \(P\). Ovo preklapanje očigledno ne treba brojati u preseke.

U nastavku ćemo razmotriti implementaciju algoritma za ispitivanje da li je tačka u mnogouglu koja ne uključuje obradu specijalnih slučajeva.

// utvrdjuje da li se tacka Q nalazi u datom mnogouglu P
// racunanjem parnosti preseka sa vertikalnom polupravom
// usmerenom nadole sa temenom u tacki Q
bool tackaUMnogouglu(const vector<Tacka>& P, const Tacka& Q) {
  int n = P.size();
  // mnogougao mora da ima bar 3 temena
  if (n < 3)
    return false;
    
  // tacka je inicijalno van mnogougla
  bool uMnogouglu = false;

  // prolazimo skupom svih stranica mnogougla
  for (int i = 0; i < n; i++) {
    // naredno teme u poretku temena mnogougla
    int j = (i + 1) % n;
    // obezbedjujemo da prva tacka ima manju x koordinatu
    Tacka Pi = P[i], Pj = P[j];
    if (Pi.x > Pj.x) swap(Pi, Pj);
    // ukoliko se x koordinata tacke Q nalazi izmedju vrednosti
    // x koordinata krajnjih tacaka stranice PiPj i
    // y koordinata presecne tacka prave x = x_Q i prave PiPj 
    // je manja od y koordinate tacke Q 
    if (Pi.x < Q.x && Q.x < Pj.x &&
        (Pi.y-Q.y)*(Pj.x-Pi.x) <= (Pj.y-Pi.y)*(Pi.x-Q.x))
      // registrujemo jos jedan presek
      uMnogouglu = !uMnogouglu;
  }
  return uMnogouglu;
} 

Neka je \(n\) broj stranica mnogougla. Kroz osnovnu petlju algoritma prolazi se \(n\) puta. U svakom prolasku kroz petlju računa se presek dve prave i izvršavaju se još neke operacije za konstantno vreme. Dakle, ukupno vreme izvršavanja algoritma iznosi \(O(n)\). Algoritam se može ubrzati tako što se izbegne analiza nekih stranica mnogougla, što se može učiniti smeštanjem stranica u specijalne strukture podataka koje omogućavaju brzu prostornu pretragu (npr. \(R\)-stabla).

10.2.4 Ispitivanje pripadnosti tačke unutrašnjosti konveksnog mnogougla

Provera pripadnosti tačke unutrašnjosti mnogougla može biti mnogo efikasnija ako je mnogougao konveksan.

Jednostavnosti radi, ponovo za početak pretpostavljamo da tačka \(Q\) ne pripada stranicama datog konveksnog mnogougla \(P_0P_1\ldots P_{n-1}\).

Algoritam zasnovan na orijentaciji

Jedno moguće rešenje je uopštenje algoritma za ispitivanje da li tačka pripada datom trouglu. Ono nije efikasnije nego opšte rešenje za prost mnogougao, ali je jednostavnije od njega. Jednostavnosti radi, pretpostavimo da su temena konveksnog mnogougla data u matematički pozitivnom smeru (smeru suprotnom od smera kazaljke na časovniku). Tačka \(Q\) pripada unutrašnjosti mnogougla ako i samo ako se nalazi s leve strane svake usmerene stranice \(P_iP_{i+1}\), \(0\leq i\leq n-1, P_n=P_0\) mnogougla, odnosno ako za svako \(i\) trojka tačaka \(P_iP_{i+1}Q\) ima pozitivnu orijentaciju. U primeru prikazanom na slici 12 ovaj uslov važi za tačku \(Q\) na slici levo, ali ne i za tačku \(Q\) na slici desno. Složenost ovog algoritma iznosi \(O(n)\).

Ako nije poznata orijentacija temena konveksnog mnogougla (već samo njihov redosled) kako bi se utvrdilo da li tačka \(Q\) pripada unutrašnjosti mnogougla potrebno je proveriti da li svaka trojka \(P_iP_{i+1}Q\) ima istu orijentaciju (bila ona pozitivna ili negativna).

Ako je orijentacija neke trojke \(P_iP_{i+1}Q\) jednaka nuli, to znači da tačka \(Q\) pripada pravoj \(P_iP_{i+1}\), pa pošto smo pretpostavili da \(Q\) ne pripada stranici \(P_iP_{i+1}\), ona sigurno pripada spoljašnjosti mnogougla.

Možemo razmotriti i opštiji problem, u kom nije unapred poznato da tačka ne pripada stranicama mnogougla. Tada, ako je orijentacija neke trojke \(P_iP_{i+1}Q\) jednaka nuli, tačka \(Q\) pripada duži \(P_iP_{i+1}\) ako i samo ako su sve ostale orijentacije istog znaka, pa rezultat određujemo u zavisnosti od toga da li želimo da smatramo da stranice pripadaju oblasti mnogougla ili ne (da li je mnogougao zatvorena ili otvorena figura).

Algoritam zasnovan na binarnoj pretrazi

Ideja na kojoj se zasniva efikasniji algoritam se oslanja na binarnu pretragu.

Iskoristićemo prethodnu lemu da binarnom pretragom pronađemo vrednost \(i\) takvu da tačka \(Q\) pripada uglu \(P_iP_0P_{i+1}\). Održavaćemo tekući ugao \(\angle P_iP_0P_j\) kome pripada tačka \(Q\), koji inicijalizujemo na \(\angle P_1P_0P_{n-1}\). U svakom koraku za tačku \(P_m\) biramo središnju tačku – tačku sa indeksom \(m=\lfloor (i+j)/2\rfloor\) i ažuriramo ugao kome pripada tačka \(Q\) prema prethodnoj lemi. Zaustavljamo se kada tačke \(P_i\) i \(P_j\) postanu susedna temena mnogougla, tj. kada je \(j = i+1\). Posle najviše \(O(\log n)\) koraka pronalazi se ugao \(\angle P_iP_0P_{i+1}\) kome tačka \(Q\) mora pripadati ako pripada mnogouglu. Tada znamo da tačka \(Q\) pripada mnogouglu ako i samo ako pripada trouglu \(\bigtriangleup P_0P_iP_{i+1}\). Na slici 14 prikazan je primer postupka polovljenja ugla kome pripada tačka \(Q\).

Na početku je moguće proveriti da li tačka pripada uglu \(\angle P_1P_0P_{n-1}\) i ako ne pripada odmah se može zaključiti da tačka ne pripada ni mnogouglu. Međutim, ta provera nije neohpodna, jer ako tačka ne pripada tom uglu binarnom pretragom će se doći ili do trougla \(\bigtriangleup P_0P_1P_2\) ili \(\bigtriangleup P_0P_{n-2}P_{n-1}\) i tada će se zaključiti da mu tačka ne pripada, pa ne pripada ni mnogouglu.

Ovaj algoritam se može veoma jednostavno implementirati.

// provera da li se tacka A nalazi unutar preseka poligona A i ugla A[l]A[0]A[d]
bool sadrzi(const vector<Tacka>& poligon, const Tacka& Q, int l, int d) {
  if (d - l == 1)
    return tackaUTrouglu(Q, poligon[0], poligon[l], poligon[d]);
  int s = l + (d - l) / 2;
  if (orijentacija(poligon[0], poligon[s], Q) == POZITIVNA)
    return sadrzi(poligon, Q, s, d);
  else
    return sadrzi(poligon, Q, l, s);
}

// provera da li konveksni poligon sadrzi tacku A
bool sadrzi(const vector<Tacka>& poligon, const Tacka& A) {
  return sadrzi(poligon, A, 1, poligon.size()-1);
}

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int, int> Tacka;

enum Orijentacija {POZITIVNA, NEGATIVNA, KOLINEARNE};

Orijentacija orijentacija(const Tacka& a, const Tacka& b, const Tacka& c) {
  int xa = a.first, ya = a.second;
  int xb = b.first, yb = b.second;
  int xc = c.first, yc = c.second;
  long long d = (long long)(xb-xa)*(long long)(yc-ya) -
                (long long)(xc-xa)*(long long)(yb-ya);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

bool saIsteStrane(const Tacka& T1, const Tacka& T2,
                  const Tacka& A1, const Tacka& A2) {
  Orijentacija o1 = orijentacija(T1, T2, A1);
  Orijentacija o2 = orijentacija(T1, T2, A2);
  if (o1 == KOLINEARNE || o2 == KOLINEARNE)
    return true;
  return o1 == o2;
}

bool tackaUTrouglu(const Tacka& A, const Tacka& T1, const Tacka& T2,
                   const Tacka& T3) {
  return saIsteStrane(T1, T2, T3, A) &&
         saIsteStrane(T1, T3, T2, A) &&
         saIsteStrane(T2, T3, T1, A);
}

// provera da li se tacka A nalazi unutar preseka poligona A i ugla A[l]A[0]A[d]
bool sadrzi(const vector<Tacka>& poligon, const Tacka& Q, int l, int d) {
  if (d - l == 1)
    return tackaUTrouglu(Q, poligon[0], poligon[l], poligon[d]);
  int s = l + (d - l) / 2;
  if (orijentacija(poligon[0], poligon[s], Q) == POZITIVNA)
    return sadrzi(poligon, Q, s, d);
  else
    return sadrzi(poligon, Q, l, s);
}

// provera da li konveksni poligon sadrzi tacku A
bool sadrzi(const vector<Tacka>& poligon, const Tacka& A) {
  return sadrzi(poligon, A, 1, poligon.size()-1);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);

  int n;
  cin >> n;
  vector<Tacka> poligon(n);
  for (int i = 0; i < n; i++) {
    cin >> poligon[i].first >> poligon[i].second;
  }

  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    Tacka A;
    cin >> A.first >> A.second;
    if (sadrzi(poligon, A))
      cout << "da" << '\n';
    else
      cout << "ne" << '\n';
  }
  
  return 0;
}

Prethodna implementacija podrazumeva da se proverava pripadnost zatvorenom mnogouglu (stranice se smatraju delom mnogougla) što dalje podrazumeva da provera pripadnosti trouglu takođe mora da uključi i stranice. U suprotnom je potrebno posebno obraditi slučaj kada središnja tačka \(P_s\) leži na pravoj \(P_0P\) i umesto da se procedura nastavi rekurzivno (što je trenutno slučaj), treba proveriti da li je \(A\) strogo između \(P_0\) i \(P_s\).

10.2.5 Konveksni omotač

Konveksni omotač (engl. convex hull) konačnog skupa tačaka definiše se kao najmanji konveksni mnogougao takav da sve tačke tog skupa pripadaju unutrašnjosti ili stranicama tog mnogougla (slika 15). Definisaćemo i da je za jednu tačku konveksni omotač ta tačka, a za par tačaka duž koja ih spaja. Jasno je iz definicije da je konveksni omotač tri nekolinearne tačke trougao kome su te tačke temena. Konveksni omotač se predstavlja na isti način kao bilo koji mnogougao — nizom svojih uzastopnih temena.

Kao što smo već videli, obrada konveksnih mnogouglova jednostavnija je od obrade proizvoljnih mnogouglova. Na primer, provera pripadnosti tačke unutrašnjosti proizvoljnog prostog \(n\)-tougla je složenosti \(O(n)\), dok je ispitivanje pripadnosti tačke unutrašnjosti konveksnog \(n\)-tougla složenosti \(O(\log n)\).

Iz uslova da je konveksni omotač najmanji konveksni mnogougao sa datim svojstvima, sledi da su temena konveksnog omotača neke od tačaka iz zadatog skupa. Kazaćemo da tačka pripada omotaču ako je teme omotača. Ako zanemarimo trivijalne slučajeve kada polazni skup ne sadrži bar tri nekolinearne tačke, konveksni omotač može se sastojati od najmanje tri, a najviše \(n\) tačaka (slika 16).

Konveksni omotači imaju široku primenu (na primer, u praćenju širenja epidemija, modelovanju glatkih krivih, smanjenju broja boja na slici, planiranju kretanja robota, kao gradivni element u drugim algoritmima, kao što je recimo traženje dijametra skupa tačaka), pa su zbog toga razvijeni mnogobrojni algoritmi za njihovu konstrukciju. Razmotrimo problem navigacije robota u ravni od tačke \(A\) do tačke \(B\). Najjednostavniji način da robot realizuje ovo kretanje je pravolinijski, duž duži \(AB\). Međutim, na ovoj pravolinijskoj putanji se može naći neka od prepreka. Stoga se svaka od prepreka može uzorkovati tačkom u ravni, a onda napraviti konveksni omotač svih ovih tačaka. Za putanju koja ne seče ovaj omotač se garantuje da neće biti sudara robota sa nekom od prepreka.

Direktni induktivni pristup

Kao i obično, pokušaćemo najpre sa direktnim induktivnim pristupom. Konveksni omotač za jednu tačku je jednočlan i to može biti baza indukcije. Pretpostavimo da umemo da konstruišemo konveksni omotač skupa sa manje od \(n\) tačaka i pokušajmo da konstruišemo konveksni omotač skupa od \(n\) tačaka. Na koji način \(n\)-ta tačka može da promeni konveksni omotač prvih \(n-1\) tačaka? Postoje dva moguća slučaja:

• nova tačka je u prethodnom konveksnom omotaču, pa on ostaje nepromenjen,
• nova tačka je van prethodnog konveksnog omotača, pa se omotač “širi” da obuhvati i novu tačku (slika 17).

Prilikom dodavanja svake nove tačke potrebno je, dakle, rešiti dva potproblema: utvrđivanje da li je nova tačka unutar omotača i proširivanje omotača novom tačkom.

Stvar se može uprostiti pogodnim izborom \(n\)-te tačke, tako da ne moramo eksplicitno vršiti proveru da li ona pripada prethodnom omotaču. Zvuči primamljivo pokušati da uvek biramo tačku unutar omotača, jer tada ne moramo da menjamo omotač da bi se proširila induktivna hipoteza; to, međutim, nije uvek moguće jer u nekim slučajevima sve tačke polaznog skupa pripadaju konveksnom omotaču (16, levo). Sasvim suprotna mogućnost je da se u svakom koraku bira tačka za koju znamo da ne pripada unutrašnjosti tekućeg omotača. To će biti zadovoljeno ako se u svakom koraku bira neka ekstremna tačka novog mnogougla, pri čemu nam taj izbor, kao što ćemo videti, dodatno uprošćava postupak ažuriranja konveksnog omotača. Podsetimo se, ekstremne tačke su se pokazale uspešne pri rešavanju problema konstrukcije prostog mnogougla. Ekstremna tačka koja se u tom problemu koristila je ona sa maksimalnom \(x\)-koordinatom (pri čemu se ako ima više takvih tačaka bira ona sa minimalnom \(y\)-koordinatom). Da bi se u svakom koraku koristila ekstremna tačka, potrebno je tačke obrađivati u neopadajućem redosledu \(x\)-koordinata (pri čemu tačke sa istom \(x\)-koordinatom treba obrađivati u nerastućem redosledu \(y\)-koordinata), što se najlakše postiže ako se u startu tačke sortiraju na taj način.

Neka je tekuća tačka kojom se proširuje konveksni omotač konstruisan od početnih \(n-1\) tačaka tačka \(Q\), koja je ekstremna u tekućem skupu od \(n\) tačaka. Tačka \(Q\) mora biti teme novog konveksnog omotača. Pitanje je kako promeniti konveksni omotač ostalih \(n-1\) tačaka tako da novi omotač obuhvati tačku \(Q\). Potrebno je najpre pronaći temena starog omotača koja su u unutrašnjosti novog omotača (\(P_3\) i \(P_4\) u primeru na slici 17) i ukloniti ih, a zatim je potrebno umetnuti novo teme \(Q\) između dva postojeća (\(P_2\) i \(P_5\) na slici 17).

Određivanje tačaka tekućeg omotača koje treba da budu zamenjene tačkom \(Q\) može se izvršiti korišćenjem pravih oslonca. Prava oslonca (engl. supporting plane) konveksnog mnogougla je prava koja sadrži bar jednu tačku mnogougla i sve ostale tačke mnogougla se nalaze sa iste strane te prave. U našem slučaju su bitne prave oslonca koje sadrže tačku \(Q\). Na primer, na slici 17 prave \(QP_2\) i \(QP_5\) su dve prave oslonca i polaznog i proširenog konveksnog mnogougla. Obično samo jedno teme mnogougla povezivanjem sa \(Q\) određuje pravu oslonca (postoji i specijalni slučaj kad više temena mnogougla leži na pravi oslonca, koji ćemo na trenutak zanemariti). Mnogougao leži između dve prave oslonca, što ukazuje na to na koji način treba izvesti modifikaciju omotača. Prave oslonca zahvataju minimalni i maksimalni ugao sa \(x\)-osom među svim pravama koje sadrže tačku \(Q\) i neko teme mnogougla. Da bismo odredili ta dva temena, potrebno je da razmotrimo poluprave iz tačke \(Q\) ka svim temenima, da izračunamo uglove koje one zahvataju sa \(x\)-osom, i među tim uglovima izaberemo minimalan (čime dobijamo tačku \(P_i\)) i maksimalan (čime dobijamo tačku \(P_j\)). Umesto eksplicitnog računanja uglova, moguće ih je samo upoređivati na osnovu orijentacije (ugao koji poluprava \(QP_m\) zahvata sa \(x\)-osom manji je od ugla koji poluprava \(QP_n\) zahvata sa \(x\)-osom ako i samo ako je trojka \(QP_mP_n\) pozitivno orijentisana. U specijalnom slučaju se može desiti da su neke tačke \(P_m\) i \(P_n\) kolinearne sa tačkom \(Q\) i tada uzimamo onu od njih koja se nalazi dalje od \(Q\) (jer pretpostavljamo da je konveksni omotač zatvoren mnogougao i da pošto bliža tačka pripada stranici, pripada i omotaču).

Posle pronalaženja dva ekstremna temena \(P_i\) i \(P_j\) modifikovani omotač dobijamo tako što onaj niz temena između \(P_i\) i \(P_j\) (bez \(P_i\) i \(P_j\)) čije su tačke sa iste strane prave \(P_iP_j\) kao i tačka \(Q\) zamenimo tačkom \(Q\) (ako je taj niz prazan, samo se umeće nova tačka \(Q\)).

Da bi se realizovao prethodni algoritam, nije neophodno eksplicitno ispitivati koji od dva niza tačaka između \(P_i\) i \(P_j\) leži sa iste strane prave \(P_iP_j\) kao i \(Q\). Naime, ako sva temena trenutnog konveksnog omotača čuvamo u redosledu pozitivne orijentacije, pošto je tačka \(Q\) ekstremna i nalazi se desno od prave \(P_iP_j\), tačke između \(P_j\) i \(P_i\) će biti sa iste strane prave \(P_iP_j\) kao i \(Q\), dok će tačke između \(P_i\) i \(P_j\) biti sa suprotne strane. Dakle, uvek je potrebno niz tačaka od \(P_{j+1}\) do \(P_{i-1}\) zameniti tačkom \(Q\) (pri čemu se uvećanje i umanjenje indeksa računa ciklično, tj. po modulu \(n\)). Ako su tačke \(P_j\) i \(P_i\) susedne, taj niz može biti i prazan.

U nastavku je prikazana C++ implementacija ovog algoritma.

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // sortiramo tacke po x koordinati neopadajuce,
  // ako postoje dve tacke sa istom vrednoscu x koordinate
  // manjom smatramo onu sa vecom y koordinatom
  sort(begin(tacke), end(tacke),
       [](const Tacka &p1, const Tacka &p2) {
         return (p1.x < p2.x) || (p1.x == p2.x && p1.y > p2.y);
       });

  // u konveksni omotac dodajemo prvu tacku
  vector<Tacka> omotac;
  omotac.push_back(tacke[0]);
  
  // dodajemo jednu po jednu tacku u omotac u redosledu rastucih x koordinata
  for (int k = 1; k < tacke.size(); k++) {
    // trazimo gornju pravu oslonca
    // to je prava P_kP_i tako da za svako ii vazi
    // da trojka tacaka {P_k, P_i, P_ii} ima pozitivnu orijentaciju ili su
    // tacke kolinearne, ali je P_ii dalje od tacke P_k nego P_i
    int i = 0;
    for (int ii = 0; ii < omotac.size(); ii++) {
      int o = orijentacija(tacke[k], omotac[i], omotac[ii]);
      if (o == NEGATIVNA ||
          (o == KOLINEARNE && kvadratRastojanja(tacke[k], omotac[i]) <
                              kvadratRastojanja(tacke[k], omotac[ii])))
         i = ii;
    }
    
    // trazimo donju pravu oslonca
    // to je prava P_kP_j tako da za svako jj vazi
    // da trojka tacaka {P_k, P_jj, P_j} ima pozitivnu orijentaciju ili su
    // tacke kolinearne, ali je P_jj dalje od tacke P_k nego P_j
    int j = 0;
    for (int jj = 0; jj < omotac.size(); jj++) {
      int o = orijentacija(tacke[k], omotac[jj], omotac[j]);
      if (o == NEGATIVNA ||
          (o == KOLINEARNE && kvadratRastojanja(tacke[k], omotac[j]) <
                              kvadratRastojanja(tacke[k], omotac[jj])))
         j = jj;
    }

    zameni(omotac, (j + 1) % omotac.size(), i, tacke[k]);
  }
  return omotac;
}

// podniz niza a_i,...,a_{j-1} menjamo elementom x
// ako je i > j, brisu se elementi do kraja, pa zatim sa pocetka niza
void zameni(vector<Tacka>& a, int i, int j, const Tacka& x) {
    if (i < j)
      // ako je i < j, onda su tacke koje brisemo susedne
      a.erase(a.begin() + i, a.begin() + j);
    else if (i > j) {
      // ako je j > i, onda elemente brisemo iz dva dela
      a.erase(a.begin() + i, a.end());
      a.erase(a.begin(), a.begin() + j);
    }
    // ako je i = j, onda se ne brise nista
    
    // ubacujemo novi broj x
    a.insert(a.begin() + i, x);
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
};

enum Orijentacija { POZITIVNA, NEGATIVNA, KOLINEARNE };

Orijentacija orijentacija(const Tacka& t0, const Tacka& t1, const Tacka& t2) {
  long long d = (long long)(t1.x-t0.x)*(long long)(t2.y-t0.y) -
                (long long)(t2.x-t0.x)*(long long)(t1.y-t0.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

long long kvadratRastojanja(const Tacka& t1, const Tacka& t2) {
  long long dx = t1.x - t2.x, dy = t1.y - t2.y;
  return dx*dx + dy*dy;
}

// podniz niza a_i,...,a_{j-1} menjamo elementom x
// ako je i > j, brisu se elementi do kraja, pa zatim sa pocetka niza
void zameni(vector<Tacka>& a, int i, int j, const Tacka& x) {
    if (i < j)
      // ako je i < j, onda su tacke koje brisemo susedne
      a.erase(a.begin() + i, a.begin() + j);
    else if (i > j) {
      // ako je j > i, onda elemente brisemo iz dva dela
      a.erase(a.begin() + i, a.end());
      a.erase(a.begin(), a.begin() + j);
    }
    // ako je i = j, onda se ne brise nista
    
    // ubacujemo novi broj x
    a.insert(a.begin() + i, x);
}

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // sortiramo tacke po x koordinati neopadajuce,
  // ako postoje dve tacke sa istom vrednoscu x koordinate
  // manjom smatramo onu sa vecom y koordinatom
  sort(begin(tacke), end(tacke),
       [](const Tacka &p1, const Tacka &p2) {
         return (p1.x < p2.x) || (p1.x == p2.x && p1.y > p2.y);
       });

  // u konveksni omotac dodajemo prvu tacku
  vector<Tacka> omotac;
  omotac.push_back(tacke[0]);
  
  // dodajemo jednu po jednu tacku u omotac u redosledu rastucih x koordinata
  for (int k = 1; k < tacke.size(); k++) {
    // trazimo gornju pravu oslonca
    // to je prava P_kP_i tako da za svako ii vazi
    // da trojka tacaka {P_k, P_i, P_ii} ima pozitivnu orijentaciju ili su
    // tacke kolinearne, ali je P_ii dalje od tacke P_k nego P_i
    int i = 0;
    for (int ii = 0; ii < omotac.size(); ii++) {
      int o = orijentacija(tacke[k], omotac[i], omotac[ii]);
      if (o == NEGATIVNA ||
          (o == KOLINEARNE && kvadratRastojanja(tacke[k], omotac[i]) <
                              kvadratRastojanja(tacke[k], omotac[ii])))
         i = ii;
    }
    
    // trazimo donju pravu oslonca
    // to je prava P_kP_j tako da za svako jj vazi
    // da trojka tacaka {P_k, P_jj, P_j} ima pozitivnu orijentaciju ili su
    // tacke kolinearne, ali je P_jj dalje od tacke P_k nego P_j
    int j = 0;
    for (int jj = 0; jj < omotac.size(); jj++) {
      int o = orijentacija(tacke[k], omotac[jj], omotac[j]);
      if (o == NEGATIVNA ||
          (o == KOLINEARNE && kvadratRastojanja(tacke[k], omotac[j]) <
                              kvadratRastojanja(tacke[k], omotac[jj])))
         j = jj;
    }

    zameni(omotac, (j + 1) % omotac.size(), i, tacke[k]);
  }
  return omotac;
}

int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;
  vector<Tacka> omotac = konveksniOmotac(tacke);
  cout << omotac.size() << endl;
  for (const Tacka& t : omotac)
    cout << t.x << " " << t.y << endl;
  return 0;
}

Primetimo da se u funkciji sortira dati niz tačaka, što znači da argument funkcije nije konstantan. Ako bismo insistirali da se niz ne sme menjati tokom izračunavanja omotača (što je korisna praksa), morali bismo napraviti sortiranu kopiju niza unutar funkcije, čime bi se dobio malo neefikasniji algoritam.

Razmotrimo složenost ovog algoritma. Prvo se sortira niz temena, za šta je potrebno vreme \(O(n\log{n})\). Za svaku novu tačku koja se dodaje skupu treba izračunati uglove koje grade prave određene tačkom \(Q\) i svakim od temena prethodnog omotača i \(x\)-osa, pronaći među njima minimalni i maksimalni ugao, izbaciti neka temena iz prethodnog omotača i dodati novo teme. Dakle, složenost dodavanja \(k\)-te tačke u tekući skup tačaka je \(O(k)\), a ukupno razmatramo \(n\) tačaka pa se složenost ovog dela algoritma može opisati rekurentnom jednačinom \(T(n)=T(n-1)+O(n)\) čije je rešenje \(O(n^2)\). Pošto je vreme sortiranja \(O(n\log{n})\) asimptotski manje od vremena \(O(n^2)\) potrebnog za ostale operacije, ono ne utiče na ukupnu složenost \(O(n^2)\). Naglasimo i da izbor strukture podataka za čuvanje trenutnog niza temena konveksnog mnogougla (liste ili vektora) ne utiče na asimptotsku složenost (složenost funkcije zameni bi mogla biti snižena kada bi se koristila lista, ali bi asimptotska složenost ostala kvadratna).

Uvijanje poklona

Na koji način se opisani algoritam može poboljšati? Kad proširujemo mnogougao teme po teme, dosta vremena trošimo na formiranje konveksnih omotača od tačaka za koje će se kasnije možda pokazati da su unutrašnje za konačni konveksni omotač. Može li se to izbeći? Umesto da pravimo konveksne omotače podskupova datog skupa tačaka, možemo da posmatramo kompletan skup tačaka i da direktno pravimo njegov konveksni omotač. Može se, kao i u prethodnom algoritmu, krenuti od ekstremne tačke. U principu, svejedno je koja se ekstremna tačka koristi. Da bismo ilustrovali malo drugačiji pristup od dosadašnjih rešenja, možemo, na primer, krenuti od tačke sa najmanjom vrednošću \(x\) koordinate, a ako ih ima više one među njima koja ima najmanju \(y\) koordinatu. Kao što smo već pomenuli, ekstremna tačka uvek pripada konveksnom omotaču. Ideja je da se u svakom koraku u omotač doda naredno teme koje je deo konačnog konveksnog omotača (pri čemu temena obilazimo, na primer, u negativnom matematičkom smeru). Kako nalazimo narednu stranicu konveksnog omotača? Jedno teme te stranice biće poslednja tačka do sada određenog dela konveksnog omotača. Da bismo odredili drugo teme stranice, analiziraćemo sve tačke i tražiti onu koja daje duž koja sa prethodnom duži gradi što veći ugao. Primetimo da prilikom određivanja prve stranice mnogougla ne postoji prethodna duž, te u tom slučaju tražimo duž koja gradi maksimalni ugao sa npr. negativnim smerom \(y\) ose.

Umesto računanja uglova možemo upotrebiti orijentaciju. Neka je \(P_t\) tekuća tačka u konveksnom omotaču. Obrađivaćemo preostale tačke i suštinski primenjivati algoritam određivanja maksimuma. Pretpostavićemo da se maksimalni ugao postiže za neku tačku \(P_l\) različitu od \(P_t\). Zatim ćemo redom obrađivati sve ostale tačke.

• Ako je orijentacija trojke tačaka \(P_tP_lP_i\) negativna, tada je ugao duži \(P_tP_l\) veći od ugla \(P_tP_i\) i \(P_l\) ostaje kandidat za teme duži sa maksimalnim uglom.
• Ako je orijentacija trojke tačaka \(P_tP_lP_i\) pozitivna, tada je ugao duži \(P_tP_i\) veći od ugla \(P_tP_l\) i \(P_i\) postaje novi kandidat za teme duži sa maksimalnim uglom.
• Ako je orijentacija trojke tačaka \(P_tP_lP_i\) jednaka nuli, tri tačke su kolinearne. Pošto smatramo da je konveksni omotač zatvoren mnogougao, želimo da uzmemo onu tačku koja je dalja od \(P_t\), tako da se tekući kandidat menja ako je \(P_l\) između \(P_t\) i \(P_i\).

Postupak se završava kada se ustanovi da je tačka koja određuje najveći ugao sa prethodnom tačkom jednaka početnoj tački. Koraci u izvršavanju ovog algoritma za jedan skup tačaka su prikazani na slici 18.

Ovaj algoritam se iz razumljivih razloga zove uvijanje poklona (engl. gift wrapping algorithm). Polazi se od jednog temena “poklona”, i onda se on uvija u konveksni omotač pronalaženjem temena po temena omotača. Poznat je i pod nazivom Džarvisov marš (engl. Jarvis March algorithm), po svom autoru.

Algoritam uvijanja poklona je direktna posledica primene sledeće induktivne hipoteze (po \(k\)):

Kod ove hipoteze naglasak je na proširivanju puta, a ne omotača. Umesto da pronalazimo konveksne omotače podskupova, mi pronalazimo deo konačnog konveksnog omotača.

Algoritam uvijanja poklona je moguće implementirati na sledeći način:

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // odredjujemo redni broj ekstremne tacke (one sa najmanjom x koordinatom)
  auto cmp = [] (const Tacka& t1, const Tacka& t2) {
    return t1.x < t2.x || (t1.x == t2.x && t1.y < t2.y);
  };
  int prva = distance(begin(tacke), min_element(begin(tacke), end(tacke), cmp));

  // niz tacaka koje cine omotac
  vector<Tacka> omotac;
  // krecemo od ekstremne tacke
  int tekuca = prva;
  do {
    omotac.push_back(tacke[tekuca]);
    // krecemo obradu od prve tacke u nizu, osim ako je prva tacka
    // bas ekstremna; u tom slucaju krecemo od druge tacke
    int naredna = tekuca == 0 ? 1 : 0;
    // odredjujemo narednu tacku u omotacu, zahtevajuci da se sve
    // ostale tacke nalaze sa desne strane prave odredjene tekucom i
    // tom narednom tackom
    for (size_t i = 0; i < tacke.size(); i++) {
      // razmatramo sve tacke osim onih kojima je odredjena poslednja duz
      if (i == tekuca || i == naredna)
        continue;
      Orijentacija o = orijentacija(tacke[tekuca], tacke[naredna], tacke[i]);
      if (o == POZITIVNA ||
          (o == KOLINEARNE && izmedju(tacke[tekuca], tacke[naredna], tacke[i])))
        naredna = i;
    }
    tekuca = naredna;
  } while (tekuca != prva);
  return omotac;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
};

enum Orijentacija { POZITIVNA, NEGATIVNA, KOLINEARNE };

Orijentacija orijentacija(const Tacka& t0, const Tacka& t1, const Tacka& t2) {
  long long d = (long long)(t1.x-t0.x)*(long long)(t2.y-t0.y) -
                (long long)(t2.x-t0.x)*(long long)(t1.y-t0.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

bool izmedju1(int a, int b, int c) {
  return (a <= b && b <= c) || (a >= b && b >= c);
}

bool izmedju(const Tacka& t1, const Tacka& t2, const Tacka& t3) {
  return izmedju1(t1.x, t2.x, t3.x) && izmedju1(t1.y, t2.y, t3.y);
}

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // odredjujemo redni broj ekstremne tacke (one sa najmanjom x koordinatom)
  auto cmp = [] (const Tacka& t1, const Tacka& t2) {
    return t1.x < t2.x || (t1.x == t2.x && t1.y < t2.y);
  };
  int prva = distance(begin(tacke), min_element(begin(tacke), end(tacke), cmp));

  // niz tacaka koje cine omotac
  vector<Tacka> omotac;
  // krecemo od ekstremne tacke
  int tekuca = prva;
  do {
    omotac.push_back(tacke[tekuca]);
    // krecemo obradu od prve tacke u nizu, osim ako je prva tacka
    // bas ekstremna; u tom slucaju krecemo od druge tacke
    int naredna = tekuca == 0 ? 1 : 0;
    // odredjujemo narednu tacku u omotacu, zahtevajuci da se sve
    // ostale tacke nalaze sa desne strane prave odredjene tekucom i
    // tom narednom tackom
    for (size_t i = 0; i < tacke.size(); i++) {
      // razmatramo sve tacke osim onih kojima je odredjena poslednja duz
      if (i == tekuca || i == naredna)
        continue;
      Orijentacija o = orijentacija(tacke[tekuca], tacke[naredna], tacke[i]);
      if (o == POZITIVNA ||
          (o == KOLINEARNE && izmedju(tacke[tekuca], tacke[naredna], tacke[i])))
        naredna = i;
    }
    tekuca = naredna;
  } while (tekuca != prva);
  return omotac;
}


int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;
  vector<Tacka> omotac = konveksniOmotac(tacke);
  cout << omotac.size() << endl;
  for (const Tacka& t : omotac)
    cout << t.x << " " << t.y << endl;
  return 0;
}

Ako je \(m\) broj temena konačnog konveksnog omotača, vremenska složenost uvijanja poklona je \(O(mn)\). Dakle, ovaj algoritam spada u grupu algoritama čija složenost zavisi ne samo od dimenzije ulaza, već i od dimenzije izlaza, tj. algoritama sa izlazno zavisnom složenošću. U slučaju kada je konveksni omotač skupa tačaka trougao (slika 16 desno), algoritam uvijanja poklona ima složenost \(O(n)\), a u slučaju kada sve tačke (ili u opštem slučaju \(O(n)\) tačaka) pripadaju konveksnom omotaču (slika 16 levo) složenost algoritma je \(O(n^2)\).

Grejemov algoritam

U nastavku ćemo razmotriti efikasnije algoritme za nalaženje konveksnog omotača. Započinje se sortiranjem tačaka prema uglovima, slično kao pri konstrukciji prostog mnogougla. Neka je \(P_0\) ekstremna tačka, recimo ona sa najvećom \(x\)-koordinatom (i sa najmanjom \(y\)-koordinatom, ako ima više tačaka sa najvećom \(x\)-koordinatom). Za svaku tačku \(P_i\) iz datog skupa tačaka izračunavamo ugao između prave \(P_0P_i\) i \(x\)-ose, i sortiramo tačke prema veličini ovih uglova (videti primer na slici 7). Tačke koje zahvataju isti ugao sortiramo na osnovu rastojanja od \(P_0\), opadajuće (tako da se prvo obrađuju dalje tačke). Alternativno, moguće je i da izbacimo sve kolinearne tačke osim one koja je najdalja od \(P_0\).

Tačke, dakle, obilazimo redosledom kojim se pojavljuju u (prostom) mnogouglu, i prilikom obilaska pokušavamo da identifikujemo temena konveksnog omotača. Kao i kod uvijanja poklona pamtimo put sastavljen od tačaka koje su obrađene tokom obilaska. Preciznije, to je konveksni put koji određuje konveksni mnogougao (dobijen povezivanjem prve i poslednje tačke puta), koji sadrži sve do sada pregledane tačke. Zbog toga, je u trenutku kad su sve tačke pregledane, konveksni omotač skupa tačaka konstruisan. Osnovna razlika između ovog algoritma i algoritma uvijanja poklona je u činjenici da tekući konveksni put ne mora da bude deo konačnog konveksnog omotača. On određuje konveksni omotač do sada pregledanih tačaka. Dakle tekući konveksni put može da sadrži tačke koje ne pripadaju konačnom konveksnom omotaču; te tačke biće eliminisane kasnije. Na primer, put od \(P_0\) do \(Q_m\) na slici 19 je konveksan, ali tačke \(Q_m\) i \(Q_{m-1}\) očigledno ne pripadaju konveksnom omotaču kompletnog skupa tačaka. Ovo razmatranje sugeriše algoritam zasnovan na sledećoj induktivnoj hipotezi.

Slučaj \(k=1\) je trivijalan (omotač sadrži samo tačku \(P_0\)). Označimo konveksni put dobijen (induktivno) za prvih \(k\) tačaka sa \(P=Q_0, Q_1, \ldots, Q_m\) (pri čemu je \(\{Q_0, \ldots Q_m\} \subseteq \{P_0, \ldots, P_{k-1}\})\). Proširimo induktivnu hipotezu na \(k+1\) tačaka. Posmatrajmo ugao između pravih \(Q_{m-1}Q_m\) i \(Q_{m}P_{k}\) (videti sliku 19).

Ako je taj ugao manji od \(\pi\) (pri čemu se ugao meri iz unutrašnjosti mnogougla), onda se tačka \(P_{k}\) može dodati postojećem putu (novi put je zbog toga takođe konveksan), čime je korak indukcije završen. U protivnom, tvrdimo da tačka \(Q_m\) leži u mnogouglu dobijenom zamenom tačke \(Q_m\) u putu \(P\) tačkom \(P_{k}\), i povezivanjem tačke \(P_{k}\) sa tačkom \(P_0\). Ovo je tačno jer su tačke uređene prema odgovarajućim uglovima, pa se prava \(P_0P_{k}\) nalazi “levo” od prvih \(k\) tačaka. Zbog toga \(Q_m\) jeste unutar gore definisanog mnogougla, može se izbaciti iz puta \(P\), a tačka \(P_{k}\) se može dodati tekućem putu. Da li je time završena obrada \((k+1)\)-ve tačke? Ne mora biti. Nakon izbacivanja tačke \(Q_m\) dobijeni put još ne mora da bude konveksan. Zaista, slika 19 pokazuje da postoje slučajevi kad treba eliminisati još tačaka. Naime, i tačka \(Q_{m-1}\) može da bude unutar mnogougla definisanog modifikovanim putem. Moramo da (unazad) nastavimo sa proverama poslednje dve stranice puta, sve dok ugao između njih ne postane manji od \(\pi\): ovo se uvek mora desiti pre nego što se iscrpu sve tačke, jer će u najgorem slučaju barem tačke \(Q_0\), \(Q_1\) i \(P_k\) činiti konveksni put (zbog prethodnog uređenja tačaka). Put je tada konveksan, a hipoteza je proširena na \(k+1\) tačaka.

Umesto da računamo ugao između pravih \(Q_{m-1}Q_m\) i \(Q_{m}P_{k}\), može se razmatrati orijentacija trojke \(Q_{m-1}Q_mP_k\): ukoliko je orijentacija ovog trougla pozitivna, onda je ugao \(Q_{m-1}Q_mP_k\) manji od \(\pi\), a ako je negativna, taj ugao je veći od \(\pi\). Ako je orijentacija jednaka nuli, tačke \(P_kQ_mQ_{m-1}\) su kolinearne. Na osnovu sortiranja tačaka znamo da tačka \(Q_m\) leži između \(Q_{m-1}\) i \(P_k\), pa se i u tom slučaju \(Q_m\) može zameniti tačkom \(P_k\).

Na slici 20 prikazani su koraci prilikom izvršavanja Grejemovog algoritma na jednom primeru.

Grejemov algoritam je moguće implementirati na sledeći način:

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // trazimo ekstremnu tacku sa maksimalnom x koordinatom,
  // u slucaju da ima vise tacaka sa maksimalnom x koordinatom
  // biramo onu sa najmanjom y koordinatom
  auto max = max_element(begin(tacke), end(tacke),
                         [](const Tacka& t1, const Tacka& t2) {
                           return t1.x < t2.x ||
                                  (t1.x == t2.x && t1.y > t2.y);
                         });
  // dovodimo je na početak niza
  swap(*begin(tacke), *max);
  const Tacka& t0 = tacke[0];

  // sortiramo ostatak niza (tačke sortiramo na osnovu ugla koji
  // zaklapaju u odnosu horizontalnu polupravu koja polazi nadesno
  // iz ekstremne tacke), a kolinearne na osnovu rastojanja te tacke
  sort(next(begin(tacke)), end(tacke),
       [t0](const Tacka& t1, const Tacka& t2) {
         Orijentacija o = orijentacija(t0, t1, t2);
         if (o == KOLINEARNE)
           return kvadratRastojanja(t0, t1) <= kvadratRastojanja(t0, t2);
         return o == POZITIVNA;
       });

  // obradjujemo tacke u sortiranom redosledu izbacujuci prethodne sve
  // dok se tekuca tacka sa dve poslednje ne cini levi zaokret
  vector<Tacka> omotac;
  omotac.push_back(tacke[0]);
  omotac.push_back(tacke[1]);
  for (size_t i = 2; i < tacke.size(); i++) {
    while (omotac.size() >= 2 &&
           orijentacija(omotac[omotac.size()-2],
                        omotac[omotac.size()-1],
                        tacke[i]) != POZITIVNA)
      omotac.pop_back();
    omotac.push_back(tacke[i]);
  }
  return omotac;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
};

enum Orijentacija { POZITIVNA, NEGATIVNA, KOLINEARNE };

Orijentacija orijentacija(const Tacka& t0, const Tacka& t1, const Tacka& t2) {
  long long d = (long long)(t1.x-t0.x)*(long long)(t2.y-t0.y) -
                (long long)(t2.x-t0.x)*(long long)(t1.y-t0.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

long long kvadratRastojanja(const Tacka& t1, const Tacka& t2) {
  long long dx = t1.x - t2.x, dy = t1.y - t2.y;
  return dx*dx + dy*dy;
}

vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // trazimo ekstremnu tacku sa maksimalnom x koordinatom,
  // u slucaju da ima vise tacaka sa maksimalnom x koordinatom
  // biramo onu sa najmanjom y koordinatom
  auto max = max_element(begin(tacke), end(tacke),
                         [](const Tacka& t1, const Tacka& t2) {
                           return t1.x < t2.x ||
                                  (t1.x == t2.x && t1.y > t2.y);
                         });
  // dovodimo je na početak niza
  swap(*begin(tacke), *max);
  const Tacka& t0 = tacke[0];

  // sortiramo ostatak niza (tačke sortiramo na osnovu ugla koji
  // zaklapaju u odnosu horizontalnu polupravu koja polazi nadesno
  // iz ekstremne tacke), a kolinearne na osnovu rastojanja te tacke
  sort(next(begin(tacke)), end(tacke),
       [t0](const Tacka& t1, const Tacka& t2) {
         Orijentacija o = orijentacija(t0, t1, t2);
         if (o == KOLINEARNE)
           return kvadratRastojanja(t0, t1) <= kvadratRastojanja(t0, t2);
         return o == POZITIVNA;
       });

  // obradjujemo tacke u sortiranom redosledu izbacujuci prethodne sve
  // dok se tekuca tacka sa dve poslednje ne cini levi zaokret
  vector<Tacka> omotac;
  omotac.push_back(tacke[0]);
  omotac.push_back(tacke[1]);
  for (size_t i = 2; i < tacke.size(); i++) {
    while (omotac.size() >= 2 &&
           orijentacija(omotac[omotac.size()-2],
                        omotac[omotac.size()-1],
                        tacke[i]) != POZITIVNA)
      omotac.pop_back();
    omotac.push_back(tacke[i]);
  }
  return omotac;
}


int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;
  vector<Tacka> omotac = konveksniOmotac(tacke);
  cout << omotac.size() << endl;
  for (const Tacka& t : omotac)
    cout << t.x << " " << t.y << endl;
  return 0;
}

Glavni deo složenosti Grejemovog algoritma potiče od početnog sortiranja. Ostatak algoritma izvršava se za vreme \(O(n)\). Svaka tačka skupa razmatra se tačno jednom u induktivnom koraku kao \(P_{k}\). U tom trenutku tačka se uvek dodaje konveksnom putu. Ista tačka biće razmatrana i kasnije (možda čak i više nego jednom) da bi se proverila njena pripadnost konveksnom putu. Broj tačaka na koje se primenjuje ovakav povratni test može biti veliki, ali se sve one, sem dve (tekuća tačka i tačka za koju se ispostavlja da dalje pripada konveksnom putu) eliminišu, a tačka može biti eliminisana samo jednom! Prema tome, troši se najviše konstantno vreme za eliminaciju svake tačke i konstantno vreme za njeno dodavanje, te je ukupna složenost ove faze \(O(n)\). Zbog početnog sortiranja tačaka vreme izvršavanja kompletnog algoritma iznosi \(O(n\log n)\).

Brzi algoritam za traženje konveksnog omotača

Pokušajmo da isti problem rešimo tehnikom dekompozicije, nalik algoritmu brzog sortiranja (QuickSort). Odredimo tačke iz datog skupa sa minimalnom i maksimalnom \(x\) koordinatom (ako ima više takvih onda biramo onu sa minimalnom ili maksimalnom \(y\) koordinatom): neka su to tačke \(P_i\) i \(P_j\). Obe ove tačke su ekstremne i kao takve sigurno pripadaju konveksnom omotaču. Duž \(P_iP_j\) deli skup tačaka na dva podskupa: svaki od podskupova čine tačke koje se nalaze sa iste strane te duži. Razmotrimo jedan od ova dva podskupa: u njemu tražimo tačku na maksimalnom rastojanju od duži \(P_iP_j\): neka je to tačka \(P_k\). I ona sigurno pripada konveksnom omotaču. Tačke iz skupa koje pripadaju trouglu \(P_iP_jP_k\) ne mogu biti deo konveksnog omotača i ne moraju se dalje razmatrati. Prethodno razmatranje sada možemo primeniti na dve nove duži koje formiraju trougao: \(P_iP_k\) i \(P_kP_j\): tražimo najudaljeniju tačku od duži \(P_iP_k\) sa one strane prave \(P_iP_k\) sa koje nije \(P_j\) i, slično, najudaljeniju tačku od duži \(P_kP_j\) sa one strane prave \(P_kP_j\) sa koje nije tačka \(P_i\). Sa postupkom nastavljamo sve dok na raspolaganju ima još tačaka. Tačke koje su tokom izvršavanja algoritma birane kao najudaljenije pripadaju konveksnom omotaču. Na ovaj način došli smo do tzv. brzog algoritma za određivanje konveksnog omotača (engl. QuickHull algorithm).

Napomenimo da prilikom traženja najudaljenije tačke \(P_k\) od duži \(P_iP_j\), nije neophodno računati tačno rastojanje po formuli:

\[d=\frac{|\overrightarrow{P_kP_i}\times \overrightarrow{P_kP_j}|}{|\overrightarrow{P_iP_j}|}\]

Naime, mi tražimo najudaljeniju tačku od prave kroz fiksirane dve tačke, te će imenilac ovog razlomka uvek biti isti. Stoga se mera rastojanja ovde može računati po formuli \(d=|\overrightarrow{P_kP_i}\times \overrightarrow{P_kP_j}|\).

U nastavku je prikazana C++ implementacija ovog algoritma. Tokom rekurzivnih poziva održava se skup temena konveksnog omotača, da bi se nakon prikupljanja svih temena ona sortirala tako da uzastopna temena idu jedno iza drugog (to se postiže tako što se neka od ekstremnih tačaka, u ovom slučaju ona sa maksimalnom \(x\)-koordinatom stavi na početak, a zatim se ostale tačke sortiraju po uglu u odnosu na nju). Pošto je osnovni algoritam takav da je moguće da su u izgrađenom omotaču neka tri temena kolinearna, nakon formiranja omotača vršimo njegovo uprošćavanje zadržavajući samo krajnja temena u nizu kolinearnih temena.

// funkcija koja racuna konveksni omotac skupa tacaka
vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // funkcija poredjenja koja je potrebna za bibliotecke funkcije
  // min_element i max_element
  auto porediKoordinate =
    [](const Tacka& A, const Tacka& B) {
      return (A.x < B.x) || (A.x == B.x && A.y > B.y);
    };
  
  // trazimo tacke sa najmanjom i najvecom x koordinatom
  int min = distance(tacke.begin(),
                     min_element(tacke.begin(), tacke.end(), porediKoordinate));
  int max = distance(tacke.begin(),
                     max_element(tacke.begin(), tacke.end(), porediKoordinate));
  
  // skup temena omotaca 
  set<Tacka> temena;
  
  // rekurzivno trazimo konveksne omotace tacaka sa jedne strane
  // duzi odredjene tackama tacka[min] i tacka[max]
  vector<Tacka> iznad = izdvojOrijentaciju(tacke, tacke[min], tacke[max], POZITIVNA);
  konveksniPoluomotac(iznad, tacke[min], tacke[max], temena);
  // i sa druge strane
  vector<Tacka> ispod = izdvojOrijentaciju(tacke, tacke[min], tacke[max], NEGATIVNA);
  konveksniPoluomotac(ispod, tacke[min], tacke[max], temena);

  // prebacujemo tacke iz skupa u vektor i soritramo ga po uglovima
  vector<Tacka> omotac(temena.begin(), temena.end());
  const Tacka& maxTacka = tacke[max];
  auto porediUgao =
    [maxTacka](const Tacka& A, const Tacka& B) {
      if (A == maxTacka) return true;
      if (B == maxTacka) return false;
      return orijentacija(maxTacka, A, B) == POZITIVNA;
    };
  sort(begin(omotac), end(omotac), porediUgao);

  // eliminisemo susedne kolinearne tacke
  vector<Tacka> omotacBezKolinearnih;
  for (int i = 0; i < omotac.size(); i++) {
    int prethodna = i == 0 ? omotac.size() - 1 : i-1;
    int sledeca = i == omotac.size() - 1 ? 0 : i + 1;
    if (orijentacija(omotac[prethodna], omotac[i], omotac[sledeca]) !=
        KOLINEARNE)
      omotacBezKolinearnih.push_back(omotac[i]);
  }
  
  return omotacBezKolinearnih;
}

// trazimo konveksni omotac tacaka sa jedne strane duzi PQ
// i dodajemo ih u skup temena konveksnog omotaca
void konveksniPoluomotac(const vector<Tacka>& tacke, const Tacka& P, const Tacka& Q,
                         set<Tacka>& temena) {
  // dodajemo tacke P i Q u omotac
  temena.insert(P);
  temena.insert(Q);

  // ako ne postoji tacka sa date strane prave PQ zavrsavamo postupak
  if (tacke.empty())
    return;
  
  // trazimo tacku sa date strane duzi PQ
  // koja je na najvecem rastojanju od prave PQ
  
  // pozicija najdalje tacke i njeno rastojanje od prave PQ
  int iMax = -1; long long dMax = 0;
  for (int i = 0; i < tacke.size(); i++) {
    long long di = rastojanjeOdPrave(P, Q, tacke[i]);
    if (di > dMax) {
      iMax = i;
      dMax = di;
    }
  }
  // najdalja tacka
  const Tacka& M = tacke[iMax];

  // rekurzivno pozivamo za dva podskupa dobijena tackom `tacke[iMax]`
  
  // analiziramo tacke koje su na suprotnoj strani prave MP u odnosu na Q
  vector<Tacka> suprotnoOdQ = izdvojOrijentaciju(tacke, M, P, -orijentacija(M, P, Q));
  konveksniPoluomotac(suprotnoOdQ, M, P, temena);

  // analiziramo tacke koje su na suprotnoj strani prave MQ u odnosu na P
  vector<Tacka> suprotnoOdP = izdvojOrijentaciju(tacke, M, Q, -orijentacija(M, Q, P));
  konveksniPoluomotac(suprotnoOdP, M, Q, temena);
}

// funkcija koja vraca vrednost koja je proporcionalna rastojanju
// od tacke A do prave odredjene tackama P i Q
long long rastojanjeOdPrave(Tacka P, Tacka Q, Tacka A) {
  return abs((long long)(A.y - P.y) * (long long)(Q.x - P.x) -
             (long long)(Q.y - P.y) * (long long)(A.x - P.x));
}

// izdvaja sve tacke T iz vektora tacke takve da je orijentacija P Q T jednaka o
vector<Tacka> izdvojOrijentaciju(const vector<Tacka>& tacke, const Tacka& P, const Tacka& Q,
                                 int o) {
  vector<Tacka> rezultat;
  for (const Tacka& T : tacke)
    if (orijentacija(P, Q, T) == o)
      rezultat.push_back(T);
  return rezultat;
}

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  int x, y;
  bool operator==(const Tacka& druga) const {
    return x == druga.x && y == druga.y;
  }
};

// posto cemo konveksni omotac pamtiti u vidu skupa tacaka
// neophodno je da definisemo operator < za dve tacke
bool operator<(const Tacka& A, const Tacka&B){
  return A.x < B.x || (A.x == B.x && A.y < B.y);
}

// racuna se kvadrat rastojanja izmedju tacaka A i B
long long kvadratRastojanja(Tacka A, Tacka B) {
  long long dx = A.x - B.x, dy = A.y - B.y;
  return dx*dx + dy*dy;
}

enum Orijentacija { POZITIVNA=1, NEGATIVNA=-1, KOLINEARNE=0 };

// orijentacija uredjene trojke tacaka P,Q i R 
int orijentacija(Tacka P, Tacka Q, Tacka R){
  long long d = (long long)(Q.y - P.y) * (long long)(R.x - Q.x) -
                (long long)(Q.x - P.x) * (long long)(R.y - Q.y);
  if (d == 0)
    return KOLINEARNE;
  else if (d > 0)
    return NEGATIVNA;
  else
    return POZITIVNA;
}

// funkcija koja vraca vrednost koja je proporcionalna rastojanju
// od tacke A do prave odredjene tackama P i Q
long long rastojanjeOdPrave(Tacka P, Tacka Q, Tacka A) {
  return abs((long long)(A.y - P.y) * (long long)(Q.x - P.x) -
             (long long)(Q.y - P.y) * (long long)(A.x - P.x));
}

// izdvaja sve tacke T iz vektora tacke takve da je orijentacija P Q T jednaka o
vector<Tacka> izdvojOrijentaciju(const vector<Tacka>& tacke, const Tacka& P, const Tacka& Q,
                                 int o) {
  vector<Tacka> rezultat;
  for (const Tacka& T : tacke)
    if (orijentacija(P, Q, T) == o)
      rezultat.push_back(T);
  return rezultat;
}

// trazimo konveksni omotac tacaka sa jedne strane duzi PQ
// i dodajemo ih u skup temena konveksnog omotaca
void konveksniPoluomotac(const vector<Tacka>& tacke, const Tacka& P, const Tacka& Q,
                         set<Tacka>& temena) {
  // dodajemo tacke P i Q u omotac
  temena.insert(P);
  temena.insert(Q);

  // ako ne postoji tacka sa date strane prave PQ zavrsavamo postupak
  if (tacke.empty())
    return;
  
  // trazimo tacku sa date strane duzi PQ
  // koja je na najvecem rastojanju od prave PQ
  
  // pozicija najdalje tacke i njeno rastojanje od prave PQ
  int iMax = -1; long long dMax = 0;
  for (int i = 0; i < tacke.size(); i++) {
    long long di = rastojanjeOdPrave(P, Q, tacke[i]);
    if (di > dMax) {
      iMax = i;
      dMax = di;
    }
  }
  // najdalja tacka
  const Tacka& M = tacke[iMax];

  // rekurzivno pozivamo za dva podskupa dobijena tackom `tacke[iMax]`
  
  // analiziramo tacke koje su na suprotnoj strani prave MP u odnosu na Q
  vector<Tacka> suprotnoOdQ = izdvojOrijentaciju(tacke, M, P, -orijentacija(M, P, Q));
  konveksniPoluomotac(suprotnoOdQ, M, P, temena);

  // analiziramo tacke koje su na suprotnoj strani prave MQ u odnosu na P
  vector<Tacka> suprotnoOdP = izdvojOrijentaciju(tacke, M, Q, -orijentacija(M, Q, P));
  konveksniPoluomotac(suprotnoOdP, M, Q, temena);
}

// funkcija koja racuna konveksni omotac skupa tacaka
vector<Tacka> konveksniOmotac(vector<Tacka>& tacke) {
  // funkcija poredjenja koja je potrebna za bibliotecke funkcije
  // min_element i max_element
  auto porediKoordinate =
    [](const Tacka& A, const Tacka& B) {
      return (A.x < B.x) || (A.x == B.x && A.y > B.y);
    };
  
  // trazimo tacke sa najmanjom i najvecom x koordinatom
  int min = distance(tacke.begin(),
                     min_element(tacke.begin(), tacke.end(), porediKoordinate));
  int max = distance(tacke.begin(),
                     max_element(tacke.begin(), tacke.end(), porediKoordinate));
  
  // skup temena omotaca 
  set<Tacka> temena;
  
  // rekurzivno trazimo konveksne omotace tacaka sa jedne strane
  // duzi odredjene tackama tacka[min] i tacka[max]
  vector<Tacka> iznad = izdvojOrijentaciju(tacke, tacke[min], tacke[max], POZITIVNA);
  konveksniPoluomotac(iznad, tacke[min], tacke[max], temena);
  // i sa druge strane
  vector<Tacka> ispod = izdvojOrijentaciju(tacke, tacke[min], tacke[max], NEGATIVNA);
  konveksniPoluomotac(ispod, tacke[min], tacke[max], temena);

  // prebacujemo tacke iz skupa u vektor i soritramo ga po uglovima
  vector<Tacka> omotac(temena.begin(), temena.end());
  const Tacka& maxTacka = tacke[max];
  auto porediUgao =
    [maxTacka](const Tacka& A, const Tacka& B) {
      if (A == maxTacka) return true;
      if (B == maxTacka) return false;
      return orijentacija(maxTacka, A, B) == POZITIVNA;
    };
  sort(begin(omotac), end(omotac), porediUgao);

  // eliminisemo susedne kolinearne tacke
  vector<Tacka> omotacBezKolinearnih;
  for (int i = 0; i < omotac.size(); i++) {
    int prethodna = i == 0 ? omotac.size() - 1 : i-1;
    int sledeca = i == omotac.size() - 1 ? 0 : i + 1;
    if (orijentacija(omotac[prethodna], omotac[i], omotac[sledeca]) !=
        KOLINEARNE)
      omotacBezKolinearnih.push_back(omotac[i]);
  }
  
  return omotacBezKolinearnih;
}

int main() {
  int n;
  cin >> n;
  vector<Tacka> tacke(n);
  for (int i = 0; i < n; i++)
    cin >> tacke[i].x >> tacke[i].y;
  vector<Tacka> omotac = konveksniOmotac(tacke);
  cout << omotac.size() << endl;
  for (const Tacka& t : omotac)
    cout << t.x << " " << t.y << endl;
  return 0;
}

Složenost ovog algoritma može se opisati rekurentnom jednačinom oblika \(T(n)=T(k)+T(n-k-1)+O(n)\), gde je sa \(k\) označena veličina jednog, a sa \(n-k-1\) veličina drugog problema na koji se vrši podela (nalik algoritmu QuickSort). U najboljem slučaju problem se uvek deli na dva potproblema iste dimenzije pa dobijamo rekurentnu jednačinu \(T(n)=2T(n/2)+O(n)\), čije je rešenje \(T(n)=O(n\log n)\). U najgorem slučaju dobijamo rekurentnu jednačinu oblika \(T(n)=T(n-1)+O(n)\) čije rešenje zadovoljava jednačinu \(T(n)=O(n^2)\). Ovo odgovara složenosti algoritma QuickSort i moguće je dokazati da je prosečna složenost ovog algoritma jednaka \(O(n \log{n})\).