Konvext hölje
Konvext hölje för en mängd punkter
Om den här räknaren
Räknaren för konvext hölje hittar den minsta konvexa polygon som omsluter en mängd punkter i planet med Andrews algoritm med monoton kedja. Den listar höljets hörn i moturs ordning, räknar hur många punkter som ligger på höljet respektive inuti det och anger exakt area och omkrets, med ett spridningsdiagram där resultatet ritas ut. Dubbletter och punkter på en linje hanteras korrekt.
Så hittar du ett konvext hölje
- Ange dina punkter som x,y-par åtskilda med kommatecken – ordningen spelar ingen roll.
- Räknaren slår ihop dubbletter och sorterar punkterna från vänster till höger.
- Den sveper igenom de sorterade punkterna för att bygga den undre och övre gränsen och behåller bara hörnen där konturen svänger åt vänster.
- Läs av höljets hörn, area och omkrets, och se konturen ritad över dina punkter.
Vanliga exempel
- Kvadratens hörn 0,0 6,0 6,4 0,4 med inre punkterna 3,2 och 2,1 → 4 hörn på höljet, area 24, omkrets 20
- Triangel 0,0 4,0 0,3 → 3 hörn på höljet, area 6, omkrets 12
- Punkter på en linje 0,0 1,1 2,2 3,3 → degenererat hölje (en sträcka), area 0
- Kvadrat 0,0 4,0 4,4 0,4 plus toppen 2,5 → 5 hörn på höljet eftersom toppen sticker ut över den övre kanten
Vanliga frågor
Vad är ett konvext hölje?
Det konvexa höljet till en mängd punkter är den minsta konvexa polygon som innehåller dem alla – som att spänna ett gummiband runt de yttersta punkterna och låta det dra åt.
Vilka punkter blir hörn i höljet?
Bara de yttersta hörnpunkterna ligger på höljet. Punkter som ligger strikt inuti figuren och punkter som hamnar exakt på en kant av höljet listas inte som hörn.
Hur hanteras dubbletter och punkter på en linje?
Identiska punkter slås först ihop. Om alla punkter ligger på samma räta linje faller höljet ihop till en sträcka med arean noll, vilket räknaren redovisar som ett degenererat hölje.
Hur många punkter behövs?
Minst tre olika punkter som inte ligger på en linje krävs för att bilda ett hölje med positiv area.