Discussion :

[Yann_69]

Bonjour,

j'ai une liste de points dont je connais les coordonnées en abscisse et en ordonnée.

Mon but est d'arriver à savoir quels points sont d'un côté d'une série de segments et lesquels sont de l'autre (j'ai mis une pièce jointe pour être plus explicite).

Si on a un seul segment, ça parait simple :
avec les points des extrémités du segment on retrouve l'équation de la droite et on applique cette équation aux coordonnées du point qu'on veut tester.

Mais pour comparer à une série de segment ça à l'air beaucoup plus compliqué et je ne vois pas comment faire.

Avez-vous une idée ?

Bonne journée.
Merci.

[Invité]

Salut,

la ligne rouge est une fonction affine par morceaux et bijective sur son ensemble de définition. C'est donc possible à partir de l'équation cartésienne de chacun des segments (puis par différence avec les ordonnées des points).

Steph

[Yann_69]

Merci pour ta réponse.

La pièce jointe était un exemple.
Je pense que la série de segment pourrait aussi bien être de ce style :

[Invité]

> Je pense que la série de segment pourrait aussi bien être de ce style

Je me doutais bien

Quelques pistes :

http://www.developpez.net/forums/d81...olygone-ferme/

http://www.developpez.net/forums/d33...ieur-polygone/

http://www.developpez.net/forums/d88...ieur-polygone/

Steph

[Yann_69]

Merci pour la réponse et pour les liens.

Cependant dans ces 3 liens il s'agit de polygones et non d'une suite de segments.

N'y a-t-il pas un moyen simplement avec les segments ?

[Invité]

Cependant dans ces 3 liens il s'agit de polygones et non d'une suite de segments.

N'y a-t-il pas un moyen simplement avec les segments ?

Ca me semble pas compliqué de construire deux polygones fermés avec ta distribution de points M(x,y), non ?

Les points (Min(x)-1, Min(y)-1), (Min(x)-1, Max(y)+1), (Max(x)+1, Max(y)+1), (Max(x)+1, Min(y)-1) définissent un carré qui contient toute ta distribution de points. Ta fonction affine par morceaux va partager ce carré en 2 polygones...

Steph

[Yann_69]

Oui, tu as raison. Je n'avais pas suffisamment réfléchi.

J'ai un algorithme qui marche pour voir si le point est dans le polygone ou non donc tout devrait fonctionner.

Merci beaucoup pour ton aide.

[co2gaz]

Hello, je ne sais pas si c'est fait, mais pourquoi ne pas créer une fonction qui vérifie l’intersection d'un segment donné avec avec ton séparateur (bool isIntersect(l)). tu parcours tes points en les reliant par un segment, si le segment s'intersecte avec ton séparateur tu vire la deuxième extrémité de ton ensemble (donc le point est de l'autre ensemble) et tu continu jusqu'à ce qu'il n'y a plus de points.
Je pense que cette approche est meilleur en complexité