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.
Problem. Dato je \(n\) različitih tačaka u ravni, takvih da nisu sve kolinearne. Povezati ih prostim mnogouglom.
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 1).
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.
U narednom apletu prikazana je rotirajuća prava i mnogougao koji se ovim pristupom dobija.
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 2). Naime, isečci su sigurno međusobno disjunktni, pa ako im duži cele pripadaju, i one su međusobno disjunktne (osim što se susedne dodiruju krajnjim tačkama).
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.
Primer 161. U primeru ilustrovanom na slici 3 duž \(P_1P_7\) prolazi kroz druge isečke kruga i seče stranice \(P_2P_3\) i \(P_3P_4\).
U narednom apletu možete videti kako se ponašaju kružni isečci kojima pripadaju stranice mnogougla dobijenog pomoću rotirajuće poluprave iz temena \(O\). Možete pomerati tačku \(O\) (ali i temena 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\). Zaista, poluprave iz težišta do temena trougla dele pun ugao na tri konveksna ugla, a poluprave ka svim ostalim tačkama polaznog skupa samo mogu da te konveksne uglove podele na manje delove koji takođe moraju biti konveksni.
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 poluprave iz \(O\) koja se prostire u pravcu pozitivnog dela \(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 i nema potrebe za izračunavanjem kvadratnih korenova.
U narednom apletu možete isprobati ponašanje algoritma konstrukcije prostog mnogougla sortiranjem uglova u odnosu na fiksiranu osu \(O_x\). Uglovi se računaju u intervalu \([0, 2 \pi)\) (što je malo različito u odnosu na funkciju \(\text{atan2}\) koja vraća uglove iz intervala \((-\pi, \pi]\), ali ne menja ništa suštinski, osim oznaka temena). Probajte da pomeranjem tačke \(O\) dobijete nekoliko različitih prostih mnogouglova čija su temena date tačke. Naravno, ako se centar kruga postavi tako da se sve tačke nađu sa jedne strane neke prave koja prolazi kroz centar, moguće je da se dobije netačan rezultat.
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);
});
}# include <iostream> {.unnumbered .unlisted}
# include <vector> {.unnumbered .unlisted}
# include <algorithm> {.unnumbered .unlisted}
# include <numeric> {.unnumbered .unlisted}
# include <cmath> {.unnumbered .unlisted}
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);
});
}
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)1. 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 pozitivnim smerom \(x\)-ose, jer su to uglovi sa paralelnim kracima). Tačke označene u ovom redosledu su prikazane na slici 4.
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, očigledno važi sledeća lema (ilustrovana na slici 5).
Lema 59. [Poredak uglova i orijentacija] Neka su \(P_i\), \(P_j\) i \(O\) tri nekolinearne tačke i neka se \(P_i\) i \(P_j\) nalaze levo od \(O\) (tj. neka je \(x\)-koordinata tačke \(O\) veća ili jednaka od \(x\)-kordinata tačaka \(P_i\) i \(P_j\)). Neka je \(p\) poluprava sa temenom u \(O\) koja se prostire duž pozitivnog smera \(x\) ose. Ugao između poluprave \(p\) i poluprave \(OP_i\) je strogo manji od ugla između poluprave \(p\) i poluprave \(OP_j\) ako i samo ako je trojka \(P_jOP_i\) pozitivno orijentisana (isto kao i \(OP_iP_j\)).
Dakle, za potrebe poređenja tačaka \(P_i\) i \(P_j\) prema uglu koji poluprave \(OP_i\) i \(OP_j\) zahvataju sa horizontalnom polupravom \(p\) kroz tačku \(O\) (tj. sa pozitivnim smerom \(x\)-ose) dovoljno je izračunati orijentaciju tačaka trojke \(OP_iP_j\). Ako je ona pozitivna, onda \(OP_i\) zaklapa manji ugao od \(OP_j\), ako je negativna, onda \(OP_j\) zaklapa manji ugao od \(OP_i\), a ako je vrednost orijentacije nula, tada su te tri tačke kolinearne, uglovi su jednaki i potrebno je uporediti ih po drugim kriterijumima (u našem slučaju na osnovu rastojanja od \(O\)).
U narednom apletu možete videti kako izgleda izgradnja prostog mnogougla kada se za tačku \(O\) uzima ekstremna tačka skupa.
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> {.unnumbered .unlisted}
# include <algorithm> {.unnumbered .unlisted}
# include <vector> {.unnumbered .unlisted}
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;
}Naravno, pošto je problem simetričan i duž horizontalne i duž vertikalne ose, bilo koja druga kombinacija uslova minimalnosti i maksimalnosti koordinata je u redu.↩︎