Résolu Retrouver tous les points à l'intérieur d'un polygone quelconque

[jacktara]

Salut tout le monde,

Alors aujourd'hui petit challenge.
J'aimerais me faire une fonction qui prends un point en paramètre, sous la forme X,Y, et qui me renvois si ce point est à l'intérieur ou sur la bordure de cette forme à l'intérieur d'un plan.
J'ai beau réfléchir je ne vois pas comment je peux déterminer, dans une forme quelconque, si un point est à l'intérieur ou pas. Pour un carrè ou un cercle pas de soucis, vu que je suis dans un plan et que j'ai les points de chaque angles ce n'est pas compliqué, mais pour le reste alors la je sèche.

Du coup ma question est: est ce qu'une tel formule existe?
Un nom en particulier?

Voilou rien de fou, au passage ne pensez que j'attends le code tout fait, mais ça fait trois jours que je cherche sans succès.
Si ça parle à quelqu'un, merci de m'aiguiller.

Bonne journée.

 

[jacktara]

Ça avance déjà!

Déjà on ne dit pas forme mais polygone quelconque.

Vous devez être connecté pour voir les liens.

Vous devez être connecté pour voir les liens.

Je test ça et je vous dis.

 

[jacktara]

J'ai trouvé que je vais essayer d'implémenter.

Vous devez être connecté pour voir les liens.

 

[magellan]

C'est de toute façon délicat, car la notion de polygone est un vrai souci. Les cas "simples" sont alors à réfléchir.

Schématiquement pour saisir les cas limites.
1° Trace trois droites dans un repère
2° définis les intersections et surtout si tu as une zone fermée
3° Refais l'opération avec plein de configurations de lignes
La détermination va être de savoir ce qu'est le périmètre de ton polygone. L'exemple de l'étoile est parlant, parce que tout dépend ce que tu considères ou pas comme étant une zone.
- Que le centre?
- Que les branches?
- Le tout?
Tiens moi au courant je suis curieux de voir comment cela va fonctionner.

 

[jacktara]

Oui c'est ce que j'ai remarqué, les polygones complexes ce n'est pas si simple.

Vous devez être connecté pour voir les images.

J'ai fait un petit dessin pour imagé mes propos et être sure de ce que je dis aussi. C'est vraiment un cas extrême quand même, mais je peux dessiner les zones à main levées ou en cliquant pour tracer des lignes, d’où la forme bizarre.
Déjà est ce qu'on considère une forme arrondie comme un polygone? Qu'au finale un arc de cercle c'est rien d'autre qu'une succession de droites très rapprochées non?

J'ai aussi pensé que je pouvais faire une fonction qui me renvoie positif si une target traverse une ligne de zone en fait. J'ai tous les points de mes zones, je peux donc trouver si une target est passé sur un de mes points ou sur une des lignes les séparant.
Mais je ne suis pas sure de gérer tous les cas comme ça.

Je vais jeter un oeil à l’exemple de l'étoile.
Je continue mes recherche.
Merci de tes conseils.

 

[magellan]

En fait... en principe ce n'est pas une addition de droites mais bien une courbe dont la formule est identifiée à partir de Pi, son centre et son rayon, et pour ce qui est des liaisons entre objets, le truc est qu'il s'agit certainement d'algos récursifs qui construisent des sous-zones pour identifier les environnements sécants (en tout cas je l'imagine comme ça).

De mémoire: il n'existe pour l'heure aucune formule permettant de "tout" calculer, et cela fait même partie d'un défi rémunéré où l'on dit "soit une zone quelconque fermée. Créez une formule mathématique capable d'en calculer l'aire sans passer par des sous-calculs".
A ce jour personne n'est parvenu à proposer une solution parfaite.

Cependant:
- la question fondamentale est de savoir de quoi tu disposes comme informations. Si tu as toutes les coordonnées des différents points (droites, courbes) et que tu peux déterminer que tu as un réel périmètre, cela rend alors la chose un peu plus simple et ce de la manière suivante:

- chaque point a deux coordonnées X,Y
- Pour que le périmètre soit fermé, il faut que les points qui se suivent finissent par boucler "indéfiniment".
* En gros: si le point de départ est 0,0, il faut que le balayage du tableau de position ramène à chaque fois jusque 0,0
* Il faut que chaque point ait deux points de contacts (avant/après lui).
- Pour que le point soit dans la zone, il faut que celui-ci soit entouré d'au moins quatre points sur les deux axes!
-> Schéma d'explication

Vous devez être connecté pour voir les images.

L'idée est que les coordonnées du point rouge sont X et Y
Les coordonnées des quatre points sont notées ainsi
X1, Y1 en haut
X2, Y2 à gauche
X3, Y3 à droite
X4, Y4 en bas
En gros

Il faut qu'on ait
X = X1
Y = Y2
Y = Y3
X = X4

Si tu as cette situation en vérifiant toutes les coordonnées de points... c'est que tu es dans la zone

 

[jacktara]

Re,

Ok pour le cercle, je voyais vraiment ça comme un ensemble droites.
Merci pour l'info sur le challenge aussi du coup, c'est tentant.

Pour ce qui est des infos dont je dispose; toutes les coordonnées de l'ensemble des points qui définissent une zone.
Je regarde tes explications, j'essaie d'implémenter quelque chose et je te dis ce que ça donne. Juste que cette aprem j'ai eu un peu de mal à être productif. :/ Bref.

Merci pour tes infos, j'essaie d'implémenter une solution et je reviens vers toi.

EDIT: je penses avoir compris ce que tu m'explique. Et ça me parait vraiment logique maintenant. Je me met au taff.

 

[magellan]

En fait c'est relativement simple:
Il faut que quatre points vérifient dans l'ensemble des points de la zone la condition précisée dans mon post précédent. Si tu as ces quatre points, c'est que ton point est dans la zone. Si tu n'as pas les quatre, c'est que tu es hors périmètre. C'est valide pour tout point!

Reprends ton schéma initial, et place quelques points... tu remarqueras que systématiquement tu n'auras pas les quatre points nécessaires à l'inclusion dans la zone.

 

[jacktara]

Oui c'est ce que j'ai remarqué, peu importe la forme si ces quatre conditions ne sont pas réunis le point est forcément hors zone.

Je tatonne une solution là mais ça ne semble pas être encore trop ça.

Dans une boucle qui itère tous les points de la zone.

Si j'ai un point qui possède le même x que ma cible.
Si ce point possède un Y supérieur à target.Y alors point = point Nord
Si ce point possède un Y inférieur à target.Y alors point = point Sud

Et de même pour les Y

Je vérifie en suite que tous mes points ne sont pas null et bien contenus dans la liste des points de la zone.
Pour le moment je n'ai pas encore réussis à faire marcher ça mais je persévère.

 

[magellan]

La boucle est simple en fait
Ajouter à un tableau de test abscisse tous les points ayant l'abscisse en concordance
Ajouter à un tableau de test ordonnées tous les ponts ayant l'ordonnée en concordance

De ces deux tableaux, chercher s'il y a au moins un point au dessus et un en dessous dans les deux directions. Si c'est le cas... alors tu es dedans

 

[jacktara]

Oui c'est ce que j'ai fait.
Je vérifie si j'ai bien les quatre points et si c'est le cas je retourne true.
Merci de ton coup demain en tout cas ça m'a vraiment aidé.
Je continue de taffer dessus, je posterais le code en cpp pour donner une idée à ceux que ça intéressent aussi.

 

[magellan]

J'ai trouvé une combinaison problématique, mais là honnêtement je ne sais pas comment traiter la chose...

Vous devez être connecté pour voir les images.

là je ne sais pas comment tu pourrais t'en dépêtrer.

 

[jacktara]

+1

Je vais plancher la dessus du coup.

PS: C'est fou ce que je peux trouver ça drôle les maths uns fois que je suis partis de l'école.

 

[magellan]

A moins de faire de la récursivité pour réduire en forme minimales chaque sous ensemble de l'aire à analyser, je ne vois pas trop comment contourner le truc.
D'un point de vue fonctionnel la phrase serait "Trouver si un point X.Y appartient à l'aire constituée par l'ensemble des points P(X,Y)"... pas évident!

 

[jacktara]

Oui exactement, c'est ce que je cherchais au début. Je pensais qu'avec Qt j'allais pouvoir analyser l’ensemble des point à l'intérieur d'un polygone à partir d'une liste de points. Je vais voir ce que ça peut donner en récursif voir si je trouve quelque chose comme tu dis en découpant la forme en plusieurs formes. Je vais voir ce que ça donne.