Discussion :

[dawadam]

Bonjour
Pour utiliser un moteur 2D, j'ai besoin de polygones, sous la forme d'une liste de points x et y.
Hors, j'utilise à la base, une matrice booléenne, un tableau à 2 dimensions.
Je recherche un moyen de convertir ma matrice en une liste de polygones pour pouvoir utiliser le moteur simplement.
J'ai l'impression que c'est un casse-tête et je me demande s'il existe déjà un système similaire à utiliser.
merci

[pseudocode]

Bonjour,

Pour utiliser un moteur 2D, j'ai besoin de polygones, sous la forme d'une liste de points x et y.
Hors, j'utilise à la base, une matrice booléenne, un tableau à 2 dimensions.

Que représente la matrice booléenne 2D ? la présence de pixels ?

[souviron34]

Autre question :

'ai besoin de polygones, sous la forme d'une liste de points x et y.

Pour faire quoi ?

[ToTo13]

Pour faire quoi ?

Pour utiliser un moteur 2D, j'ai besoin de polygones, sous la forme d'une liste de points x et y.
...
convertir ma matrice en une liste de polygones pour pouvoir utiliser le moteur

[dawadam]

Bonjour,
Que représente la matrice booléenne 2D ? la présence de pixels ?

La matrice booléenne est une matrice de collision.
A chaque boolean vrai correspond un block de une unité pas une unité.
C'est une carte en "tuiles".

[pseudocode]

La matrice booléenne est une matrice de collision.
A chaque boolean vrai correspond un block de une unité pas une unité.
C'est une carte en "tuiles".

Et donc, il faut trouver un seul grand polygone qui englobe toutes les cases qui sont "vrai" ?

[dawadam]

Et donc, il faut trouver un seul grand polygone qui englobe toutes les cases qui sont "vrai" ?

Oui, seulement il peut y en avoir plusieurs.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 
0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 1 1 1 1 0

Doit donner une liste de 2 polygones:
Une bar de 4 par 1 en position 1x 0y
Un carré de 2 par 2 en position 2x 2y

[prgasp77]

La méthode dépend de ce qui est attendu. Doit-on par exemple faire des approximations :

. . . . . . . . . . .
. . 1 1 . . . . . . .
. . 1 1 1 1 1 . . . .
. . 1 1 1 1 1 1 1 1 .
. 1 1 1 1 1 1 1 1 . .
. . . . 1 1 1 1 1 . .
. . . . . . . 1 1 . .
. . . . . . . . . . .

Doit-on considérer le polygone comme un (unique) rectangle ? Sinon, il suffit d'opérer en deux phases :

1/ Recherche des contours : on supprime tous les 1 qui ont leurs 4 voisins (N,S,E,O) à 1

. . . . . . . . . . .
. . 1 1 . . . . . . .
. . 1 . 1 1 1 . . . .
. . 1 . . . . 1 1 1 .
. 1 1 1 . . . . 1 . .
. . . . 1 1 1 . 1 . .
. . . . . . . 1 1 . .
. . . . . . . . . . .

2/ On boucle sur le contour :

. . . . . . . . . . .
. . a b . . . . . . .
. . t . c d e . . . .
. . s . . . . f g h .
. r q p . . . . i . .
. . . . o n m . j . .
. . . . . . . l k . .
. . . . . . . . . . .

Exercice laissé au lecteur : gérer les cas des trous et des formes complexes

[dawadam]

La méthode dépend de ce qui est attendu. Doit-on par exemple faire des approximations :

. . . . . . . . . . .
. . 1 1 . . . . . . .
. . 1 1 1 1 1 . . . .
. . 1 1 1 1 1 1 1 1 .
. 1 1 1 1 1 1 1 1 . .
. . . . 1 1 1 1 1 . .
. . . . . . . 1 1 . .
. . . . . . . . . . .

Doit-on considérer le polygone comme un (unique) rectangle ? Sinon, il suffit d'opérer en deux phases :

1/ Recherche des contours : on supprime tous les 1 qui ont leurs 4 voisins (N,S,E,O) à 1

. . . . . . . . . . .
. . 1 1 . . . . . . .
. . 1 . 1 1 1 . . . .
. . 1 . . . . 1 1 1 .
. 1 1 1 . . . . 1 . .
. . . . 1 1 1 . 1 . .
. . . . . . . 1 1 . .
. . . . . . . . . . .

2/ On boucle sur le contour :

. . . . . . . . . . .
. . a b . . . . . . .
. . t . c d e . . . .
. . s . . . . f g h .
. r q p . . . . i . .
. . . . o n m . j . .
. . . . . . . l k . .
. . . . . . . . . . .

Exercice laissé au lecteur : gérer les cas des trous et des formes complexes

ça semble être ce que je recherche.
Il me faut gérer les polygones complexes, par contre, ils ne seront jamais creux.

[souviron34]

...

ce que je voulais dire était :

sous forme de liste de points ( = pixels) ou sous forme de points (= ligne brisée de segments)...

[dawadam]

ce que je voulais dire était :

sous forme de liste de points ( = pixels) ou sous forme de points (= ligne brisée de segments)...

C'est donc bien sous la forme de lignes brisées de segments qu'il me faut.

[souviron34]

OK

Le problème géométrique sous-jacent est très complexe (calcul de l'enveloppe concave d'un ensemble de points)

Cependant, vu que à la base tu as une matrice, la solution donnée par pgrasp77 est la bonne..

Il te suffit, une fois les "polygones" ainsi isolés, de suivre les contours et stocker les points d'nflexion..

[dawadam]

J'aurais tellement voulu trouver une solutions clef en main dans une API ou autre, mais on dirait bien que je vais devoir m'y coller...
Merci