Algoritmul lui Andrew

Algoritmul lui Andrew  este un algoritm pentru construirea unei carcase convexe în spațiu bidimensional, o modificare a algoritmului lui Graham .

Spre deosebire de algoritmul Graham, acesta folosește ordonarea lexicografică a punctelor după coordonate, din acest motiv algoritmul nu trebuie să folosească numere reale și funcții trigonometrice . Algoritmul calculează separat învelișurile superioare și inferioare din lanțuri succesive de puncte. În esență, algoritmul lui Andrew este un caz special al algoritmului lui Graham, unde punctul central este ales să fie la infinit în direcția negativă de-a lungul axei y, astfel încât în ​​acest caz ordonarea absciselor să fie aceeași cu ordonarea unghiului polar.

Aplicație

Primul algoritm[ rafina ] sortează un set de puncte prin increment , apoi . Fie coordonatele minime și maxime și . Evident, primul dintre puncte are . Dar pot exista și alte puncte cu această coordonată minimă . Să găsim astfel de puncte în care există două minime și două maxime și să le conectăm cu un segment. Restul setului de puncte este împărțit în două, în funcție de ce parte a acestei linii drepte se află punctele. În acest fel putem defini o nouă linie de jos și o nouă linie de sus. Luate împreună, aceste linii dau învelișul necesar.

Pentru a construi învelișul superior, punctele mulțimii sunt ordonate în funcție de creșterea abscisei, iar apoi munca datelor obținute este efectuată conform algoritmului Graham . Pentru a face acest lucru, algoritmul lui Andrew folosește o stivă pentru a stoca shell-ul de sus actual. Punctul este considerat a fi în partea de sus a stivei. După finalizarea algoritmului, stiva conține shell-ul superior al setului .

Literatură