Marcherende firkanter

Marching Squares (fra engelsk - "moving squares") er en algoritme i computergrafik , der genererer isoliner på et todimensionalt skalarfelt .

Ansøgning

Algoritmen bruges til at visualisere isobarer på vejrkort og konturlinjer på geografiske kort. Det er en forenkling af marcherende terninger-algoritmen for den flade sag.

Sådan virker det

Som input modtager algoritmen et regulært gitter, ved hver knude, hvis værdi feltet er kendt. Outputgitteret (angivet med blåt i figuren) kan have en lavere opløsning (i dette tilfælde går nøjagtigheden tabt, men aliasing reduceres). Dernæst kontrolleres det for hver node i outputgitteret, om værdien i det er højere end på isooverfladen. Alle noder, der er højere, tildeles "+", resten - "-". Dernæst betragter vi kvadraterne af outputgitteret, hvis toppunkter ligger ved de markerede knudepunkter. I alt er der 16 forskellige tilfælde, som under hensyntagen til symmetrier og rotationer kan reduceres til fire:

Tilfælde 1: alle hjørner har samme fortegn
Tilfælde 2: et toppunkt har et andet fortegn
Tilfælde 3: hjørner med samme fortegn har en fælles kant
Tilfælde 4: Hjørner med samme fortegn deler ikke en kant

I det fjerde tilfælde er det umuligt entydigt at bestemme formen af det isoline segment, så værdien i midten af firkanten ses yderligere (hvis inputdataene tillader det). Hvis det er umuligt at finde ud af værdien i midten af pladsen, kan den trufne beslutning påvirke isolinens forbindelse.

Tilfælde 1 : Alle hjørner er over (eller under) isooverfladen.
Tilfælde 2 : Med undtagelse af én er alle toppunkter over (eller under) isooverfladen.
Tilfælde 3 : To spidser på samme kant er over (eller under) isooverfladen.
Tilfælde 4 : To hjørner, der ikke deler en kant, er over (eller under) isooverfladen.
Løsning af tilfælde 4 med en positiv værdi i cellen.
Løsning af tilfælde 4 med en negativ værdi i cellen.

Lineær interpolation bruges til at forbedre kvaliteten af den resulterende isolin . I dette tilfælde deler enden af isoline-segmentet på kanten af kvadratet kanten i forhold til , hvor er værdierne for enderne af kanten af kvadratet, er værdien af isolinen. Faktisk er enden af isoline-segmentet "trukket" til enden af kanten, som er tættere på den rigtige isoline. ${\frac {f_{1}-c}{c-f_{2}}}$ $f_{1},f_{2}$ $c$

Marcherende firkanter

Ansøgning

Sådan virker det

Links