Vatti klippningsalgoritm
Vatti -klippningsalgoritmen används i datorgrafik . Det tillåter klippning av valfritt antal godtyckligt formade ämnespolygoner med . valfritt antal godtyckligt formade klipppolygoner Till skillnad från polygonklippningsalgoritmerna Sutherland-Hodgman och Weiler-Atherton , begränsar Vatti-algoritmen inte vilka typer av polygoner som kan användas som motiv eller klipp. Även komplexa (självkorsande) polygoner och polygoner med hål kan bearbetas. Algoritmen är generellt endast tillämplig i 2D-rymden .
Beskrivning
Klippning definieras som interaktionen mellan motiv och klipppolygoner. Medan klippning vanligtvis innebär att hitta skärningspunkterna (överlappningsområdena) mellan motiv och klipppolygoner, kan klippningsalgoritmer också tillämpas med andra booleska klippningsoperationer: difference , där klipppolygonerna tar bort överlappande områden från motivet; union , där klippning returnerar de regioner som täcks av antingen ämnes- eller klipppolygoner, och; xor , där klippning returnerar de områden som täcks av antingen ämnes- eller klipppolygoner utom där de täcks av både ämnes- och klipppolygoner.
Vatti-algoritmen involverar att bearbeta både motiv och klippa polygonkanter på ett ordnat sätt, med början med de nedersta kanterna och arbeta mot toppen; detta liknar begreppsmässigt Bentley-Ottmann-algoritmen . Denna sveplinjemetod delar upp problemutrymmet med skanningslinjer , imaginära horisontella linjer som passerar genom varje hörn av de deltagande polygonerna. Dessa skanningslinjer konturerar skanningsstrålar – utrymmena mellan intilliggande skanningslinjer. Dessa avsökningsstrålar bearbetas i sin tur, med början med den lägsta avsökningsstrålen, med algoritmen som lägger till skärningspunkter inom dessa avsökningsstrålar till lösningspolygonerna.
Se även
- Martinez-Rueda_clipping_algorithm
- Greiner–Hormann urklippsalgoritm
- Sutherland–Hodgman urklippsalgoritm
- Weiler–Atherton urklippsalgoritm
- Booleska operationer på polygoner
externa länkar