Konvext skrov av en enkel polygon
I diskret geometri och beräkningsgeometri är det konvexa skrovet av en enkel polygon polygonen med minsta omkrets som innehåller en given enkel polygon . Det är ett specialfall av det mer allmänna konceptet med ett konvext skrov . Det kan beräknas i linjär tid , snabbare än algoritmer för konvexa skrov av punktuppsättningar .
Det konvexa skrovet av en enkel polygon kan delas in i den givna polygonen själv och i polygonala fickor som begränsas av en polygonal kedja av polygonen tillsammans med en enda konvex skrovkant. Att upprepade gånger reflektera en godtyckligt vald ficka över denna konvexa skrovkant producerar en sekvens av större enkla polygoner; enligt Erdős–Nagy-satsen avslutas denna process så småningom med en konvex polygon.
Strukturera
Det konvexa skrovet av en enkel polygon är i sig en konvex polygon . Genom att överlagra den ursprungliga enkla polygonen på dess konvexa skrov delas denna konvexa polygon in i regioner, varav en är den ursprungliga polygonen. De återstående regionerna kallas fickor . Varje ficka är i sig en enkel polygon, avgränsad av en polygonal kedja på gränsen för den givna enkla polygonen och av en enda kant av det konvexa skrovet. En polygon som redan är konvex har inga fickor.
Man kan bilda en hierarkisk beskrivning av en given polygon genom att konstruera dess skrov och dess fickor på detta sätt och sedan rekursivt bilda en hierarki av samma typ för varje ficka. Denna struktur, som kallas ett konvext skillnadsträd , kan konstrueras effektivt.
Algoritmer
Att hitta det konvexa skrovet av en enkel polygon kan utföras i linjär tid . Flera tidiga publikationer om detta problem upptäcktes vara felaktiga, ofta för att de ledde till mellantillstånd med korsningar som fick dem att gå sönder. Den första korrekta linjära tidsalgoritmen för detta problem gavs av McCallum & Avis (1979) . Även efter publiceringen fortsatte andra felaktiga algoritmer att publiceras. Brönnimann & Chan (2006) skriver att en majoritet av de publicerade algoritmerna för problemet är felaktiga, även om en senare historik insamlad av Greg Aloupis listar endast sju av femton algoritmer som felaktiga.
En särskilt enkel algoritm för detta problem publicerades av Graham & Yao (1983) och Lee (1983) . Liksom Graham-skanningsalgoritmen för konvexa skrov av punktuppsättningar, är den baserad på en stackdatastruktur . Algoritmen korsar polygonen i medurs ordning, med början från en vertex som är känd för att vara på det konvexa skrovet (till exempel dess punkt längst till vänster). När den gör det lagrar den en konvex sekvens av hörn på stapeln, de som ännu inte har identifierats som i fickorna. Punkterna i denna sekvens är hörnen på en konvex polygon (inte nödvändigtvis skrovet på alla hörn som vi sett hittills) som kan ha fickor fästa vid några av sina kanter. Vid varje steg följer algoritmen en bana längs polygonen från stapeltoppen till nästa vertex som inte finns i en av de två fickorna intill stapeltoppen. Sedan, medan de två översta hörnen på stapeln tillsammans med denna nya vertex inte är i konvex position, skjuter den upp stapeln, innan den till slut skjuter den nya vertexen på stapeln. När medurs traverseringen når startpunkten är algoritmen klar och stacken innehåller de konvexa skrovets hörn i medurs ordning. Varje steg i algoritmen skjuter antingen en vertex på stapeln eller poppar den från stapeln, och varje vertex skjuts och skjuts högst en gång, så den totala tiden för algoritmen är linjär. Om ingångspunkten ges i medurs ordning i en array, då kan utgången returneras i samma array, med endast ett konstant antal ytterligare variabler som mellanlagring.
En liknande metod kan också användas för att konstruera konvexa skrov av styckvis jämna slutna kurvor i planet. Genom att använda en deque i stället för en stack, kan en liknande algoritm generaliseras till det konvexa skrovet av vilken polygonal kedja som helst, och algoritmen för enkla polygoner kan startas vid valfri vertex av polygonen istället för att kräva en extrem vertex som startpunkt .
Vändbara fickor
En vändning av en ficka konstruerar en ny polygon från den givna genom att reflektera den polygonala kedjan som avgränsar en ficka över fickans konvexa skrovkant. Varje vändning producerar en annan enkel polygon med samma omkrets och större yta, även om flera samtidiga vändningar kan introducera korsningar. Att vända en godtyckligt vald ficka och sedan upprepa denna process med fickorna för varje successivt bildad polygon, producerar en sekvens av enkla polygoner. Enligt Erdős-Nagy-satsen avslutas denna vändningsprocess så småningom genom att nå en konvex polygon. Liksom med problemet med konvex skrovkonstruktion har detta problem en lång historia av felaktiga bevis.