Algoritmus
Az alapötlet a következő: kiválasztunk egy belső átlót, ezzel kettévágjuk a sokszöget, az átlót hozzáadjuk a háromszögeléshez, a két részre pedig rekurzív megoldjuk a problémát.
Ismer tétel, hogy mindig választható belső átló.
Belső átló kiválasztása
- Vesszük a legbaloldalibb legalsó pontot, legyen ez $v$.
($O(n)$ lépés)
- A $v$ szomszédai $u$ és $w$. (Megfelelő adatszerkezettel ez konstans lépés, ügyetlenebb módszerrel $O(n)$.)
- Teszteljük az $uvw$ háromszöget ($O(n)$ lépés): ha nincs benne és határán pont, akkor $uw$ jó átló. Ha van belső pont, akkor a belső pontok közül az $uw$-től legtávolabbival ($v'$) jó átló lesz $vv'$.
Kettévágás
Ha az eredeti csúcsok ciklikus sorrendben
$1,2,3,...,n$, a megtalált átló pedig
$uw$, ahol
$u, akkor a két új rész:
- $u,u+1,u+2,...,w$
- $w,w+1,...,n,1,2,...,u-1$
A csúcsok eredeti sorrendjét megtartva a részek csúcsainak is helyes lesz a ciklikus rendezése.
Kódok
