Algoritm för presentinpackning
Inom beräkningsgeometri är presentinpackningsalgoritmen en algoritm för att beräkna det konvexa skrovet för en given uppsättning punkter .
Planar fall
I det tvådimensionella fallet är algoritmen också känd som Jarvis march , efter RA Jarvis, som publicerade den 1973; den har O ( nh ) tidskomplexitet , där n är antalet punkter och h är antalet punkter på det konvexa skrovet. Dess verkliga prestanda jämfört med andra konvexa skrovalgoritmer är gynnsam när n är liten eller h förväntas vara mycket liten med avseende på n [ citat behövs ] . I allmänna fall överträffas algoritmen av många andra (Se Konvexa skrovalgoritmer) .
Algoritm
För enkelhetens skull antar beskrivningen nedan att punkterna är i allmän position , dvs inga tre punkter är kolinjära . Algoritmen kan lätt modifieras för att hantera kollinearitet, inklusive valet om den endast ska rapportera extrema punkter (hörn av det konvexa skrovet) eller alla punkter som ligger på det konvexa skrovet [ citat behövs ] . Dessutom måste det fullständiga genomförandet hantera [ hur? ] med degenererade fall när det konvexa skrovet bara har 1 eller 2 hörn, samt med frågorna om begränsad aritmetisk precision , både datorberäkningar och indata.
Presentinpackningsalgoritmen börjar med i =0 och en punkt p 0 som är känd för att vara på det konvexa skrovet, t.ex. punkten längst till vänster, och väljer punkten p i+1 så att alla punkter är till höger om linjen p i p i +1 . Denna punkt kan hittas i O ( n ) tid genom att jämföra polära vinklar för alla punkter med avseende på punkten pi tagen för mittpunkten av polära koordinater . Att låta i = i +1, och upprepa med tills man når p h = p 0 igen ger det konvexa skrovet i h steg. I två dimensioner liknar presentinslagningsalgoritmen processen att linda ett snöre (eller omslagspapper) runt uppsättningen av punkter.
Tillvägagångssättet kan utvidgas till högre dimensioner.
Pseudokod
Algoritmen jarvis(S) är // S är uppsättningen av punkter // P kommer att vara den uppsättning punkter som bildar det konvexa skrovet. Slutlig uppsättningsstorlek är i. pointOnHull = punkten längst till vänster i S // som garanterat är en del av CH(S) i := 0 repeat P[i] := pointOnHull endpoint := S[0] // initial endpoint för en kandidatkant på skrovet för j från 0 till |S| do // endpoint == pointOnHull är ett sällsynt fall och kan bara inträffa när j == 1 och en bättre slutpunkt ännu inte har ställts in för slingan om (endpoint == pointOnHull) eller (S[j] är till vänster om linjen från P[i] till ändpunkt) sedan ändpunkt := S[j] // hittade större vänstersväng, uppdatera ändpunkt i := i + 1 pointOnHull = ändpunkt tills ändpunkt = P[0] // lindad runt till första skrovpunkt
Komplexitet
Den inre slingan kontrollerar varje punkt i setet S , och den yttre slingan upprepas för varje punkt på skrovet. Därför är den totala körtiden . Körtiden beror på storleken på utdata, så Jarvis's march är en utdatakänslig algoritm .
Men eftersom körtiden beror linjärt på antalet skrovhörn, är den bara snabbare än algoritmer som Graham skannar när antalet h skrovhörn är mindre än log n . Chans algoritm , en annan konvex skrovalgoritm, kombinerar det logaritmiska beroendet av Graham-skanning med utgångskänsligheten för presentinpackningsalgoritmen, vilket uppnår en asymptotisk körtid som förbättrar på både Graham-skanning och presentförpackning.
Se även
- Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "33.3: Hitta det konvexa skrovet". Introduktion till algoritmer (2:a upplagan). MIT Press och McGraw-Hill. s. 955–956. ISBN 0-262-03293-7 .
- Jarvis, RA (1973). "Om identifieringen av det konvexa skrovet av en ändlig uppsättning punkter i planet". Informationsbehandlingsbrev . 2 : 18–21. doi : 10.1016/0020-0190(73)90020-3 .