Marching Squares est un algorithme de l'infographie, qui est utilisé pour récupérer des isocontours 2D à partir d'une grille d'échantillons (voir également son grand frère Marching Cubes pour les paramètres 3D). L'idée est de traiter chaque cellule de la grille indépendamment et de déterminer les contours passant par cette cellule en fonction des valeurs à ses coins.
La première étape de ce processus consiste à déterminer quelles arêtes sont reliées par des contours, selon que les coins sont supérieurs ou inférieurs à la valeur du contour. Par souci de simplicité, nous ne considérerons que les contours le long de la valeur 0, de sorte que nous souhaitons savoir si les coins sont positifs ou négatifs. Il y a des cas à distinguer:24 = 16
Source de l'image: Wikipedia
L'identification du blanc et du noir n'a pas vraiment d'importance ici, mais pour être précis, disons que le blanc est positif et le noir est négatif. Nous ignorerons les cas où l'un des coins est exactement 0.
Les points de selle (cas 5 et 10) offrent un peu de difficulté supplémentaire: il n'est pas clair quelles diagonales doivent être utilisées en ne regardant que les coins. Cela peut être résolu en trouvant la moyenne des quatre coins (c'est-à-dire une approximation de la valeur centrale) et en choisissant les diagonales de telle sorte que les contours séparent le centre des coins avec le signe opposé. Si la moyenne est exactement 0, l'un ou l'autre cas peut être choisi.
Normalement, ces 16 cas sont simplement stockés dans une table de recherche. C'est génial pour l'efficacité, mais bien sûr, nous préférerions que le code soit court ici. Votre tâche consiste donc à effectuer cette étape de recherche et à imprimer une représentation ASCII du cas dans le moins de code possible.
Le défi
On vous donne les valeurs des quatre coins (entiers non nuls) dans un ordre fixe de votre choix. Vous devez ensuite générer la disposition correcte des contours, en résolvant correctement les cas de point de selle.
Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).
L'entrée peut être prise dans n'importe quel format de chaîne ou de liste.
Les 16 cas seront représentés dans l'art ASCII en utilisant l'un des blocs 5x5 suivants:
o---o o---o o---o
| | | | | | |
| | |---| | | |
| | | | | | |
o---o o---o o---o
o---o o---o o---o o---o
|/ | | \| | | | |
| | | | | | | |
| | | | |\ | | /|
o---o o---o o---o o---o
o---o o---o
|/ | | \|
| | | |
| /| |\ |
o---o o---o
Vous ne devez imprimer aucun espace de début ou de fin, mais vous pouvez imprimer une seule nouvelle ligne facultative.
Il s'agit du code golf, donc la réponse la plus courte (en octets) l'emporte.
Cas de test
Les cas de test supposent que l'entrée est donnée dans l'ordre supérieur gauche , supérieur droit , inférieur gauche , inférieur droit . Les cas de test sont présentés en 9 groupes, un correspondant à chacune des 9 représentations données ci-dessus (dans le même ordre, à partir de la cellule vide, en terminant par les deux points de selle).
[1, 2, 1, 3]
[-9, -2, -2, -7]
[4, 5, -1, -2]
[-1, -2, 3, 4]
[7, -7, 7, -7]
[-5, 5, -5, 5]
[1, -6, -4, -1]
[-2, 3, 3, 4]
[-1, 6, -4, -1]
[2, -3, 3, 4]
[-1, -6, 4, -1]
[2, 3, -3, 4]
[-1, -6, -4, 1]
[2, 3, 3, -4]
[3, -8, -9, 2]
[-3, 8, 9, -2]
[8, -3, -2, 9]
[-8, 3, 2, -9]
De plus, les cas de test suivants peuvent renvoyer l'un des points de selle (votre choix):
[1, -4, -2, 5]
[-1, 4, 2, -5]