Osnove geometrijskih algoritama

Svi objekti se u računaru predstavljaju brojevima (koordinatama, koeficijentima i slično). Pretpostavlja se da je čitalac upoznat sa osnovama analitičke geometrije. Ipak, u nastavku ćemo rezimirati neke osnovne pojmove korisne prilikom konstrukcije geometrijskih algoritama, pri čemu ćemo većinu operacija zasnovati na vektorima i operacijama sa njima (alternativno, u tradicionalnoj analitičkoj geometriji se geometrijski objekti obično predstavljaju implicitnim jednačinama). Bavićemo se pitanjima poput izračunavanja rastojanja između dve tačke, ispitivanja kolinearnosti tri tačke ili izračunavanja presečne tačke dveju duži. Sve ove operacije mogu se izvesti algoritmima konstantne vremenske složenosti, korišćenjem osnovnih aritmetičkih operacija. Pretpostavljamo i da se različite elementarne funkcije (kvadratni koren, trigonometrijske funkcije i slično) mogu izračunati za konstantno vreme, ali, pošto je njihovo izvršavanje sporije od elementarnih računskih operacija, treba ih izbegavati kada god je to moguće.

10.1.1 Tačke, koordinate

Osnovni geometrijski objekti su tačke i većina drugih objekata se predstavlja pomoću tačaka.

Dekartove koordinate

Tačke se u računaru najčešće predstavljaju svojim Dekartovim koordinatama. Tačke u ravni se predstavljaju parom Dekartovih koordinata \((x, y)\), a tačke u trodimenzionom prostoru trojkom Dekartovih koordinata \((x, y, z)\). U zavisnosti od primene, koordinate su najčešće ili celobrojne ili realne (u računaru najčešće predstavljene brojevima u pokretnom zarezu).

Tačke se mogu predstaviti ili strukturnim tipom ili ugrađenim tipom za predstavljanje uređenih parova. Na primer, tačke u ravni sa celobrojnim koordinatama mogu se predstaviti na bilo koji od sledeća dva načina.

Naravno, umesto tipa int mogu se koristiti i drugi tipovi za predstavljanje koordinata (npr. long long, float, double itd.).

Polarne koordinate

U nekim algoritmima je pogodnija reprezentacija tačaka pomoću njihovih polarnih koordinata. Zbog toga je za date Dekartove koordinate \(x\) i \(y\) tačke \(T\) ponekad potrebno odrediti njene polarne koordinate: rastojanje \(r\) od koordinatnog početka \(P\) i ugao \(\phi\) koji duž \(PT\) zahvata sa pozitivnim delom \(x\) ose i, obratno, na osnovu polarnih koordinata odrediti Dekartove. Ugao se često razmatra kao orijentisani ugao iz intervala \((-\pi, \pi]\) ili \([0, 2\pi)\), gde ugao \(0\) predstavlja pozitivan smer \(x\) ose i ugao raste u pozitivnom matematičkom smeru.

Da bismo transformisali polarne koordinate u Dekartove, možemo iskoristiti sledeću vezu (slika 1):

Za transformaciju Dekartovih koordinata u polarne u većini slučajeva možemo iskoristiti naredne jednačine:

\[\begin{eqnarray*} r&=&\sqrt{x^2+y^2}\\ \phi&=&\arctan \frac{y}{x} \end{eqnarray*}\]

Treba obratiti pažnju na to da prethodne formule nisu uvek ispravne, jer vrednost \(\arctan \frac{y}{x}\) nije definisana za tačke kod kojih je \(x=0\), tj. za tačke na \(y\)-osi, kao i da je vrednost funkcije \(\arctan\) uvek u intervalu \((-\pi/2, \pi/2]\), a ne u intervalu \((-\pi, \pi]\) (ili u intervalu \([0, 2\pi)\)), kako bismo želeli. Zbog toga se umesto funkcije \(\mathrm{atan}\) definiše i koristi funkcija \(\mathrm{atan2}\), koja ima dva argumenta — \(y\) i \(x\) koordinatu tačke čiji se polarni ugao izračunava kao \(\phi = \mathrm{atan2}(y, x)\) (obratiti pažnju na redosled argumenata). Ova funkcija je direktno podržana u većini programskih jezika i vraća ugao iz intervala \((-\pi, \pi]\).

\[\begin{align*} \mathrm{atan2}(y, x) = \begin{cases} \arctan\left(\frac{y}{x}\right) & \text{za } x > 0 \\ \arctan\left(\frac{y}{x}\right) + \pi & \text{za } x < 0 \text{ i } y \geq 0 \\ \arctan\left(\frac{y}{x}\right) - \pi & \text{za } x < 0 \text{ i } y < 0 \\ +\frac{\pi}{2} & \text{za } x = 0 \text{ i } y > 0 \\ -\frac{\pi}{2} & \text{za } x = 0 \text{ i } y < 0 \\ \text{nedefinisano} & \text{za } x = 0 \text{ i } y = 0 \\ \end{cases} \end{align*}\]

10.1.2 Vektori

Pored tačaka, osnovni pojam analitičke geometrije predstavljaju vektori koji se predstavljaju usmerenim dužima. Usmerena duž koja ima početnu tačku \(A\) i krajnju tačku \(B\) određuje vektor \(\overrightarrow{AB}\). Svi drugi parovi tačaka \(\overrightarrow{A'B'}\) takvih da postoji translacija kojom se \(\overrightarrow{AB}\) preslikava u \(\overrightarrow{A'B'}\) određuju isti vektor. Ako su početna i krajnja tačka vektora jednake, one određuju tzv. nula-vektor (govorićemo i da je u pitanju vektor jednak nuli).

Vektori se mogu sabirati i skalirati (množiti brojem, tj. skalarom). Izraz \(\vec{a} + \vec{b}\) označava zbir vektora \(\vec{a}\) i \(\vec{b}\), dok izraz \(k\cdot \vec{a}\) označava skaliranje vektora \(\vec{a}\) skalarom \(k\). Vektori se mogu i oduzimati. Razlika vektora \(\vec{a}\) i \(\vec{b}\) se definiše kao \(\vec{a} - \vec{b} = \vec{a} + (-1)\cdot \vec{b}\). Sabiranje i skaliranje imaju svoju geometrijsku interpretaciju (slika 2).

Vektori se najčešće predstavljaju analitički, svojim Dekartovim koordinatama (parom koordinata za vektore u ravni i trojkom koordinata za vektore u prostoru). Svaki vektor u ravni se može jednoznačno izraziti kao linearna kombinacija proizvoljna dva nekolinearna jedinična vektora \(\vec{i}\) i \(\vec{j}\), tj. za svaki vektor \(\vec{a}\) postoje brojevi \(x\) i \(y\) takvi da je \(\vec{a} = x\cdot \vec{i} + y \cdot \vec{j}\). Brojevi \((x, y)\) predstavljaju koordinate vektora \(\vec{a}\). Dekartov koordinatni sistem je određen međusobno normalnim jediničnim vektorima \(\vec{i}\) i \(\vec{j}\) i koordinatnim početkom \(O\) i u nastavku ćemo uvek podrazumevati da radimo sa ovakvim koordinatnim sistemom.

Sabiranje i skaliranje vektora se lako izražavaju analitički. Zbir vektora \(\vec{a} = (a_x, a_y)\) i \(\vec{b} = (b_x, b_y)\) je vektor \(\vec{a} + \vec{b} = (a_x + b_x, a_y + b_y)\). Proizvod vektora \(\vec{a} = (a_x, a_y)\) i skalara \(k\) je vektor \(k\cdot \vec{a} = (ka_x, ka_y)\).

Koordinate bilo koje tačke \(A\) su zapravo koordinate vektora \(\overrightarrow{OA}\).

10.1.3 Skalarni proizvod

Skalarni proizvod \(\vec{a} \circ \vec{b}\) vektora \(\vec{a}\) i \(\vec{b}\) je skalar (broj):

gde je sa \(|\vec{v}|\) označen intenzitet vektora \(\vec{v}\), a sa \(\phi\) konveksni ugao (manji ili jednak \(\pi\)) koji obrazuju vektori \(\vec{a}\) i \(\vec{b}\). Jednostavno se dokazuje da skalarni proizvod ima sledeće osobine:

\[\begin{eqnarray*} \vec{a} \circ \vec{b} = \vec{b} \circ \vec{a}&& \mathrm{simetričnost}\\ \vec{a}\circ (\vec{b}_1 + \vec{b}_2) = \vec{a}\circ\vec{b}_1 + \vec{a}\circ\vec{b}_1&&\mathrm{desna\ distributivnost}\\ (\vec{a}_1 + \vec{a}_2)\circ \vec{b} = \vec{a}_1\circ\vec{b} + \vec{a}_2\circ\vec{b}&&\mathrm{leva\ distributivnost}\\ \vec{a}\circ \vec{a} \geq 0 && \mathrm{nenegativnost}\\ \vec{a}\circ \vec{a} = 0 \Leftrightarrow \vec{a}=\vec{0} && \mathrm{pozitivna\ definitnost}\\ (k\cdot\vec{a})\circ \vec{b}=\vec{a}\circ(k\cdot \vec{b}) = k\cdot (\vec{a}\circ \vec{b})&&\mathrm{odnos\ sa\ skaliranjem} \end{eqnarray*}\]

Ako umemo da izračunamo skalarni proizvod proizvoljna dva vektora, jednostavno je izračunati:

Specijalno, skalarni proizvod dva vektora različita od nule je nula ako i samo ako je \(\cos{\phi} = 0\), pa se skalarni proizvod može koristiti i za proveru da li su vektori međusobno normalni (pri čemu treba biti obazriv ako se radi sa brojevima zapisanim u pokretnom zarezu, jer se usled numeričkih grešaka može dobiti vrednost bliska, ali ne i jednaka nuli iako su vektori međusobno normalni). Negativna vrednost skalarnog proizvoda ukazuje na to da je manji (konveksni) ugao između vektora tup, a pozitivna da je taj ugao oštar.

Skalarni proizvod se lako izračunava analitički, kada su vektori zadati koordinatama u Dekartovom koordinatnom sistemu.. Naime, ako su dva vektora \(\vec{a}(a_1,\ldots,a_n)\) i \(\vec{b}(b_1,\ldots,b_n)\) iste dimenzije, njihov skalarni proizvod je skalar čiju vrednost računamo po formuli:

Ovo se veoma jednostavno može dokazati izražavanjem vektora \(\vec{a}\) i \(\vec{b}\) preko svojih koordinata i korišćenjem osnovnih osobina skalarnog proizvoda.

Ukoliko su koordinate vektora \(\vec{a}\) i \(\vec{b}\) celobrojne, i vrednost skalarnog proizvoda je celobrojna.

U daljem tekstu ćemo razmatrati vektore određene tačkama u ravni, te će dimenzija vektora biti jednaka \(2\). Skalarni proizvod vektora \(\vec{a}(a_x, a_y)\) i vektora \(\vec{b}(b_x,b_y)\) dimenzije \(2\) jednak je \(\vec{a}\circ \vec{b}=a_x\cdot b_x+a_y\cdot b_y\).

Projekcija vektora na pravac vektora

Analitičko izračunavanje skalarnog proizvoda podrazumeva korišćenje koordinata vektora, koje su zapravo određene projekcijom vektora na koordinatne ose. Umesto toga, moguće je odrediti projekciju jednog vektora na pravac drugog. Time se dobijaju dva kolinearna vektora čiji se skalarni proizvod dobija množenjem njihovih intenziteta (vodeći računa o znaku).

Na slici 3, tačka \(B_p\) je projekcija tačke \(B\) (krajnje tačke vektora \(\overrightarrow{OB}\)) na pravac vektora \(\overrightarrow{OA}\). Dužina \(OB_p\) je jednaka apsolutnoj vrednosti izraza \(|\overrightarrow{OB}|\cos{\phi}\) (gde je \(\phi\) konveksni ugao između vektora \(\overrightarrow{OA}\) i \(\overrightarrow{OB}\)), pri čemu negativan znak tog izraza ukazuje na to da je vektor \(\overrightarrow{OB_p}\) suprotno usmeren od vektora \(\overrightarrow{OA}\), a pozitivan znak na to da su ta dva vektora isto usmerena.

Projekcija pomaže i da se vrednost skalarnog proizvoda vizualizuje. Apsolutna vrednost skalarnog proizvoda \(\overrightarrow{OA} \circ \overrightarrow{OB} = |\overrightarrow{OA}| |\overrightarrow{OB}| \cos{\phi}\) jednaka je proizvodu dužina \(OB_p\) i \(OA\) (pri čemu je znak skalarnog proizvoda negativan ako su vektori \(\overrightarrow{OB_p}\) i \(\overrightarrow{OA}\) suprotno usmereni, a pozitivan ako su isto usmereni). Da bismo vizuelno predstavili apsolutnu vrednost skalarnog proizvoda, vektor \(\overrightarrow{OA}\) rotiramo za \(90^\circ\) tj. \(\frac{\pi}{2}\) radijana, čime se dobija vektor \(\overrightarrow{OA'}\), koji sa vektorom \(\overrightarrow{OB_p}\) gradi pravougaonik (prikazan plavom bojom na slici 3) čija je površina jednaka apsolutnoj vrednosti skalarnog proizvoda.

Naravno, pošto je sve simetrično, moguće je projektovati tačku \(A\) na pravac vektora \(\overrightarrow{OB}\).

Projekcija tačke na pravu

Videli smo da je skalarni proizvod u tesnoj vezi sa projekcijom tačke na pravu, tj. na pravac jednog od vektora koji se množe. Stoga se ta projekcija veoma jednostavno određuje korišćenjem skalarnog proizvoda.

Za tačku \(M_p\) važi \(M_p = A + \overrightarrow{AM_p}\). Vektor \(\overrightarrow{AM_p}\) kolinearan je sa vektorom \(\overrightarrow{AB}\), a dužina vektora \(\overrightarrow{AM_p}\) jednaka je apsolutnoj vrednosti izraza \(|AM|\cos\phi\) (gde je \(\phi\) ugao između vektora \(\overrightarrow{AB}\) i \(\overrightarrow{AM}\)). Vrednost skalarnog proizvoda vektora \(\overrightarrow{AB}\) i \(\overrightarrow{AM}\) jednaka je \(|AB||AM|\cos\phi\), pa je dužina vektora \(\overrightarrow{AM_p}\) jednaka apsolutnoj vrednosti izraza

pri čemu znak ove vrednosti govori o tome da li su vektori \(\overrightarrow{AB}\) i \(\overrightarrow{AM_p}\) isto ili suprotno usmereni. Vektor \(\overrightarrow{AM_p}\) se može dobiti tako što se jedinični vektor \(\frac{\overrightarrow{AB}}{|\overrightarrow{AB}|}\) pomnoži ovim koeficijentom. Zato je

\[M_p = A + \overrightarrow{AM_p} = A + \frac{\overrightarrow{AB} \circ \overrightarrow{AM}}{|\overrightarrow{AB}|^2}\overrightarrow{AB}.\]

Naglasimo da se ova formula može koristiti i za tačke u ravni i za tačke u prostoru.

10.1.4 Vektorski proizvod

Vektorski proizvod vektora \(\vec{a}(a_x,a_y,a_z)\) i \(\vec{b}(b_x,b_y,b_z)\) dimenzije \(3\) je vektor upravan na ravan određenu vektorima \(\vec{a}\) i \(\vec{b}\), čiji je smer određen pravilom desne ruke (slika 5), a intenzitet jednak površini paralelograma koji određuju vektori \(\vec{a}\) i \(\vec{b}\), odnosno može se izračunati korišćenjem formule

gde je sa \(\phi\) označen manji od uglova koji obrazuju vektori \(\vec{a}\) i \(\vec{b}\) (tj. konveksni ugao, čiji je sinus uvek pozitivan).

\[\begin{eqnarray*} \vec{a}\times \vec{b} = -\vec{b}\times\vec{a}&&\mathrm{antikomutativnost}\\ \vec{a}\times (\vec{b}_1 + \vec{b}_2) = \vec{a}\times\vec{b}_1 + \vec{a}\times\vec{b}_1&&\mathrm{desna\ distributivnost}\\ (\vec{a}_1 + \vec{a}_2)\times \vec{b} = \vec{a}_1\times\vec{b} + \vec{a}_2\times\vec{b}&&\mathrm{leva\ distributivnost}\\ \vec{a}\times \vec{a} = 0&&\mathrm{samoproizvod}\\ (k\cdot\vec{a})\times \vec{b}=\vec{a}\times(k\cdot \vec{b}) = k\cdot (\vec{a}\times \vec{b})&&\mathrm{odnos\ sa\ skaliranjem} \end{eqnarray*}\]

Naglasimo i da nam skalarni proizvod daje način da lako odredimo kosinus ugla između dva vektora, a odatle i veličinu konveksnog ugla između njih. Sa druge strane, iz vektorskog proizvoda se lako određuje sinus ugla između dva vektora, međutim, vrednost sinusa nije dovoljna da se lako odredi konveksni ugao (jer istu vrednost sinusa daju jedan oštar i jedan tup ugao). Stoga se za određivanje veličine konveksnog ugla između dva vektora koristi skalarni, a ne vektorski proizvod.

\[\begin{eqnarray*} \vec{a}&=&a_x\cdot \vec{i}+a_y\cdot \vec{j}+a_z\cdot \vec{k} \\ \vec{b}&=&b_x\cdot \vec{i}+b_y\cdot \vec{j}+b_z\cdot \vec{k} \end{eqnarray*}\]

gde su sa \(\vec{i}\), \(\vec{j}\) i \(\vec{k}\) označeni međusobno normalni jedinični vektori u smeru \(x\), \(y\) i \(z\) koordinatne ose, i istovremeno je:

\[\begin{eqnarray*} \vec{i}\times \vec{j}=\vec{k}=-\vec{j}\times \vec{i} \\ \vec{j}\times \vec{k}=\vec{i}=-\vec{k}\times \vec{j} \\ \vec{k}\times \vec{i}=\vec{j}=-\vec{i}\times \vec{k} \end{eqnarray*}\]

\[\vec{a}\times \vec{b} = (a_yb_z-a_zb_y)\vec{i}+(a_zb_x-a_xb_z)\vec{j}+(a_xb_y-a_yb_x)\vec{k}\]

\[\vec{a}\times \vec{b} = \begin{vmatrix} \vec{i} & \vec{j} & \vec{k} \\ a_x & a_y & a_z \\ b_x & b_y & b_z \end{vmatrix}\]

u čijoj se prvoj vrsti nalaze jedinični vektori u smeru \(x\), \(y\) i \(z\) ose, u drugoj vrsti koordinate vektora \(\vec{a}\), a u trećoj koordinate vektora \(\vec{b}\). Ukoliko su koordinate vektora \(\vec{a}\) i \(\vec{b}\) celobrojne, i koordinate vektora \(\vec{a}\times \vec{b}\) su celobrojne.

Dvodimenzionalni vektorski proizvod

Vektorski proizvod je definisan samo za vektore u trodimenzionom prostoru. Ipak, i vektori u ravni se mogu vektorski množiti ako se ravan \(xOy\) utopi u trodimenzioni prostor. Time se koordinate svakog od dva vektora ravni prošire nulom (\(z\) koordinata tih vektora je nula) i izvrši se vektorsko množenje. Rezultat je vektor koji je upravan na ravan \(xOy\), tj. vektor čije su prve dve koordinate jednake nuli. Zaista

\[\vec{a}\times \vec{b} = \begin{vmatrix} \vec{i} & \vec{j} & \vec{k} \\ a_x & a_y & 0 \\ b_x & b_y & 0 \end{vmatrix} = (0, 0, a_xb_y-a_yb_x).\]

U ovom slučaju nam je jedino značajna \(z\) koordinata vektorskog proizvoda. Stoga se vektorski proizvod dva ravanska vektora \(\vec{a} = (a_x, a_y)\) i \(\vec{b} = (b_x, b_y)\) poistovećuje sa skalarom \(a_xb_y - a_yb_x\) (što može biti zbunjuće, jer nazivi skalarni i vektorski proizvod potiču od toga što je u prvom slučaju rezultat množenja skalar, a u drugom vektor). Da bismo izbegli zabunu, naglašavaćemo uvek da je u pitanju množenje dvodimenzionalnih vektora (tj. dvodimenzionalni vektorski proizvod¹) i umesto oznake \(\times\) koristićemo oznaku \(\times_{2d}\). Dakle, za dvodimenzionalne vektore \(\vec{a} = (a_x, a_y)\) i \(\vec{b}=(b_x, b_y)\) definišemo da je:

Ako dvodimenzionalni vektori obrazuju ugao \(\phi\), vrednost dvodimenzionalnog vektorskog proizvoda \(\vec{a}\times_{2d}\vec{b}\) jednaka je \(|\vec{a}|\cdot |\vec{b}|\cdot \sin{\phi}\).

Vrednost \(\vec{a}\times_{2d}\vec{b}=0\) nam govori da su vektori \(\vec{a}\) i \(\vec{b}\) kolinearni, tj. da je ugao koji obrazuju \(0\) ili \(\pi\) i to se obično koristi kao potreban i dovoljan uslov za ispitivanje kolinearnosti vektora. Zaista, pošto je \(\vec{a} \times_{2d} \vec{b} = |\vec{a}|\cdot|\vec{b}|\cdot \sin \phi\), važi da je \(\sin \phi = \frac{\vec{a} \times \vec{b}}{|\vec{a}|\cdot|\vec{b}|},\) a sinus je jednak nuli za ugao \(0\) ili \(\pi\).

Jedna od osnovnih primena vektorskog proizvoda može biti da se utvrdi da li su tri tačke kolinearne.

Ako razmatramo tačke u trodimenzionalnom prostoru, tačka \(X\) pripada pravoj koja je određena tačkama \(A\) i \(B\) ako i samo ako je \(\overrightarrow{XA} \times \overrightarrow{XB} = \overrightarrow{0}\) (a slično i, na primer, ako i samo ako je \(\overrightarrow{AB} \times \overrightarrow{AX} = \overrightarrow{0}\)). Pri tome treba biti obazriv ako se radi sa realnim koordinatama (jer je zbog računskih grešaka malo verovatno da će se dobiti vrednosti koje su baš tačno jednake nuli). Ako su tačke \(A\), \(B\) i \(X\) date koordinatama u ravni, tada možemo razmatrati dvodimenzionalni vektorski proizvod \(\overrightarrow{XA}\times_{2d}\overrightarrow{XB}\) i proveravati da li je njegova vrednost jednaka nula.

Znak vrednosti dvodimenzionalnog vektorskog proizvoda \(\vec{a}\times_{2d}\vec{b}\) nam govori o orijentisanom uglu između vektora \(\vec{a}\) i \(\vec{b}\), pri čemu se sada ugao posmatra u intervalu \([0, 2\pi)\) (slika 6). Pozitivne vrednosti govore da je ugao koji se opisuje rotiranjem vektora \(\vec{a}\) ka vektoru \(\vec{b}\) u pozitivnom matematičkom smeru konveksan (u intervalu je \((0, \pi)\)), a negativne vrednosti da je taj ugao nekonveksan (u intervalu je \((\pi, 2\pi)\)). Ovo, naravno, odgovara znaku sinusa ugla.

Još jedna interpretacija je da pozitivni znak dvodimenzionalnog vektorskog proizvoda \(\vec{a}\times_{2d}\vec{b}\) ukazuje da je najbliži put od vektora \(\vec{a}\) do vektora \(\vec{b}\) “nalevo” tj. u pozitivnom matematičkom smeru, dok negativni znak dvodimenzionalnog vektorskog prostora ukazuje na to da je najbliži put “nadesno”.

Znak dvodimenzionalnog vektorskog proizvoda se može iskoristiti i da se tačke klasifikuju u dve poluravni na koje prava \(AB\) deli ravan. Negativna vrednost vektorskog proizvoda \(\overrightarrow{OA}\times_{2d}\overrightarrow{OB}\) ukazuje da tačka \(O\) pripada jednoj poluravni, a pozitivna da pripada drugoj (dok vrednost \(0\) ukazuje na to da tačka \(O\) pripada graničnoj pravoj \(AB\)).

10.1.5 Površina i primene

Površina trougla čije su stranice dva data vektora \(\vec{a}\) i \(\vec{b}\) je polovina površine paralelograma koji oni grade i jednaka je polovini apsolutne vrednosti njihovog vektorskog proizvoda. Ako su poznate koordinate temena trougla \(A(a_x, a_y)\), \(B(b_x, b_y)\) i \(C(c_x, c_y)\), vektori stranica su \(\overrightarrow{AB} = \vec{b} - \vec{a} = (b_x - a_x, b_y - a_y)\) i \(\overrightarrow{AC} = \vec{c} - \vec{a} = (c_x - a_x, c_y - a_y)\), pa je površina jednaka

\[P_{ABC} = \frac{|\overrightarrow{AB} \times_{2d} \overrightarrow{AC}|}{2} = \frac{|(b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)|}{2}.\]

Izrazom \(\frac{|\overrightarrow{AB} \times \overrightarrow{AC}|}{2}\) se može računati i površina trougla u prostoru (ali će tada njegovo izražavanje na osnovu koordinata tačaka biti malo komplikovanije).

Površinu je moguće izračunati i na druge načine, ali je to često ili neefikasno ili se konačna formula svodi na prethodnu. Na primer, Heronov obrazac \(s = (a+b+c)/2\), \(P=\sqrt{s(s-a)(s-b)(s-c)}\) uključuje korenovanje.

Još jedan način dolaska do rešenja je da se površina trougla iskaže kao razlika površina određenih trapeza. Na primer, ako važi raspored \(a_x < b_x < c_x\), i ako su \(A_x\), \(B_x\) i \(C_x\) redom projekcije tačaka \(A\), \(B\) i \(C\) na \(x\)-osu, tada je površina trougla \(ABC\) jednaka razlici između zbira površina pravouglih trapeza \(AA_xB_xB\), \(BB_xC_xC\) i površine pravouglog trapeza \(AA_xC_xC\) (slika 7).

Površina trapeza \(AA_xB_xB\) jednaka je proizvodu dužine njegove srednje linije i dužine njegove visine. Dužina osnovice \(A_xA\) jednaka je apsolutnoj vrednosti koordinate \(a_y\), dužina osnovice \(B_xB\) jednaka je apsolutnoj vrednosti koordinate \(b_y\) dok je dužina visine jednaka apsolutnoj vrednosti razlike koordinata \(b_x\) i \(a_x\). Tako da je površina tog trapeza jednaka

Analizom mogućih rasporeda tačaka, može se pokazati da će se ispravan rezultat dobiti i ako se posmatra takozvana označena površina trapeza, koja isključuje računanje apsolutne vrednosti u formuli (1) i dopušta negativne dužine i površine. Naime, označena površina trougla \(ABC\) biće jednaka zbiru označenih površina tri pomenuta pravougla trapeza (\(AA_xB_xB\), \(BB_xC_xC\) i \(CC_xA_xA\)), a prava površina trougla biće jednaka njenoj apsolutnoj vrednosti. Označene površine ovih trapeza dobijaju se tako što se u prethodno izvedenim formulama za njihovu površinu zanemare apsolutne vrednosti, tako da se površina trougla dobija sledećom formulom.

\[P_{ABC} = \frac{|(b_x - a_x)(b_y + a_y) + (c_x - b_x)(c_y + b_y) + (a_x - c_x)(a_y + c_y)|}{2}\]

Ova formula se nekada naziva pravilo pertle (eng. shoelace formula). Zaista, ako napišemo koordinate tačaka u narednom obliku

\[ \left. \begin{array}{cc} a_x & a_y\\ b_x & b_y\\ c_x & c_y\\ a_x & a_y \end{array} \right. \]

formula se gradi tako što se sa jednim znakom uzimaju proizvodi odozgo-naniže, sleva-udesno (to su \(a_xb_y\), \(b_xc_y\) i \(c_xa_y\)), dok se sa suprotnim znakom uzimaju proizvodi odozdo-naviše, sleva udesno (to su \(a_xc_y\), \(c_xb_y\) i \(b_xa_y\)), što, kada se nacrta, zaista podseća na cik-cak vezivanje pertli.

Primetimo da se nakon sređivanja formule dobijene kada se površina trougla računa pomoću vektorskog proizvoda takođe dobija formula pertle. Videćemo da se formula pertle može uopštiti i na izračunavanje površine određenih vrsta mnogouglova.

Rastojanje tačke od prave

Površina paralelograma određenog vektorima \(\overrightarrow{AB}\) i \(\overrightarrow{AC}\) (slika 8) je sa jedne strane jednaka apsolutnoj vrednosti dvodimenzionalnog vektorskog proizvoda vektora njegovih stranica, dok je sa druge strane jednaka proizvodu dužine njegove osnove \(AB\) i visine \(CC_{AB}\). Ovo se može upotrebiti da bi se izračunalo rastojanje tačke \(C\) od prave određene tačkama \(A\) i \(B\), jer to rastojanje predstavlja visinu \(CC_{AB}\) paralelograma određenog vektorima \(\overrightarrow{AB}\) i \(\overrightarrow{AC}\). Pošto je dužina osnovice jednaka \(|\overrightarrow{AB}|\), visina tj. rastojanje tačke \(C\) do prave \(AB\) je jednako

\[\frac{|\overrightarrow{AB}\times_{2d}\overrightarrow{AC}|}{|\overrightarrow{AB}|} = \frac{|(b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)|}{\sqrt{(b_x - a_x)^2+(b_y - a_y)^2}}\]

// rastojanje tacke C od prave odredjene tackama A i B
double rastojanje(const Tacka& A, const Tacka& B, const Tacka& C) {
  double dx = B.x - A.x;
  double dy = B.y - A.y;
  return abs(dx*(C.y-A.y) - dy*(C.x-A.x)) / sqrt(dx*dx + dy*dy);
}

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

struct Tacka {
  double x, y;
};

// rastojanje tacke C od prave odredjene tackama A i B
double rastojanje(const Tacka& A, const Tacka& B, const Tacka& C) {
  double dx = B.x - A.x;
  double dy = B.y - A.y;
  return abs(dx*(C.y-A.y) - dy*(C.x-A.x)) / sqrt(dx*dx + dy*dy);
}

int main() {
  Tacka A, B, C;
  cin >> A.x >> A.y;
  cin >> B.x >> B.y;
  int n;
  cin >> n;
  cin >> C.x >> C.y;
  double r = rastojanje(A, B, C);
  double najmanje = r, najvece = r;
  for (int i = 1; i < n; i++) {
    cin >> C.x >> C.y;
    r = rastojanje(A, B, C);
    najmanje = min(najmanje, r);
    najvece = max(najvece, r);
  }

  cout << fixed << showpoint << setprecision(5)
       << najmanje << endl
       << najvece << endl;

  return 0;
}

Izrazom \(\frac{|\overrightarrow{AB}\times\overrightarrow{AC}|}{|\overrightarrow{AB}|}\) se može računati i rastojanje od tačke do prave u prostoru.

Ako je potrebno odrediti najbližu ili najdalju tačku nekog skupa od prave \(AB\) (a ne i njihova rastojanja), dovoljno je izračunati i porediti samo vrednosti brojioca, jer će za sve tačke vrednost imenioca biti ista.

10.1.6 Orijentacija trojke tačaka i primene

Orijentacija se može zasnovati i aksiomatski², ali se lako može analitički izračunati kada su poznate koordinate tačaka \(A(a_x, a_y)\), \(B(b_x, b_y)\), \(C(c_x, c_y)\). Translacijom tačke \(A\) u koordinatni početak, možemo povezati orijentaciju trojke \(ABC\) sa orijentacijom trojke \(OB'C'\), za \(B'(b_x-a_x, b_y-a_y)\) i \(C'(c_x-a_x, c_y-a_y)\). Za nju znamo da je određena znakom dvodimenzionog vektorskog proizvoda vektora \(\overrightarrow{AB}\) i \(\overrightarrow{AC}\) (o čemu je bilo reči u poglavlju 10.1.4.1). Dakle, uređena trojka \(ABC\) ima pozitivnu orijentaciju ako i samo ako dvodimenzionalni vektorski proizvod vektora \(\overrightarrow{AB}\) i \(\overrightarrow{AC}\) ima pozitivnu vrednost. Ta vrednost je jednaka:

\[\overrightarrow{AB}\times_{2d} \overrightarrow{AC} = (b_x-a_x)(c_y-a_y) - (b_y-a_y)(c_x-a_x)\]

Pošto postoje tri moguće orijentacije, u cilju postizanja čitljivog programa moguće je definisati nabrojivi tip za predstavljanje orijentacije.

Kada su koordinate tačaka celobrojne, funkcija za izračunavanje orijentacije se veoma jednostavno definiše.

// orijentacija trojke tačka sa koordinatama A, B i C
// orijentacija je pozitivna akko je orijentisani ugao ABC konveksan
Orijentacija orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  int d = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

#include <iostream>

using namespace std;

struct Tacka {
  int x, y;
};

// moguce orijentacije trojke tacaka
enum Orijentacija {POZITIVNA, KOLINEARNE, NEGATIVNA};

// orijentacija trojke tačka sa koordinatama A, B i C
// orijentacija je pozitivna akko je orijentisani ugao ABC konveksan
Orijentacija orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  int d = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

// provera da li su tačke M i N sa iste strane prave
// određene tačkama A i B.
// Pretpostavlja se da nijedna od dve tačke ne pripada toj pravoj.
bool saIsteStrane(const Tacka& A, const Tacka& B, const Tacka& M, const Tacka& N) {
  return orijentacija(A, B, M) == orijentacija(A, B, N);
}

int main() {
  Tacka A, B;
  cin >> A.x >> A.y;
  cin >> B.x >> B.y;
  Tacka M;
  cin >> M.x >> M.y;
  int n;
  cin >> n;
  int broj = 0;
  for (int i = 0; i < n; i++) {
    Tacka N;
    cin >> N.x >> N.y;
    if (saIsteStrane(A, B, M, N))
      broj++;
  }
  cout << broj << endl;
  return 0;
}

Stvar je komplikovanija kada se radi sa koordinatama koje su zapisane pomoću brojeva u pokretnom zarezu. Naime, klasifikovanje orijentacije, a posebno ispitivanje kolinearnosti može biti veoma problematično usled grešaka u zapisu brojeva. Naime, umesto da vrednost dvodimenzionalnog vektorskog proizvoda bude tačno nula, ona može da bude neki veoma mali broj blizak nuli. Najjednostavnije je da se tada fiksira neka vrednost \(\varepsilon\) i da se, kada god je vrednost proizvoda u intervalu \([-\varepsilon, \varepsilon]\), tačke proglase za kolinearne. Međutim, nije unapred jasno kolika bi trebalo da bude ta vrednost \(\varepsilon\). Vrednost vektorskog proizvoda ne zavisi samo od ugla između vektora, već i od njihove dužine, pa bi precizniji pristup bi bio da se na osnovu vrednosti dvodimenzionalnog vektorskog proizvoda izračuna sinus ugla između vektora i da se za proveru kolinearnosti zahteva da on pripada nekom malom intervalu, međutim, to je računski intenzivnije. U nekim primenama nije previše bitno kako će se klasifikovati tačke koje su skoro kolinearne. Na primer, u računarskoj grafici, kako god da se klasifikuju tačke koje su gotovo kolinearne, ljudsko oko neće primetiti razliku.

Provera da li su tačke sa iste strane prave

Jednostavnosti radi pretpostavićemo da nijedna od tačaka \(M\) i \(N\) ne pripada na pravoj \(AB\).

Tačke \(M\) i \(N\) su sa iste strane prave \(p\) ako i samo ako su trouglovi \(ABM\) i \(ABN\), \(A,B\in p\) iste orijentacije (slika 10). Dakle, dovoljno je da ispitamo da li su odgovarajući dvodimenzionalni vektorski proizvodi istog znaka.

Kada imamo na raspolaganju funkciju za računanje orijentacije, implementacija provere da li su dve tačke sa iste strane prave je veoma jednostavna.

// provera da li su tačke M i N sa iste strane prave
// određene tačkama A i B.
// Pretpostavlja se da nijedna od dve tačke ne pripada toj pravoj.
bool saIsteStrane(const Tacka& A, const Tacka& B, const Tacka& M, const Tacka& N) {
  return orijentacija(A, B, M) == orijentacija(A, B, N);
}

#include <iostream>

using namespace std;

struct Tacka {
  int x, y;
};

// moguce orijentacije trojke tacaka
enum Orijentacija {POZITIVNA, KOLINEARNE, NEGATIVNA};

// orijentacija trojke tačka sa koordinatama A, B i C
// orijentacija je pozitivna akko je orijentisani ugao ABC konveksan
Orijentacija orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  int d = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
  if (d > 0)
    return POZITIVNA;
  else if (d < 0)
    return NEGATIVNA;
  else
    return KOLINEARNE;
}

// provera da li su tačke M i N sa iste strane prave
// određene tačkama A i B.
// Pretpostavlja se da nijedna od dve tačke ne pripada toj pravoj.
bool saIsteStrane(const Tacka& A, const Tacka& B, const Tacka& M, const Tacka& N) {
  return orijentacija(A, B, M) == orijentacija(A, B, N);
}

int main() {
  Tacka A, B;
  cin >> A.x >> A.y;
  cin >> B.x >> B.y;
  Tacka M;
  cin >> M.x >> M.y;
  int n;
  cin >> n;
  int broj = 0;
  for (int i = 0; i < n; i++) {
    Tacka N;
    cin >> N.x >> N.y;
    if (saIsteStrane(A, B, M, N))
      broj++;
  }
  cout << broj << endl;
  return 0;
}

Proširimo sada zahtev time da želimo da ako su tačke sa raznih strana prave odredimo i presečnu tačku duži koja ih spaja i prave.

Ovaj metod jeste zasnovan na korišćenju dvodimenzionalnog vektorskog proizvoda, ali ne za izračunavanje orijentacije trojke tačaka, jer ćemo koristiti proizvode vektora oblika \(\overrightarrow{XY} \times_{2d} \overrightarrow{ZW}\) (koji, podsetimo se, daju vrednost označene površine paralelograma određenog pomoću ta dva vektora).

Degenerisani slučaj nastupa kada su vektori \(\overrightarrow{AB}\) i \(\overrightarrow{MN}\) kolinearni, što se dešava ako i samo ako je \(\overrightarrow{AB} \times_{2d} \overrightarrow{MN} = 0\). Ako su u tom slučaju tačke \(M\), \(A\) i \(B\) kolinearne tj. ako je \(\overrightarrow{MA} \times_{2d} \overrightarrow{MB} = 0\), tada duž pripada pravoj, a ako nisu kolinearne, onda presek ne postoji.

U nedegenerisanom slučaju je \(\overrightarrow{AB} \times_{2d} \overrightarrow{MN} \neq 0\). Tada postoji presečna tačka \(X\) pravih \(AB\) i \(MN\) i važi da je:

\[X = M + k\overrightarrow{MN},\quad\mathrm{tj.}\quad \overrightarrow{MX}=k\overrightarrow{MN}.\]

Tačka \(X\) pripada duži \(MN\) ako i samo ako je \(0 \leq k \leq 1\). Pošto je \(\overrightarrow{MX} = \overrightarrow{MA} + \overrightarrow{AX}\), množenjem prethodne jednačine vektorski sa \(\overrightarrow{AB}\) sleva, dobija se:

\[\overrightarrow{AB}\times_{2d} (\overrightarrow{MA} + \overrightarrow{AX}) = k \cdot (\overrightarrow{AB}\times_{2d}\overrightarrow{MN})\]

Pošto važi da je \(\overrightarrow{AB}\times_{2d}\overrightarrow{AX} = 0\), jer tačka \(X\) pripada pravoj \(AB\), pa su ti vektori kolinearni, možemo izračunati koeficijent \(k\).

\[k = \frac{\overrightarrow{AB}\times_{2d}\overrightarrow{MA}}{\overrightarrow{AB}\times_{2d}\overrightarrow{MN}}\]

Da bi se proverilo da li tačka \(X\) pripada duži \(MN\) dovoljno je proveriti: (1) da li su brojevi \(\overrightarrow{AB}\times_{2d}\overrightarrow{MA}\) i \(\overrightarrow{AB}\times_{2d}\overrightarrow{MN}\) istog znaka i (2) da li je \(|\overrightarrow{AB}\times_{2d}\overrightarrow{MA}| \leq |\overrightarrow{AB}\times_{2d}\overrightarrow{MN}|\), što se sve može uraditi i u celobrojnoj aritmetici (ako su početne koordinate tačaka celobrojne).

Neka je \(M' = M + \overrightarrow{AB}\) i \(N' = N + \overrightarrow{AB}\). Vrednost \(\overrightarrow{AB}\times_{2d}\overrightarrow{MA}\) predstavlja označenu površinu paralelograma određenog vektorima \(\overrightarrow{AB}\) i \(\overrightarrow{MA}\) (on je obojen na slici 11). Ta je površina jednaka označenoj površini paralelograma \(P_1\) određenog vektorima \(\overrightarrow{MX}\) i \(\overrightarrow{XX'}\). Vrednost \(\overrightarrow{AB}\times_{2d}\overrightarrow{MN}\) predstavlja označenu površinu paralelograma \(P_2\) određenog vektorima \(\overrightarrow{AB} = \overrightarrow{MM'}\) i \(\overrightarrow{MN}\) (i on je obojen na slici 11). Pošto paralelogrami \(P_1\) i \(P_2\) imaju istu visinu, odnos njihovih površina jednak je odnosu dužina njihovih stranica \(MX\) i \(MN\).

Ispitivanje da li tačka pripada unutrašnjosti trougla

Kao što je to obično slučaj u geometriji, treba obratiti pažnju na degenerisane i granične slučajeve. Na primer, mi ćemo, jednostavnosti radi, pretpostavljati da je trougao nedegenerisan tj. da su tačke \(A\), \(B\) i \(C\) nekolinearne. Smatraćemo i da je trougao otvoren lik, tj. da tačke na stranicama trougla ne pripadaju njegovoj unutrašnjosti.

Tačka pripada trouglu ako i samo ako su tačke \(C\) i \(P\) sa iste strane prave \(AB\), tačke \(A\) i \(P\) sa iste strane prave \(BC\) i tačke \(B\) i \(P\) sa iste strane prave \(CA\). Ako to važi, tada je ista orijentacija trojki \(ABC\) i \(ABP\), ista orijentacija trojki \(BCA\) i \(BCP\) i trojki \(CAB\) i \(CAP\). Pošto su orijentacije trojki \(ABC\), \(BCA\) i \(CAB\) jednake, jednake su i orijentacije trojki \(ABP\), \(BCP\) i \(CAP\). Pokazuje se da je ovo dovoljan uslov da bi tačka \(P\) pripadala trouglu \(ABC\) (slika 12).

Obratimo pažnju da ovaj uslov ne obuhvata pripadnost stranicama trougla, što je u skladu sa pretpostavkom da je trougao otvoren lik (ako bi tačka pripadala nekoj stranici, neka orijentacija bi bila jednaka nuli i ne bi bilo moguće da su sve orijentacije međusobno jednake).

Kada imamo funkciju za izračunavanje orijentacije na raspolaganju, implementacija provere pripadnosti trouglu je veoma jednostavna.

bool tackaUTrouglu(const Tacka& T,
                   const Tacka& A, const Tacka& B, const Tacka& C) {
  Orijentacija o1 = orijentacija(A, B, T);
  Orijentacija o2 = orijentacija(B, C, T);
  Orijentacija o3 = orijentacija(C, A, T);
  return o1 == o2 && o2 == o3;
}

#include <iostream>
#include <cmath>

using namespace std;

// tolerancija
const double EPS = 1e-6;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  double x, y;
  Tacka(double x_, double y_) {
    x = x_; y = y_;
  }
};

// moguce orijentacije trojke tacaka
enum Orijentacija {POZITIVNA, KOLINEARNE, NEGATIVNA};

Orijentacija orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  double d = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
  if (abs(d) < EPS)
    return KOLINEARNE;
  else if (d > EPS)
    return POZITIVNA;
  else
    return NEGATIVNA;
}

bool tackaUTrouglu(const Tacka& T,
                   const Tacka& A, const Tacka& B, const Tacka& C) {
  Orijentacija o1 = orijentacija(A, B, T);
  Orijentacija o2 = orijentacija(B, C, T);
  Orijentacija o3 = orijentacija(C, A, T);
  return o1 == o2 && o2 == o3;
}


int main() {
  double x, y;
  cin >> x >> y;
  Tacka P(x, y);
  cin >> x >> y;
  Tacka A(x, y);
  cin >> x >> y;
  Tacka B(x, y);
  cin >> x >> y;
  Tacka C(x, y);
  if (tackaUTrouglu(P, A, B, C))
    cout << "da" << endl;
  else
    cout << "ne" << endl;
  return 0;
}

Još jedan mogući pristup proveri da li tačka pripada je da se proveri da li je zbir površina trouglova \(ABP\), \(BCP\) i \(CAP\) jednak površini trougla \(ABC\). Ovaj pristup može biti računski neefikasniji (naročito ako se površine računaju preko Heronovog obrasca koji uključuje korenovanje). Dodatno, ako su tačke predstavljene realnim koordinatama, ovaj pristup može da bude numerički nestabilan. Naime, i za tačku koja je unutar trougla, može da se desi da zbir površina tri manja trougla ne bude tačno jednak, već samo blizak površini većeg trougla. Zato je jednakost potrebno proveravati do na neku tačnost \(\varepsilon\) (pri čemu ostaje osetljivo pitanje kako odrediti tu vrednost \(\varepsilon\)). Iz svih navedenih razloga, ovaj pristup je poželjno izbegavati.

bool tackaUTrouglu(const Tacka& T,
                   const Tacka& A, const Tacka& B, const Tacka& C) {
  // racunamo povrsinu trougla ABC
  double P = povrsinaTrougla(A, B, C);
  // racunamo povrsine trouglova TBC, TAC i TAB
  double PA = povrsinaTrougla(T, B, C);
  double PB = povrsinaTrougla(A, T, C);
  double PC = povrsinaTrougla(A, B, T);
  // proveravamo da li one u zbiru daju povrsinu trougla ABC
  // poredimo dve realne vrednosti na jednakost
  return abs(P - (PA + PB + PC)) < EPS;
}

#include <iostream>
#include <cmath>

using namespace std;

// tolerancija
const double EPS = 1e-6;

// tacka je zadata svojim dvema koordinatama
struct Tacka {
  double x, y;
  Tacka(double x_, double y_) {
    x = x_; y = y_;
  }
};

double povrsinaTrougla(const Tacka& A, const Tacka& B, const Tacka& C) {
  // pertle (cik-cak)
  return abs(+ A.x*B.y + B.x*C.y + C.x*A.y
             - A.x*C.y - C.x*B.y - B.x*A.y) / 2.0;
}

bool tackaUTrouglu(const Tacka& T,
                   const Tacka& A, const Tacka& B, const Tacka& C) {
  // racunamo povrsinu trougla ABC
  double P = povrsinaTrougla(A, B, C);
  // racunamo povrsine trouglova TBC, TAC i TAB
  double PA = povrsinaTrougla(T, B, C);
  double PB = povrsinaTrougla(A, T, C);
  double PC = povrsinaTrougla(A, B, T);
  // proveravamo da li one u zbiru daju povrsinu trougla ABC
  // poredimo dve realne vrednosti na jednakost
  return abs(P - (PA + PB + PC)) < EPS;
}


int main() {
  double x, y;
  cin >> x >> y;
  Tacka P(x, y);
  cin >> x >> y;
  Tacka A(x, y);
  cin >> x >> y;
  Tacka B(x, y);
  cin >> x >> y;
  Tacka C(x, y);
  if (tackaUTrouglu(P, A, B, C))
    cout << "da" << endl;
  else
    cout << "ne" << endl;
  return 0;
}

Presek duži

Ako su sve tačke u opštem položaju, tj. sve tačke su različite i nikoje tri nisu kolinearne, duži se seku ako i samo ako duž \(AB\) seče pravu \(CD\) i duž \(CD\) seče pravu \(AB\), pa se ispitivanje preseka dve duži može lako svesti na ispitivanje preseka duži i prave (što je opisano u poglavlju 10.1.6.1). Duž seče pravu ako i samo ako su njene krajnje tačke sa raznih strana te prave, a to je problem koji se lako rešava pomoću ispitivanja orijentacije tačaka. Dovoljno je proveriti da li su orijentacije trojki \(CDA\) i \(CDB\) različitog znaka i da li su orijentacije trojki \(ABC\) i \(ABD\) različitog znaka, tj. da li im je proizvod negativan (pri čemu se za orijentaciju trojke \(XYZ\) može uzeti znak dvodimenzionalnog vektorskog proizvoda \(\overrightarrow{XY} \times_{2d} \overrightarrow{XZ}\)). Ovaj test se lako prilagođava slučajevima u kojima su neke tri tačke kolinearne. Naime, umesto da se zahteva da su dve tačke sa striktno različitih strana prave, moguće je uključiti i slučaj da neka od njih pripada pravoj, što se svodi na ispitivanje da li je orijentacija nepozitivna (vrednost joj je manja ili jednaka od nule).

Problem predstavlja degenerisani slučaj kada su sve četiri tačke kolinearne. Naime, ako su sve tačke kolinearne, sve orijentacije trojki biće jednake \(0\) i iz toga nećemo moći da izvučemo nikakav zaključak o međusobnom odnosu dve duži (znamo da one pripadaju jednoj pravoj, ali su svi njihovi međusobni odnosi mogući). U tom slučaju njihov odnos je moguće ispitati ispitivanjem njihovih projekcija na \(x\)-osu (tj. njihovih \(x\)-koordinata). Nažalost, ni ovo nije dovoljno u slučaju kada sve \(4\) tačke imaju istu \(x\) koordinatu, no tada možemo ispitati njihove projekcije na \(y\)-osu (tj. njihove \(y\)-koordinate). Da bi se projekcije na \(x\)-osu \([a_x, b_x]\) i \([c_x, d_x]\) sekle dovoljno je da ne važi da je jedan od intervala levo od drugog tj. ne sme da važi \(b_x < c_x\) niti \(d_x < a_x\), što je ekvivalentno tome da je \(b_x \geq c_x \wedge d_x \geq a_x\). Prilikom primene ovoga uslova potrebno je obezbediti da važi da se zna šta je levi, a šta desni kraj intervala tj. da je \(a_x \leq b_x\) i \(c_x \leq d_x\). Analogno se postavlja uslov koji mora da važi i za projekcije na \(y\)-osu.

Sledi implementacija provere da li se dve duži seku. Funkcija koja izračunava orijentaciju vraća vrednosti \(-1\), \(0\), \(1\), čime je kôd možda malo manje čitljiv, ali je omogućeno da se provera da li su dva broja istog znaka izvrši tako što se proveri da li je proizvod dve orijentacije nenegativan. Obratimo pažnju na to da umesto vrednosti vektorskog proizvoda funkcija vraća njen znak, čime se izbegava opasnost od prekoračenja prilikom množenja dve orijentacije.

struct Tacka {
  int x, y;
};

// 1 za pozitivne vrednosti, -1 za negativne i 0 za nulu
int znak(long long x) {
  return (x > 0) - (x < 0);
}

// orijentacija tj. znak vektorskog proizvoda AB x AC
int orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  return znak((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
}

// provera da li prava AB sece duz MN
bool pravaSeceDuz(const Tacka& A, const Tacka& B,
                         const Tacka& M, const Tacka& N) {
  return orijentacija(A, B, M) * orijentacija(A, B, N) <= 0;
}

// provera da li se intervali realne prave [a, b] i [c, d] seku
// (pri cemu se ne zna odnos vrednosti a i b tj. c i d)
bool projekcijeSeSeku(long long a, long long b, long long c, long long d) {
  return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
}

// provera da li se duzi AB i CD seku
bool duziSeSeku(const Tacka& A, const Tacka& B,
                const Tacka& C, const Tacka& D) {
  return pravaSeceDuz(A, B, C, D) &&
         pravaSeceDuz(C, D, A, B) &&
         // seku se projekcije na x osu
         projekcijeSeSeku(A.x, B.x, C.x, D.x) && 
         // seku se projekcije na y osu
         projekcijeSeSeku(A.y, B.y, C.y, D.y);
}

#include <iostream>
using namespace std;

struct Tacka {
  int x, y;
};

// 1 za pozitivne vrednosti, -1 za negativne i 0 za nulu
int znak(long long x) {
  return (x > 0) - (x < 0);
}

// orijentacija tj. znak vektorskog proizvoda AB x AC
int orijentacija(const Tacka& A, const Tacka& B, const Tacka& C) {
  return znak((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
}

// provera da li prava AB sece duz MN
bool pravaSeceDuz(const Tacka& A, const Tacka& B,
                         const Tacka& M, const Tacka& N) {
  return orijentacija(A, B, M) * orijentacija(A, B, N) <= 0;
}

// provera da li se intervali realne prave [a, b] i [c, d] seku
// (pri cemu se ne zna odnos vrednosti a i b tj. c i d)
bool projekcijeSeSeku(long long a, long long b, long long c, long long d) {
  return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
}

// provera da li se duzi AB i CD seku
bool duziSeSeku(const Tacka& A, const Tacka& B,
                const Tacka& C, const Tacka& D) {
  return pravaSeceDuz(A, B, C, D) &&
         pravaSeceDuz(C, D, A, B) &&
         // seku se projekcije na x osu
         projekcijeSeSeku(A.x, B.x, C.x, D.x) && 
         // seku se projekcije na y osu
         projekcijeSeSeku(A.y, B.y, C.y, D.y);
}

int main() {
  Tacka A, B, C, D;
  cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
  cout << (duziSeSeku(A, B, C, D) ? "da" : "ne") << endl;
  return 0;
}

Funkcija koju smo implementirali ispravno radi u svim slučajevima (i nedegenerisanim i degenerisanim), ali u mnogim slučajevima vrši neke nepotrebne provere uslova (na primer, ako nisu sve četiri tačke kolinearne, nema potrebe proveravati projekcije na ose). Uz to, nakon što se detektuje da presek postoji, potrebno je izračunati ga sasvim iznova. Prikažimo sada drugačiji metod, koji je malo efikasniji i kojim se može odmah odrediti i presečna tačka.

Na početku računamo \(\overrightarrow{AB}\times_{2d} \overrightarrow{CD}\) i proveravamo da li je taj broj različit od nule. Time smo efektivno ispitali da li su vektori \(\overrightarrow{AB}\) i \(\overrightarrow{CD}\) kolinearni.

// z koordinata vektorskog proizvoda vektora MN i PQ
long long vektorski_proizvod_2d(const Tacka& M, const Tacka& N, 
                                const Tacka& P, const Tacka& Q) {
   return (N.x - M.x)*(Q.y - P.y) - (N.y - M.y)*(Q.x - P.x);
}

// provera da li je 0 <= brojilac/imenilac <= 1
bool kolicnikUIntervalu01(int brojilac, int imenilac) {
  return brojilac == 0 ||
         (istogZnaka(brojilac, imenilac) && abs(brojilac) <= abs(imenilac));
}

// provera da li se intervali realne prave [a, b] i [c, d] seku
// (pri cemu se ne zna odnos vrednosti a i b tj. c i d)
bool projekcijeSeSeku(long long a, long long b, long long c, long long d) {
   return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
}

// provera da li se duzi AB i CD seku
bool duziSeSeku(const Tacka& A, const Tacka& B, 
                const Tacka& C, const Tacka& D) {
   int ABCD = vektorski_proizvod_2d(A, B, C, D);
   if (ABCD != 0) {
      int ABCA = vektorski_proizvod_2d(A, B, C, A);
      int ACCD = vektorski_proizvod_2d(A, C, C, D);
      // presecna tacka se moze odrediti kao: C + (ABCA/ABCD)CD
      return kolicnikUIntervalu01(ACCD, ABCD) &&
             kolicnikUIntervalu01(ABCA, ABCD);
   } else {
     int ABAC = vektorski_proizvod_2d(A, B, A, C);
     if (ABAC != 0)
        return false;
     if (A.x == B.x && C.x == D.x)
        return projekcijeSeSeku(A.y, B.y, C.y, D.y);
     else
        return projekcijeSeSeku(A.x, B.x, C.x, D.x);
   }
}

#include <iostream>
using namespace std;

struct Tacka {
  int x, y;
};

// provera da li su brojevi m i n (n je razlicito od nule) istog znaka 
bool istogZnaka(int m, int n) {
   return (m > 0) == (n > 0);
}

// z koordinata vektorskog proizvoda vektora MN i PQ
long long vektorski_proizvod_2d(const Tacka& M, const Tacka& N, 
                                const Tacka& P, const Tacka& Q) {
   return (N.x - M.x)*(Q.y - P.y) - (N.y - M.y)*(Q.x - P.x);
}

// provera da li je 0 <= brojilac/imenilac <= 1
bool kolicnikUIntervalu01(int brojilac, int imenilac) {
  return brojilac == 0 ||
         (istogZnaka(brojilac, imenilac) && abs(brojilac) <= abs(imenilac));
}

// provera da li se intervali realne prave [a, b] i [c, d] seku
// (pri cemu se ne zna odnos vrednosti a i b tj. c i d)
bool projekcijeSeSeku(long long a, long long b, long long c, long long d) {
   return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
}

// provera da li se duzi AB i CD seku
bool duziSeSeku(const Tacka& A, const Tacka& B, 
                const Tacka& C, const Tacka& D) {
   int ABCD = vektorski_proizvod_2d(A, B, C, D);
   if (ABCD != 0) {
      int ABCA = vektorski_proizvod_2d(A, B, C, A);
      int ACCD = vektorski_proizvod_2d(A, C, C, D);
      // presecna tacka se moze odrediti kao: C + (ABCA/ABCD)CD
      return kolicnikUIntervalu01(ACCD, ABCD) &&
             kolicnikUIntervalu01(ABCA, ABCD);
   } else {
     int ABAC = vektorski_proizvod_2d(A, B, A, C);
     if (ABAC != 0)
        return false;
     if (A.x == B.x && C.x == D.x)
        return projekcijeSeSeku(A.y, B.y, C.y, D.y);
     else
        return projekcijeSeSeku(A.x, B.x, C.x, D.x);
   }
}

int main() {
  Tacka A, B, C, D;
  cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
  cout << (duziSeSeku(A, B, C, D) ? "da" : "ne") << endl;
  return 0;
}

Prethodni program je veoma jednostavno preraditi tako da izračunava i presečnu tačku duži ako ona postoji.

Treće moguće rešenje bi bilo da za tačke \(A\) i \(B\) ispitamo da li pripadaju duži \(CD\), a za tačke \(C\) i \(D\) da li pripadaju duži \(AB\) (ako je bilo šta od ovoga zadovoljeno, duži se seku). Da bi se ispitalo da li tačka \(P\) pripada duži \(MN\) dovoljno je proveriti da li su tačke \(M\), \(N\) i \(P\) kolinearne (tj. da li je orijentacija trojke \(MNP\) jednaka nuli) i da li je \(x\)-koordinata tačke \(P\) između \(x\)-koordinata tačaka \(M\) i \(N\) kao i da li je \(y\)-koordinata tačke \(P\) između \(y\)-koordinata tačaka \(M\) i \(N\).

10.1.7 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.

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 13.

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 13).

Brišuća prava (pa i vertikalne duži koje se sa njom poklope) se mogu 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 vertikalne duži). 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 prave 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 13 ima šest kandidata za presek sa \(L\).

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.

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 14).

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 standadnoj biblioteci većine savremeniih programskih jezika (u C++-u to je struktura podataka set).

// 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>
#include <vector>
#include <set>
#include <algorithm>

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;
}

Nekada se ova vrednost naziva i označena površina (engl. signed area) paralelograma određenog preko dva vektora u ravni.↩︎
Aksiomatsko zasnivanje orijentacije detaljno je opisano u knjizi Donada Knuta “Aksiome i omotači”.↩︎

10.1 Osnove geometrijskih algoritama