Rakt skelett

Krympprocessen, det raka skelettet (blått) och takmodellen.

Inom geometrin är ett rakt skelett en metod för att representera en polygon med ett topologiskt skelett . Det liknar på vissa sätt den mediala axeln men skiljer sig genom att skelettet är sammansatt av raka linjesegment, medan en polygons mediala axel kan involvera paraboliska kurvor. Båda är dock homotopi-ekvivalenta med den underliggande polygonen.

Raka skelett definierades först för enkla polygoner av Aichholzer et al. (1995) , och generaliserat till plana rätlinjediagram (PSLG) av Aichholzer & Aurenhammer (1996) . I sin tolkning som projektion av takytor diskuteras de redan utförligt av GA Peschka ( 1877 ).

Definition

En polygons raka skelett definieras av en kontinuerlig krympningsprocess där kanterna på polygonen flyttas inåt parallellt med sig själva med konstant hastighet. När kanterna rör sig på detta sätt rör sig även de hörn där par av kanter möts, med hastigheter som beror på vinkeln på vertexet. Om en av dessa rörliga hörn kolliderar med en icke intilliggande kant, delas polygonen i två av kollisionen, och processen fortsätter i varje del. Det raka skelettet är den uppsättning kurvor som spåras ut av de rörliga hörnen i denna process. I illustrationen visar den översta figuren krympningsprocessen och den mittersta figuren visar det raka skelettet i blått.

Algoritmer

Det raka skelettet kan beräknas genom att simulera den krympningsprocess genom vilken det definieras; ett antal variantalgoritmer för att beräkna det har föreslagits, som skiljer sig åt i antagandena de gör på inmatningen och i de datastrukturer de använder för att detektera kombinatoriska förändringar i ingångspolygonen när den krymper.

Följande algoritmer tar hänsyn till en indata som bildar en polygon, en polygon med hål eller en PSLG. För en polygonal ingång betecknar vi antalet hörn med n och antalet reflexpunkter (konkava, dvs. vinkel större än π ) med r . Om ingången är en PSLG så betraktar vi den initiala vågfrontsstrukturen, som bildar en uppsättning polygoner, och återigen betecknar med n antalet hörn och med r antalet reflexhörn wrt utbredningsriktningen. De flesta av algoritmerna som listas här är designade och analyserade i den verkliga RAM- modellen för beräkning.

  • Aichholzer et al. visade hur man beräknar raka skelett av PSLGs i tiden O( n 3 log n ), eller mer exakt tid O(( n 2 + f ) log n ), där n är antalet hörn av ingångspolygonen och f är talet av flip-händelser under bygget. Den mest kända gränsen för f är O( n 3 ).
  • En algoritm med en värsta gångtid i O( nr log n), eller helt enkelt O( n 2 log n), ges av Huber och Held ( 2010 , 2011 ), som hävdar att deras tillvägagångssätt sannolikt kommer att köras i nära- linjär tid för många ingångar.
  • Petr Felkel och Štěpán Obdržálek designade en algoritm för enkla polygoner som sägs ha effektiviteten O( nr + n log r ) . Det har dock visat sig att deras algoritm är felaktig.
  • Genom att använda datastrukturer för problemet med det bikromatiska närmaste paret visade Eppstein och Erickson hur man konstruerar raka skelettproblem med hjälp av ett linjärt antal uppdateringar av närmaste pars datastruktur. En datastruktur av närmaste par baserad på quadtrees tillhandahåller en O( nr + n log n ) tidsalgoritm, eller så leder en betydligt mer komplicerad datastruktur till den bättre asymptotiska tidsbundna O( n 1 + ε + n 8/11 + ε r 9 /11 + ε ) , eller enklare O( n 17/11 + ε ) , där ε är vilken konstant som helst som är större än noll. Detta är fortfarande den bästa värsta tänkbara tidsgränsen som är känd för rak skelettkonstruktion med obegränsade ingångar, men är komplicerad och har inte implementerats.
  • För enkla polygoner i allmän position är problemet med rak skelettkonstruktion lättare. Cheng, Mencel och Vigneron visade hur man beräknar det raka skelettet av enkla polygoner i tiden O( n log n log r + r 4/3 + ε ). I värsta fall r vara i storleksordningen n , i vilket fall denna tidsbundna kan förenklas till O( n 4/3+ε ). Om hörn av ingångspolygonen har O(log n)-bitars rationella koordinater, kan deras algoritm förbättras för att köras i O( n log n ) tid, även om ingångspolygonen inte är i allmän position .
  •   En monoton polygon med avseende på en linje L är en polygon med egenskapen att varje linje ortogonal mot L skär polygonen i ett enda intervall. När ingången är en monoton polygon kan dess raka skelett konstrueras i tiden O( n log 2 n ).

Ansökningar

Varje punkt inom inmatningspolygonen kan lyftas in i tredimensionellt utrymme genom att använda tiden då krympningsprocessen når den punkten som z-koordinaten för punkten. Den resulterande tredimensionella ytan har konstant höjd på polygonens kanter och stiger med konstant lutning från dem förutom punkterna på själva det raka skelettet, där ytfläckar i olika vinklar möts. På så sätt kan det raka skelettet användas som uppsättningen av nocklinjer på ett byggnadstak, baserat på väggar i form av den initiala polygonen. Den nedre figuren i illustrationen föreställer en yta som på detta sätt bildas av det raka skelettet.

Demaine, Demaine och Lubiw använde det raka skelettet som en del av en teknik för att vika ett pappersark så att en given polygon kan skäras från det med ett enda rakt snitt (vik-och-klipp-satsen) , och relaterade origamidesignproblem .

Barequet et al. använd raka skelett i en algoritm för att hitta en tredimensionell yta som interpolerar mellan två givna polygonala kedjor .

Tănase och Veltkamp föreslår att bryta ned konkava polygoner till sammanslutningar av konvexa regioner med hjälp av raka skelett, som ett förbearbetningssteg för formmatchning vid bildbehandling.

Bagheri och Razzazi använder raka skelett för att styra placeringen av vertex i en grafritningsalgoritm där grafritningen är begränsad till att ligga innanför en polygonal gräns.

Det raka skelettet kan också användas för att konstruera en förskjuten kurva av en polygon, med geringshörn , analogt med konstruktionen av en förskjuten kurva med rundade hörn bildade från den mediala axeln. Tomoeda och Sugihara tillämpar denna idé i utformningen av skyltar, synliga från vida vinklar, med ett illusoriskt utseende av djup. På liknande sätt använder Asente och Carr raka skelett för att designa färggradienter som matchar bokstavskonturer eller andra former.

Som med andra typer av skelett, såsom mediala axeln , kan det raka skelettet användas för att kollapsa ett tvådimensionellt område till en förenklad endimensionell representation av området. Till exempel beskriver Haunert och Sester en tillämpning av denna typ för raka skelett i geografiska informationssystem, för att hitta vägarnas mittlinjer.

Varje träd utan grad -två hörn kan realiseras som det raka skelettet av en konvex polygon . Det konvexa skrovet av takformen som motsvarar detta raka skelett bildar en Steinitz-förverkligande av Halin-grafen som bildas av trädet genom att förbinda dess löv i en cykel.

Högre dimensioner

Barequet et al. definierade en version av raka skelett för tredimensionella polyedrar , beskrev algoritmer för att beräkna det och analyserade dess komplexitet på flera olika typer av polyeder.

Huber et al. undersökte metriska utrymmen under vilka motsvarande Voronoi-diagram och raka skelett sammanfaller. För två dimensioner är karakteriseringen av sådana metriska utrymmen klar. För högre dimensioner kan denna metod tolkas som en generalisering av raka skelett av vissa ingående former till godtyckliga dimensioner med hjälp av Voronoi-diagram.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Straight_skeleton&oldid=1140543035 "