Greiner–Hormann urklippsalgoritm
Greiner -Hormann-algoritmen används i datorgrafik för polygonklippning . Den presterar bättre än Vatti-klippningsalgoritmen , men kan inte hantera degenerationer . Den kan bearbeta både självskärande och icke-konvexa polygoner. Det kan trivialt generaliseras att beräkna andra booleska operationer på polygoner , såsom union och skillnad.
Algoritmen är baserad på definitionen av "insidan" av en polygon baserat på lindningsnumret . Den anser att regioner med udda lindningsnummer är inuti polygonen; detta kallas jämn-udda-regeln . Det tar två listor med polygoner som indata.
I sin ursprungliga form är algoritmen uppdelad i tre faser:
- I den första fasen beräknas parvisa skärningar mellan kanterna på polygonerna. Ytterligare hörn infogas i båda polygonerna vid skärningspunkterna; en skärningspunkt håller en pekare till sin motsvarighet i den andra polygonen.
- I den andra fasen markeras varje korsning som antingen en infartskorsning eller en avfartskorsning . Detta åstadkoms genom att utvärdera den jämna-udda-regeln vid den första vertexen, som låter dig veta om den första vertexen är innanför eller utanför den andra polygonen. Sedan, efter polygonens gränser, markeras korsningarna med alternerande flaggor (nästa korsning efter en infartskorsning måste vara en utfartskorsning).
- I den tredje fasen genereras resultatet. Algoritmen startar vid en obearbetad korsning och väljer korsningsriktningen baserat på in-/utfartsflaggan: för en infartskorsning går den framåt, och för en utfartskorsning går den bakåt. Vertices läggs till i resultatet tills nästa korsning hittas; Algoritmen växlar sedan till motsvarande skärningspunkt i den andra polygonen och väljer genomgångsriktningen igen med samma regel. Om nästa korsning redan har bearbetats avslutar algoritmen den aktuella komponenten av utdata och börjar om från en obearbetad korsning. Utmatningen är klar när det inte finns fler obearbetade korsningar.
Algoritmen är inte begränsad till polygoner och kan hantera godtyckliga parametriska kurvor som segment, så länge det finns en lämplig parvis skärningsprocedure.
En stor brist med den ursprungliga Greiner-Hormann-algoritmen är det faktum att den inte kan hantera degenerationer, såsom gemensamma kanter eller skärningar exakt i en vertex. Originalpapperet föreslår att man ska störa hörnen för att ta bort dem.
Se även
- Vatti klippningsalgoritm
- Sutherland–Hodgman urklippsalgoritm
- Weiler–Atherton urklippsalgoritm
- Booleska operationer på polygoner
externa länkar
- Geografisk klippning Beskriver urklippsalgoritmerna i D3.js.
- https://github.com/helderco/univ-polyclip En implementering i Python och Java.
- https://github.com/w8r/GreinerHormann En implementering i JavaScript
- JTS Topological Suite En topologisk svit med en Java-implementering