Wyler-Atherton algoritm
Weiler-Atherton- algoritmen ( Weiler -Atherton , Weiler-Atherton ) används i datorgrafik för att klippa (att hitta skärningsområdet) av en klipppolygon längs en klipppolygon , även kallad ett fönster . Utskurna och skära polygoner kan vara icke-konvexa. Algoritmen är endast tillämplig för platta figurer.
Ingångspolygonerna måste ha en fast gränsövergångsriktning (låt oss säga medurs), och får inte ha självkorsningar . Algoritmen kan hantera polygoner med hål (hål anges som polygoner med motsatt riktning), men kräver ytterligare algoritmer för att avgöra vilka av polygonerna som är hål.
Algoritmen kan modifieras för att slå samman två polygoner.
Algoritm
- Från koordinaterna för hörnen för polygonerna A och B sammanställs två listor.
- Topparna i var och en av listorna är märkta efter om de är inuti den andra polygonen eller inte.
- Polygon skärningspunkter läggs till i båda listorna; tvåvägslänkar upprättas mellan sammanfallande punkter i olika listor.
- Om ingen korsning hittas inträffar en av följande situationer:
- A inuti B - returnera A när den är trunkerad, B när den kombineras.
- B inuti A - returnera B när den är trunkerad, A när den kombineras.
- A och B korsar varandra inte - returnera en tom uppsättning när den är trunkerad, A&B när den kombineras.
- En lista över skärningspunkter sammanställs där gränsen för polygon A, när den korsas, går in i polygon B. Efter varje sådan punkt medurs längs gränserna för både polygonerna A och B, kan man hitta en uppsättning skärningsområden. I fallet när A och B är konvexa finns det bara en skärningspolygon. På samma sätt kan du hitta föreningen av polygoner, i detta fall måste genomgången börja med utgångspunkterna.
Se även
Länkar