Polygontriangulering

I beräkningsgeometri är polygontriangulering uppdelningen av ett polygonområde ( enkel polygon ) $P$ $i$ en uppsättning trianglar , dvs att hitta en uppsättning trianglar med parvis icke-skärande interiörer vars förening är P.

Triangulering kan ses som speciella fall av plana rätlinjediagram . När det inte finns några hål eller tillagda punkter, bildar triangulering maximala ytterplanära grafer .

Polygontriangulering utan extra hörn

Med tiden har ett antal algoritmer föreslagits för att triangulera en polygon.

Speciella fall

De 42 möjliga trianguleringarna för en konvex heptagon (7-sidig konvex polygon). Detta nummer ges av det 5:e katalanska numret .

Det är trivialt att triangulera vilken konvex polygon som helst i linjär tid till en fläkttriangulering , genom att lägga till diagonaler från en vertex till alla andra icke-närmaste grannhörn.

Det totala antalet sätt att triangulera en konvex n -gon med icke-korsande diagonaler är det ( n −2):a katalanska talet , som är lika med

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

,

en formel hittad av Leonhard Euler .

En monoton polygon kan trianguleras i linjär tid med antingen algoritmen för A. Fournier och DY Montuno, eller algoritmen för Godfried Toussaint .

Öronklippningsmetod

Ett polygonöra

Ett sätt att triangulera en enkel polygon är baserat på tvåöronsatsen , eftersom det faktum att varje enkel polygon med minst 4 hörn utan hål har minst två " öron ", som är trianglar med två sidor som kanterna på polygonen och den tredje helt inne i den. Algoritmen består sedan av att hitta ett sådant öra, ta bort det från polygonen (vilket resulterar i en ny polygon som fortfarande uppfyller villkoren) och upprepa tills det bara finns en triangel kvar.

Denna algoritm är lätt att implementera, men långsammare än vissa andra algoritmer, och den fungerar bara på polygoner utan hål. En implementering som håller separata listor över konvexa och konkava hörn kommer att köras i $O(n 2)$ tid. Denna metod kallas öronklippning och ibland öronklippning . En effektiv algoritm för att skära av öron upptäcktes av Hossam ElGindy, Hazel Everett och Godfried Toussaint .

Monotone polygontriangulering

Dela en polygon i monotona polygoner

En enkel polygon är monoton med avseende på en linje $L$ , om någon linje som är ortogonal mot $L$ skär polygonen högst två gånger. En monoton polygon kan delas upp i två monotona kedjor . En polygon som är monoton med avseende på y-axeln kallas y-monotone . En monoton polygon med $n$ hörn kan trianguleras i $O(n)$ tid. Om man antar att en given polygon är y-monoton, börjar den giriga algoritmen med att gå på en kedja av polygonen uppifrån och ned samtidigt som diagonaler läggs till närhelst det är möjligt. Det är lätt att se att algoritmen kan appliceras på vilken monoton polygon som helst.

Triangulering av en icke-monotone polygon

Om en polygon inte är monoton kan den delas upp i monotona subpolygoner på $O(n log n)$ tid med en sveplinjemetod . Algoritmen kräver inte att polygonen är enkel, så den kan appliceras på polygoner med hål. Generellt kan denna algoritm triangulera en plan underavdelning med $n$ hörn i $O(n log n)$ -tid med användning av $O(n)$ -rymden.

Dubbel graf av en triangulering

En användbar graf som ofta förknippas med en triangulering av en polygon $P$ är den dubbla grafen . Givet en triangulering $TP P$ av definierar man grafen $G (T P)$ som grafen vars vertexuppsättning är trianglarna för $TP , varvid$ två hörn (trianglar) ligger intill om och endast om de delar en diagonal $.$ Det är lätt att observera att $G (T P)$ är ett träd med maximal grad 3.

Beräkningskomplexitet

Fram till 1988 var huruvida en enkel polygon kan trianguleras snabbare än $O(n log n)$ tid ett öppet problem inom beräkningsgeometri. Sedan upptäckte Tarjan & Van Wyk (1988) en $O(n log log n)$ -tidsalgoritm för triangulering, senare förenklad av Kirkpatrick, Klawe & Tarjan (1992) . Flera förbättrade metoder med komplexitet $O(n log * n)$ (i praktiken omöjlig att skilja från linjär tid ) följde.

Bernard Chazelle visade 1991 att vilken enkel polygon som helst kan trianguleras i linjär tid, även om den föreslagna algoritmen är mycket komplex. En enklare randomiserad algoritm med linjär förväntad tid är också känd.

Seidels nedbrytningsalgoritm och Chazelles trianguleringsmetod diskuteras i detalj i Li & Klette (2011) .

Tidskomplexiteten för triangulering av en $n$ -vertexpolygon med hål har en $Ω(log n) nedre$ n gräns , i algebraiska beräkningsträdmodeller för beräkning. Det är möjligt att beräkna antalet distinkta trianguleringar av en enkel polygon i polynomtid med hjälp av dynamisk programmering och (baserat på denna räknealgoritm) att generera enhetligt slumpmässiga trianguleringar i polynomtid. Att räkna trianguleringarna för en polygon med hål är dock #P-komplett , vilket gör det osannolikt att det kan göras i polynomtid.

Relaterade objekt och problem

Båda trianguleringsproblemen är ett specialfall av triangulering (geometri) och ett specialfall av polygonpartition .
Minimiviktstriangulering är en triangulering där målet är att minimera den totala kantlängden.
En punktuppsättningstriangulering är en polygontriangulering av det konvexa skrovet av en uppsättning punkter. En Delaunay-triangulering är ett annat sätt att skapa en triangulering baserat på en uppsättning punkter.
Associaedern är en polytop vars hörn motsvarar trianguleringarna av en konvex polygon .
Polygontriangeltäckning , där trianglarna kan överlappa varandra.
Plattläggning av polygoner , där målet är att täcka hela planet med polygoner av fördefinierade former.

Se även

externa länkar

Demo som Flash swf , A Sweep Line-algoritm.
Song Hos förklaring av OpenGL GLU-tesselatorn