Bowyer-Watson-algoritme

I beregningsmæssige geometri Bowyer-Watson algoritme er en fremgangsmåde til beregning af Delaunay triangulering af et finit sæt af punkter i et vilkårligt antal dimensioner. Kan anvendes algoritmen for at opnå en voronoi diagram over de punkter, som er den dobbelte graf af Delaunay triangulering.

Den Bowyer-Watson algoritme er en trinvis algoritme. Det virker ved at tilføje punkter, ét ad gangen, til en gyldig Delaunay triangulering af en delmængde af de ønskede punkter. Efter hver indsættelse, er nogen trekanter hvis circumcircles indeholder det nye punkt slettet, efterlader en stjerne-formet polygonal hul, som derefter igen trianguleret hjælp af den nye punkt. Ved at bruge konnektivitet af triangulering man effektivt lokalisere trekanter til at fjerne, kan algoritmen tage O operationer for at triangulere N punkter, selv om særlige degenererede tilfælde foreligge, hvor det går op til O.

Algoritmen er også kendt ligesom Bowyer algoritme eller Watson algoritme. Adrian Bowyer og David Watson udtænkt det uafhængigt af hinanden på samme tid, og hver offentliggjort et dokument om den i samme nummer af The Computer Journal.

Pseudokode

Følgende pseudokode beskriver en grundlæggende implementering af Bowyer-Watson algoritme. Effektivitet kan forbedres på en række forskellige måder. For eksempel kan trekanten forbindelse anvendes til at lokalisere trekanter, som indeholder det nye punkt i deres circumcircle, uden at skulle kontrollere alle trekanterne. Pre-computing circumcircles kan spare tid på bekostning af ekstra hukommelse skik. Og hvis de punkter jævnt fordelt, sortering dem langs et rum påfyldning Hilbert kurve før indsættelse kan også fremskynde punkt placering.

  0   0
Forrige artikel Bennington Gratis Bibliotek
Næste artikel Bouillon

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha