Discussion :

[SKone]

Bonjour,
Je suis à la recherche d'un algo de subdivision de forme convexe et concave. Je ne pense pas qu'il existe c'est pourquoi je demande votre aide puisque j'ai essayé de retourné le problème de tous les sens je n'y arrive pas.
J'ai des îlots un îlots est une liste de point. Une liste circulaire pour pouvoir accéder à chaque segment.
Et le but est de diviser cette îlot suivant une axe Verticale ou Horizontale en fonction de la taille du carré englobant. En gros on coupe suivant un axe perpendiculaire au plus grand des côtés du carré englobant de l'îlot.
Coupé l'îlot ne me pose aucun problème je test l'intersection entre chaque segment et l'axe j'insert le point d'intersection à sa place en lui mettant un flag POINT_CREE.
Voilà où j'en suis et le tout est de récupérer les sous îlots pour leur réappliquer l'algo jusqu'à ce que leur surface soit inférieur à une valeur donnée.
Pour être plus claire voilà une image.

Merci pour votre aide

PS : je dois implémenter ça en C++

[PRomu@ld]

C'est un problème de partitionnement de l'espace, ça ressemble furieusement à un arbre BSP ce que tu veux faire.

[SKone]

Presque puisque je me base pas sur un espace convexe et je ne veux pas en sortie des espaces convexes. Je veux juste reccupérer l'ensemble des listes de points qui sont formé par les boucles bleu dans l'exemple.
Une idée ?

[Furikawari]

Comment est construite la droite qui coupe ? Tu cherches à maximiser le nombre d'îlots construits ? Parce qu'avec juste la coupure sur le coté le plus grand du rectangle, ça laisse quelques possibilités...

[SKone]

J'ai l'îlot qui est une liste de point et je test les segments (2 points consécutifs) si ils sont en intersection avec l'axe et si c'est le cas je place un point avec un flag POINT_CREE. Et j'ai une liste de pointeur "ligne" qui pointe vers les points crées. Quand je coupe verticalement je tri ligne en fonction de ces Z et sinon selon les X.

Et je ne cherche pas vraiment à maximiser le nombre d'îlot. Mais de récupérer les îlots former par la coupe. Comme si l'on coupais l'îlot avec un hache.

Je ne sais pas si j'ai été assez claire ?

[Furikawari]

Donc tu connais la droite ? Tu connais les segments ? C'est juste un problème d'intersection d'une droite d'équation connue avec des segments d'équations connues ? Si oui le problème est trivial (surtout dans le cas de droites parallèles aux axes).

Je pense qu'il faut que tu poses ton problèmes clairement, d'un coté les données, de l'autre ce que tu cherches et à mon avis la solution devrait te sauter aux yeux.

[SKone]

Arf...
Suis-je si peu claire que cela
J'ai les points d'intersection, j'ai la droite et j'ai aussi les segments...
Le tout est de récupérer l'ensemble d'ensemble de point qui forme les sous-îlots issus de la division

[Furikawari]

Je crois que j'ai compris...

Un algorithme de parcours devrait suffire.

Tu pars d'un point de ta liste.

Tu parcours tes segments. A chaque point que tu rencontres, tu l'ajoutes a ta liste pour l'ilot en cours. La question se pose quand tu arrives à une intersection (donc entre un de tes segments et la droite, ou encore, quand tu arrives sur un des POINT_CREE).

Lorsque tu arrives a un de ces points, tu branches en allant sur la droite. Ensuite, au POINT_CREE suivant que tu rencontres, tu repars sur un segment. La direction est simple à trouver étant donné que ta droite est parallèle à un des axes. Lorsque tu as bouclé, tu as construit un ilot et tu peux donc retirer ses points de ta liste globale. Attention, de par leur nature, les POINT_CREE appartiennent à 2 ilots.

[SKone]

J'ai pensé à cette méthode mais le problème c'est que cela fonctionne avec les îlots type C, U ou S.
On prend un point de l'îlot on avance et quand on rencontre un POINT_CREE on regarde la parité du point si il est pair on va au point suivant selon la ligne et sinon on va en avant dans ligne. En stockant la valeur du point en tant que X. Lorsque l'on revient au point de départ. On avance on dit que le le point de départ est X. et on recommence. Jusqu'à avoir tous les îlots. Le nombre d'îlot est de nb_Intersection/2 + 1.

Mais le problème est que cela ne fonctionne pas avec les îlots de type E.


PS : j'espère être assez claire

[Furikawari]

Avec cette méthode je pense que j'obtiens bien les 4 ilots pour l'ilot de type E. Où est ton problème avec le E ? (sur ton deuxième schéma ça ne parait pas mais je considerais les angles comme des points, l'erreur vient peut être de là).

[lcfseth]

J'ai une idée, je sais pas si c'est bien ce que tu veux, c'est pas assez claire.
Je pense que tu utilise une liste chainé circulaire.
Tu dis pouvoir trouver les points d'intersections, je suppose donc que tu les a inséré dans la liste. Dans ce cas pourquoi ne pas utiliser deux autres listes.
Ensuite tu parcours ta liste, si le point est à droite de la droite, tu l'ajoute à la premiere liste, sinon à la deuxieme. Les points d'intersections sont eux ajouté au deux. Normalement tu devrais definir les deux moitié de l'ilot principale.

L'observation des deux types d'ilot montre ces deux régles tres importantes :

* Pour la liste de droite, il faut relier les points d'intersection(2n+1 - 2n).
* Si un point d'intersection (2n+1) est directement relié à un point d'intersection (2n+2) alors chacun appartient à un ilot different.


Donc, il suffit de parcourir chacune des listes à la recherche des points de separation etablit selon la 2eme regle. Un fois chaque ilot definit, on clos les listes de gauche selon la regle n°1.