Piețe de marș

Marching Squares (din engleză - „moving squares”) este un algoritm de grafică pe computer care generează izolinii pe un câmp scalar bidimensional .

Aplicație

Algoritmul este folosit pentru a vizualiza izobarele pe hărțile meteo și liniile de contur pe hărțile geografice. Este o simplificare a algoritmului cuburilor de marș pentru cazul plat.

Cum funcționează

Ca intrare, algoritmul primește o grilă obișnuită, la fiecare nod al căruia este cunoscută valoarea câmpului. Grila de ieșire (indicată cu albastru în figură) poate avea o rezoluție mai mică (în acest caz, precizia este pierdută, dar aliasing-ul este redus). În continuare, pentru fiecare nod al grilei de ieșire, se verifică dacă valoarea din acesta este mai mare decât pe izosuprafața. Toate nodurile care sunt mai sus li se atribuie „+”, restul - „-”. În continuare, luăm în considerare pătratele grilei de ieșire, ale căror vârfuri se află la nodurile marcate. În total, există 16 cazuri diferite, care, ținând cont de simetrii și rotații, pot fi reduse la patru:

Cazul 1: toate vârfurile au același semn
Cazul 2: un vârf are un semn diferit
Cazul 3: vârfurile cu aceleași semne au o muchie comună
Cazul 4: vârfurile cu același semn nu au o muchie comună

În al patrulea caz, este imposibil să se determine fără ambiguitate forma segmentului izolinii, astfel încât valoarea din centrul pătratului este vizualizată suplimentar (dacă datele de intrare permit acest lucru). Dacă este imposibil să aflați valoarea din centrul pătratului, decizia luată poate afecta conectivitatea izolinei.

Cazul 1 : Toate nodurile sunt deasupra (sau dedesubt) izosuprafaței.
Cazul 2 : Cu excepția unuia, toate vârfurile sunt deasupra (sau sub) izosuprafaței.
Cazul 3 : Două vârfuri de pe aceeași muchie sunt deasupra (sau dedesubt) suprafeței izolate.
Cazul 4 : Două vârfuri care nu împărtășesc o muchie sunt deasupra (sau dedesubtul) suprafeței izolate.
Rezolvarea cazului 4 cu o valoare pozitivă în celulă.
Rezolvarea cazului 4 cu o valoare negativă în celulă.

Interpolarea liniară este utilizată pentru a îmbunătăți calitatea izolinei rezultate . În acest caz, capătul segmentului de izolinie de pe marginea pătratului împarte marginea în raport cu , unde sunt valorile de la capetele marginii pătratului, este valoarea izolinei. De fapt, capătul segmentului de izolinie este „tras” până la capătul marginii, care este mai aproape de izolina reală. ${\frac {f_{1}-c}{c-f_{2}}}$ $f_{1},f_{2}$ $c$

Link -uri

Implementare în Java
Algoritmul Marching Square Matlab — Un algoritm open source ușor de înțeles.
Isoline Isoband - Descrieri de algoritm și cod C / Fortran open source pentru sistemul de vizualizare științifică AVS (Mike French, 1992).