I datavitenskap og i beregningsgeometri er Graham-banen (også kalt Grahams algoritme ) en algoritme for å beregne den konvekse konvolutten til et sett med punkter i planet. Hovedinteressen er dens algoritmiske kompleksitet i O (n log n) hvor n er antall poeng. Denne algoritmen er oppkalt etter Ronald Graham , som publiserte den opprinnelige algoritmen i 1972 .
Algoritmen tar som inngang en rekke punkter, som vist i følgende figur:
Det første trinnet i denne algoritmen er å finne punktet med den minste ordinaten , kalt pivot . Hvis flere punkter har samme minste ordinat, velger algoritmen blant dem punktet med minste abscisse . Som vist i figuren nedenfor, er svingpunktet det laveste punktet til venstre. Svingpunktet blir nå punkt nummer 1.
Punktsettet (inkludert pivot) blir deretter sortert i henhold til vinkelen som hver av dem lager med x-aksen i forhold til pivot. Enhver sammenligningssorteringsalgoritme er egnet for dette, for eksempel haugsortering eller flettesortering (som er optimale og har en kompleksitet på O (n log n) ). For dette er det ikke nødvendig å beregne den virkelige vinkelen; man kan begrense seg til sammenligningen av tangentene, eller til og med bruke kryssproduktet til koordinatene for å kjenne de relative posisjonene til punktene. På slutten av dette trinnet er det en matrise T som inneholder de punktene som er sortert. Følgende figur viser punktene som er nummerert for å respektere sorteringsrekkefølgen.
Algoritmen konstruerer iterativt den konvekse konvolutten (i grønt i følgende figur). Vi starter med dreietappen. Deretter undersøker vi punktene i rekkefølgen på den sorterte matrisen (punktet som skal undersøkes vises i svart). Ved hvert trinn ser vi for å se om det er en "venstresving" (som i trinn 2, 5, 13, 15 på eksemplet gitt i figuren) eller en "høyre sving" (som i trinn 10, 17, 18 av eksemplet).
På slutten (trinn 19 og deretter 20) har algoritmen beregnet den konvekse konvolutten.
For å avgjøre om tre punkter utgjør en "venstresving" eller en "høyresving", krever ikke beregning av den faktiske vinkelen mellom de to segmentene , og kan oppnås ved enkel regning. For tre punkter (x 1 , y 1 ), (x 2 , y 2 ) og (x 3 , y 3 ) er det tilstrekkelig å beregne retningen til kryssproduktet til de to vektorene definert av punktene (x 1 , y 1 ), (x 2 , y 2 ) og (x 1 , y 1 ), (x 3 , y 3 ), gitt av tegnet på uttrykket (x 2 - x 1 ) (y 3 - y 1 ) - ( y 2 - y 1 ) (x 3 - x 1 ). Hvis resultatet er null, blir punktene justert. Hvis det er positivt, utgjør de tre punktene en "venstresving". Ellers er det en “høyresving”.
Denne prosessen vil til slutt gå tilbake til det tidspunktet den startet, i hvilket tilfelle algoritmen vil bli avsluttet, og returnere punktene som danner den konvekse konvolutten, i moturs rekkefølge. På eksemplet, punkt 1, 2, 3, 6 og 9.
Tidskompleksiteten til valget av dreietappen er i Θ (n), n er antall punkter i settet. Sorteringen av punktene kan gjøres med en tidskompleksitet i O (n log n) . Kompleksiteten til hovedsløyfen kan se ut til å være Θ (n 2 ), fordi algoritmen går tilbake på hvert punkt for å vurdere om noen av de forrige punktene er en "høyresving". Men det er faktisk ved O (n), fordi hvert punkt bare blir vurdert en gang. Dermed slutter hvert analyserte punkt enten sub-loop, eller blir fjernet fra T og blir derfor aldri vurdert igjen. Den totale kompleksiteten til algoritmen er derfor i O (n log n) , siden kompleksiteten av sorteringen dominerer kompleksiteten til den effektive beregningen av den konvekse konvolutten.
La T være et sett med punkter som skal undersøkes, representert i form av en matrise indeksert fra en. I løpet av algoritmen lagres polygonen som konstrueres i en stabel .
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 pilehvor stack.second er punktet på toppen av stacken og stack.second er punktet under toppen av stabelen. For å teste at et punkt A er til venstre for et segment [BC], sjekker vi at kryssproduktet er negativt, dvs. vi sjekker at productVector (A, B, C) ≤ 0 der productVector er definert av:
fonction produit_vectoriel(A, B, C) retourner (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);Merk : for å håndtere degenererte tilfeller der det konvekse skroget har mindre enn tre punkter, skal bare ett punkt innføres i bunken i utgangspunktet, og hvis noen gang bunken har mindre enn to punkter (den vil alltid ha minst ett), så er toppen av stakken skal også trekkes ut hvis det nye punktet er det ansett punktet. Med andre ord bør tilstanden til "while" være som følger.
pile.hauteur >= 2 et produit_vectoriel(pile.second, pile.sommet, T[i]) <= 0 ou pile.sommet == T[i]I stedet for å sortere etter vinkelen, kan vi sortere etter abscissen, så bygger vi den konvekse konvolutten i to trinn: den øvre delen og deretter den nedre delen. Denne modifikasjonen ble opprettet av AM Andrew og kalles Andrews monotone kjeden algoritme . Denne nye algoritmen har de samme egenskapene som Grahams algoritme.
Bruken av en stabel i Grahams algoritme er lik den som gjøres i algoritmen for det nærmeste mindre verdiproblemet . Dessuten er det parallelle algoritmer for dette problemet som kan brukes til å beregne det konvekse skroget mer effektivt.
Numerisk robusthet gjelder oppførselen til en algoritme med hensyn til presisjonen til flytende punktum . En artikkel fra 2004 undersøker hvordan og hvorfor Grahams algoritme kan oppføre seg dårlig på grunn av dårlig presisjon. Artikkelen tilbyr en løsning. En utvidelse av Graham-algoritmen, kalt Graham-Fortune-algoritmen, er mer stabil.