Begränsad Delaunay-triangulering

Inom beräkningsgeometri är en begränsad Delaunay-triangulering en generalisering av Delaunay-trianguleringen som tvingar in vissa nödvändiga segment i trianguleringen som kanter, till skillnad från själva Delaunay-trianguleringen som är baserad enbart på positionen för en given uppsättning av hörn utan hänsyn till hur de ska förbindas med kanter. Den kan beräknas effektivt och har tillämpningar i geografiska informationssystem och i mesh-generering.

Definition

Ingången till det begränsade Delaunay-trianguleringsproblemet är en plan rätlinjegraf , en uppsättning punkter och icke-korsande linjesegment i planet. Den begränsade Delaunay-trianguleringen av denna ingång är en triangulering av dess konvexa skrov , inklusive alla ingångssegment som kanter, och med endast ingångens hörn. För varje ytterligare kant $e$ som läggs till denna inmatning för att göra den till en triangulering, bör det finnas en cirkel genom ändpunkterna för ${\displaystyle e} ,$ så att eventuell vertex inuti cirkeln blockeras från synlighet från minst en slutpunkt för $e$ av ett segment av ingången. Detta generaliserar den definierande egenskapen hos tvådimensionella Delaunay-trianguleringar av punkter, att varje kant har en cirkel genom sina två ändpunkter som inte innehåller några andra hörn. En triangulering som uppfyller dessa egenskaper finns alltid.

Jonathan Shewchuk har generaliserat denna definition till begränsade Delaunay-trianguleringar av tredimensionella ingångar, system av punkter och icke-korsande segment och trianglar i tredimensionellt rum; dock har inte varje input av denna typ en begränsad Delaunay-triangulering enligt hans generaliserade definition.

Algoritmer

Flera algoritmer för beräkning av begränsade Delaunay-trianguleringar av plana rätlinjediagram i tiden $O(n\log n)$ är kända. Den begränsade Delaunay-trianguleringen av en enkel polygon kan konstrueras i linjär tid .

Ansökningar

Vid topografisk mätning konstruerar man en triangulering från punkter skjutna i fält. Om en kant av trianguleringen korsar en flod, modellerar den resulterande ytan inte flodens väg exakt. Så man ritar brytlinjer längs floder, kanter av vägar, bergsryggar och liknande. Brytlinjerna används som begränsningar vid konstruktion av trianguleringen.

Begränsad Delaunay-triangulering kan också användas i Delaunay-förfiningsmetoder för nätgenerering , som ett sätt att tvinga nätet att överensstämma med domängränserna när det förfinas.

externa länkar

• [1] Implementering av öppen källkod.