Jarvis Walk

I beregningsgeometri er Jarvis-gangen en algoritme til beregning af det konvekse skrog af et endeligt sæt punkter. Ideen med algoritmen er at ” wrap ” det sæt af punkter i en ” indpakning papir ”: vi hook dette papir til et af de punkter, strække vi det, så vi vende omkring det punkt sky.

Princip

Lad være det indledende punkt, hvor papiret hænges op. $p_ {0}$

Det første punkt, papiret støder på, er , så ... indtil det findes . $p_1$ $p_2$ $p_ {0}$

Mere formelt for hvert nye toppunkt i den konvekse konvolut, der er fundet, er det et spørgsmål om at finde den næste ved at beregne punktet for den minimale polære vinkel i forhold til . $p_ {i}$ $p_ {i}$

I praksis opdeler vi ruten i to: fra punktet med minimum abscissa, derefter fra punktet med maksimal abscissa.

Algoritme

fonction marcheJarvis(E) p := un point d'abscisse minimale dans E L := liste vide répéter insérer p dans L p := point p' de E tel que [pp') est le plus incliné vers la gauche (1) jusqu’à p = p0 retourner L

Linje (1) udføres som følger:

pour tout p' de E Si p'' = p' ou p' est à gauche de [pp') alors p'' = p' p := p

Loopens krop gentages - indtil udføres så mange gange, som der er punkter i den konvekse konvolut. Linje (1) er inde . Derfor en kompleksitet i , hvor repræsenterer antallet af hjørner af den konvekse konvolut. $Vi)$ ${\ displaystyle O (nh)}$ $h$

Eksternt link

(fr) [1] , Kursus ved University of Montpellier 2

Noter og referencer

RA Jarvis , “ Om identifikation af det konvekse skrog af et endeligt sæt punkter i flyet, ” Information Processing Letters , vol. 2,1 st marts 1973, s. 18–21 ( DOI 10.1016 / 0020-0190 (73) 90020-3 , læst online , adgang 25. marts 2016 )

Se også

Relaterede artikler