A számítástechnika és a számítógépes geometria , a Graham útvonal (más néven Graham algoritmus ) egy algoritmus számára kiszámítására konvex burok egy ponthalmaz a síkon. Fő érdeke annak algoritmikus komplexitása az O (n log n) , ahol n a pontok számát. Ez az algoritmus Ronald Graham nevéhez fűződik , aki 1972-ben publikálta az eredeti algoritmust .
Az algoritmus bemenetként egy tömb pontot vesz fel , az alábbi ábra szerint:
Ennek az algoritmusnak az első lépése a legkisebb ordinátával rendelkező pont megtalálása , amelyet pivotnak hívunk . Ha több pontnak ugyanaz a legkisebb ordinátája van, akkor az algoritmus kiválasztja közülük a legkisebb abszissza pontját . Amint az a következő ábrán látható, a csukló a bal oldali legalacsonyabb pont. Az elforgatás most 1. pont lesz.
Ezután a pontok halmaza (a forgást is beleértve) rendezésre kerül annak a szögnek megfelelően, amelyet mindegyikük az x tengellyel a forgáshoz viszonyítva megad. Erre bármilyen összehasonlító rendezési algoritmus alkalmas, például halom rendezés vagy egyesítés rendezés (amelyek optimálisak és O (n log n) összetettségűek ). Ehhez nem szükséges kiszámítani a valós szöget; korlátozódhat az érintők összehasonlítására, vagy akár a koordináták kereszttermékével megismerheti a pontok relatív helyzetét. Ennek a lépésnek a végén van egy T tömb, amely az így rendezett pontokat tartalmazza. Az alábbi ábra azokat a pontokat mutatja, amelyeket a rendezési sorrend betartása érdekében újraszámoztunk.
Az algoritmus iteratív módon konstruálja a konvex burkot (a következő ábrán zöld színnel). A forgatással kezdjük. Ezután a pontokat a rendezett tömb sorrendjében vizsgáljuk meg (a vizsgálandó pontot feketével mutatjuk be). Minden lépésnél megnézzük, hogy van-e "bal kanyar" (mint az ábrán bemutatott példánál a 2., 5., 13., 15. lépésnél) vagy "jobb kanyar" (mint a 10., 17., 18. lépésnél). a példa).
A végén (19. lépés, majd 20. lépés) az algoritmus kiszámította a konvex borítékot.
Annak megállapításához, hogy három pont "balra" vagy "jobbra" képez-e, nincs szükség a két szegmens közötti tényleges szög kiszámítására , és ezt egyszerű számtannal lehet elérni. Három pontra (x 1 , y 1 ), (x 2 , y 2 ) és (x 3 , y 3 ) elegendő kiszámítani a pontok által definiált két vektor kereszttermékének irányát (x 1 , y 1 ), (x 2 , y 2 ) és (x 1 , y 1 ), (x 3 , y 3 ), az (x 2 - x 1 ) (y 3 - y 1 ) - ( y 2 - y 1 ) (x 3 - x 1 ). Ha az eredmény nulla, a pontok egymáshoz igazodnak. Ha pozitív, akkor a három pont "balra fordulást" jelent. Ellenkező esetben ez egy „jobb kanyar”.
Ez a folyamat végül visszatér arra a pontra, ahol elkezdődött, ebben az esetben az algoritmus megszűnik, és a konvex burkot képező pontokat az óramutató járásával ellentétes sorrendben adja vissza. A példánál az 1., 2., 3., 6. és 9. pont.
A forgásválasztás időbeli összetettsége Θ (n) -ben van, n a halmaz pontjainak száma. A válogatás a pontokat lehet tenni egy ideig összetettsége a O (n log n) . A fő hurok bonyolultsága úgy tűnhet, hogy n (n 2 ), mivel az algoritmus minden ponton visszamegy, hogy felmérje, hogy az előző pontok bármelyike „jobb-e”. De valójában O (n) -nél van, mert minden pontot csak egyszer veszünk figyelembe. Így minden elemzett pont vagy befejezi az alhurkot, vagy eltávolításra kerül a T-ből, ezért soha többé nem veszi figyelembe. Az algoritmus teljes komplexitása tehát O (n log n) -ben van , mivel a rendezés bonyolultsága uralja a konvex burok hatékony számításának bonyolultságát.
Legyen T a vizsgálandó pontok halmaza, amely egyből indexelt tömb formájában jelenik meg. Az algoritmus során a szerkesztendő sokszöget veremben tároljuk .
fonction parcours_de_Graham(T[1,.., n]) trouver le pivot et le placer en T[1]; trier le tableau T[2..n] par angle croissant par rapport au pivot (les points d'angle égal seront triés par abscisse croissante) pile.empiler(T[1]); pile.empiler(T[2]); pour i = 3 à n tant que (pile.hauteur >= 2) et (T[i] à droite du segment [pile.second, pile.sommet]) pile.dépiler; pile.empiler(T[i]); retourner pileahol a verem.második a verem és a verem tetején lévő pont. a második a verem teteje alatt található pont. Annak tesztelésére, hogy egy A pont van-e egy szegmenstől [BC] balra, ellenőrizzük, hogy a kereszttermék negatív-e, azaz ellenőrizzük, hogy a productVector (A, B, C) ≤ 0 ahol a productVector-t a következő határozza meg:
fonction produit_vectoriel(A, B, C) retourner (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);Megjegyzés : a degenerált esetek kezeléséhez, ahol a domború hajótest háromnál kevesebb ponttal rendelkezik, kezdetben csak egy pontot kell beírni a verembe, és ha valaha a veremnek kevesebb mint két pontja van (mindig lesz legalább egy), akkor a teteje akkor is ki kell húzni, ha az új pont a figyelembe vett pont. Más szavakkal, a "míg" feltételnek a következőnek kell lennie.
pile.hauteur >= 2 et produit_vectoriel(pile.second, pile.sommet, T[i]) <= 0 ou pile.sommet == T[i]A szög szerinti válogatás helyett az abszcissza szerint válogathatunk, majd a konvex borítékot két szakaszban építjük fel: a felső, majd az alsó részbe. Ezt a módosítást Andrew Andrew készítette, és Andrew Monoton Lánc Algoritmusának hívják . Ez az új algoritmus ugyanazokkal a tulajdonságokkal rendelkezik, mint Graham algoritmusa.
A verem használata Graham algoritmusában hasonló az algoritmusban a legközelebbi kisebb értékekkel kapcsolatos problémához . Ezenfelül léteznek párhuzamos algoritmusok erre a problémára, amelyek felhasználhatók a konvex hajótest hatékonyabb kiszámítására.
A numerikus robusztusság egy algoritmus viselkedését érinti a lebegőpontos számok pontossága szempontjából . Egy 2004-es cikk azt vizsgálja, hogy Graham algoritmusa hogyan és miért viselkedhet rosszul a gyenge pontosság miatt. A cikk megoldást kínál. A Graham-Fortune algoritmusnak nevezett Graham-algoritmus kiterjesztése stabilabb.