Marssivat neliöt

Marching Squares ( englanniksi - "liikkuvat neliöt") on tietokonegrafiikassa oleva algoritmi, joka luo isolineja kaksiulotteiseen skalaarikenttään .

Sovellus

Algoritmia käytetään visualisoimaan isobaarit sääkartoilla ja ääriviivat maantieteellisillä kartoilla . Se on yksinkertaistettu marssikuutioiden algoritmia litteälle kotelolle.

Kuinka se toimii

Algoritmi vastaanottaa syötteenä säännöllisen ruudukon, jonka jokaisessa solmussa kentän arvo tiedetään. Tulostusruudukon (merkitty sinisellä kuvassa) resoluutio voi olla pienempi (tässä tapauksessa tarkkuus menetetään, mutta aliasointi vähenee). Seuraavaksi jokaiselle lähtöruudukon solmulle tarkistetaan, onko siinä oleva arvo suurempi kuin isopinnalla. Kaikille korkeammille solmuille on annettu "+", loput - "-". Seuraavaksi tarkastellaan lähtöruudukon neliöitä, joiden kärjet ovat merkittyissä solmuissa. Yhteensä on 16 erilaista tapausta, jotka voidaan symmetriat ja kierrokset huomioon ottaen vähentää neljään:

Tapaus 1: kaikilla pisteillä on sama merkki
Tapaus 2: yhdellä kärjellä on eri merkki
Tapaus 3: pisteillä, joilla on samat merkit, on yhteinen reuna
Tapaus 4: Vertices, joilla on sama merkki, eivät jaa reunaa

Neljännessä tapauksessa on mahdotonta määrittää yksiselitteisesti isoline-segmentin muotoa, joten neliön keskellä olevaa arvoa tarkastellaan lisäksi (jos syöttötiedot sallivat sen). Jos neliön keskellä olevaa arvoa ei saada selville, tehty päätös voi vaikuttaa isolinan liitettävyyteen.

Tapaus 1 : Kaikki kärjet ovat tasapinnan yläpuolella (tai alapuolella).
Tapaus 2 : Yhtä lukuun ottamatta kaikki kärjet ovat tasapinnan yläpuolella (tai alapuolella).
Tapaus 3 : Kaksi kärkeä samassa reunassa ovat tasapinnan yläpuolella (tai alapuolella).
Tapaus 4 : Kaksi kärkeä, joilla ei ole yhteistä reunaa, ovat tasapinnan yläpuolella (tai alapuolella).
Tapauksen 4 ratkaisu positiivisella arvolla solussa.
Tapauksen 4 ratkaisu negatiivisella arvolla solussa.

Lineaarista interpolaatiota käytetään parantamaan tuloksena olevan isolinan laatua . Tässä tapauksessa neliön reunassa olevan isolinjasegmentin pää jakaa reunan suhteessa kohtaan , missä ovat neliön reunan päissä olevat arvot, on isolinan arvo. Itse asiassa isoline-segmentin pää "vedetään" reunan päähän, joka on lähempänä todellista isoliinia. ${\frac {f_{1}-c}{c-f_{2}}}$ $f_{1},f_{2}$ $c$

Linkit

Toteutus Javassa
Marssineliön Matlab-algoritmi – Helposti ymmärrettävä avoimen lähdekoodin marssineliö-algoritmi.
Isoline Isoband - Algoritmien kuvaukset ja avoimen lähdekoodin C / Fortran -koodi AVS- tieteelliseen visualisointijärjestelmään (Mike French, 1992).