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.