Marschande torg

Marching Squares (från engelska - "moving squares") är en algoritm inom datorgrafik som genererar isoliner på ett tvådimensionellt skalärt fält .

Applikation

Algoritmen används för att visualisera isobarer på väderkartor och konturlinjer på geografiska kartor. Det är en förenkling av algoritmen för marschkuber för det platta fallet.

Hur det fungerar

Som indata får algoritmen ett vanligt rutnät, vid varje nod vars värde fältet är känt. Utmatningsrutnätet (indikerat i blått i figuren) kan ha en lägre upplösning (i det här fallet går noggrannheten förlorad, men aliasing reduceras). Därefter kontrolleras det för varje nod i utgångsnätet om värdet i det är högre än på isoytan. Alla noder som är högre tilldelas "+", resten - "-". Därefter överväger vi kvadraterna på utmatningsnätet, vars hörn ligger vid de markerade noderna. Totalt finns det 16 olika fall, som, med hänsyn till symmetrier och rotationer, kan reduceras till fyra:

Fall 1: alla hörn har samma tecken
Fall 2: en vertex har ett annat tecken
Fall 3: hörn med samma tecken har en gemensam kant
Fall 4: Vertices med samma tecken delar inte en kant

I det fjärde fallet är det omöjligt att entydigt bestämma formen på det isolinska segmentet, så värdet i mitten av kvadraten ses dessutom (om indata tillåter det). Om det är omöjligt att ta reda på värdet i mitten av torget, kan det fattade beslutet påverka anslutningen av isolinen.

Fall 1 : Alla hörn är över (eller under) isoytan.
Fall 2 : Med undantag för en, är alla hörn över (eller under) isoytan.
Fall 3 : Två hörn på samma kant är ovanför (eller under) isoytan.
Fall 4 : Två hörn som inte delar en kant är ovanför (eller under) isoytan.
Lösning av fall 4 med ett positivt värde i cellen.
Lösning av fall 4 med ett negativt värde i cellen.

Linjär interpolation används för att förbättra kvaliteten på den resulterande isolinen . I det här fallet delar änden av isolinsegmentet på kanten av kvadraten kanten i förhållande till , där är värdena i ändarna av kanten av kvadraten, är värdet på isolinen. Faktum är att änden av isolinsegmentet "dras" till änden av kanten, som är närmare den riktiga isolinen. ${\frac {f_{1}-c}{c-f_{2}}}$ $f_{1},f_{2}$ $c$

Länkar

Implementering i Java
Marching Square Matlab-algoritm — En lättförståelig marschkvadratalgoritm med öppen källkod.
Isoline Isoband - Algoritmbeskrivningar och öppen källkod C / Fortran -kod för AVS vetenskapliga visualiseringssystem (Mike French, 1992).