Petit problème de géographie.
dvanhee
Je voudrais vous soumettre un problème pour lequel je n'ai même pas
le
début du commencemnt d'une solution.
Je sais cela part mal mais bon. Je vous présente la chose.
J'ai un ensemble de points de coordonnées (x,y) sérié et qui définit
une surface.
J'ai par ailleurs un point de coordonnées aléatoire.
Existe-t-il un méthode simple permettant de définir si le point P
appartient à la surface ?
Le nombre de points définissant la surface peut varier de 100 à 300.
La forme de la surface peut être :
xxx
x x
x xx
xx x
xx x
x x
x x
x P x
x x
x x
x x
x x
xx x
xx x
xxxx
xxxxxxxxxx
xxx x
x x
xx x
x x
x x
xxxxxxxx x
x x
P x x
x x
xxxxx x
xx x
x x
x x
x x
xx xx
xxxxx
Si une personne a une idée géniale, merci d'avance.
Sinon vers quelle direction dois-je me tourner.
Une première piste consiste à définir une demi-droite partant du point
et
de compter le nombre d'intersection avec le contour. Si le résultat
est impair le point est à l'intérieur, sinon il est à l'extérieur.
Mais à moins d'être passer à coté, cela sous entend de connaître
la fonction qui définit le contour. Or je ne dispose que d'une série
de
coordonnées.
D. Vanhée
------------------------------------------------------------------------
<domini...@vanhee.fr> - <http://www.vanhee.fr/>
"Les utopies sont réalisables. La vie marche vers les utopies"
Patrick 'Zener' Brunet
"dvanhee" <d.va...@free.fr> a écrit dans le message
de news db0f2cfc-047c-4be6...@q2g2000vbr.googlegroups.com
> Bonjour,
>
> Je voudrais vous soumettre un problème pour lequel je n'ai même pas
> le début du commencemnt d'une solution.
> Je sais cela part mal mais bon. Je vous présente la chose.
> J'ai un ensemble de points de coordonnées (x,y) sérié et qui définit
> une surface.
> J'ai par ailleurs un point de coordonnées aléatoire.
> Existe-t-il un méthode simple permettant de définir si le point P
> appartient à la surface ?
> Le nombre de points définissant la surface peut varier de 100 à 300.
> [...]
> Si une personne a une idée géniale, merci d'avance.
>
J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie
constructive...
De mémoire: on parcours les points du contour (polygone) en considérant pour
chaque nouveau point:
- le triangle qu'il forme avec les deux précédents,
- le changement de direction pour le nouveau segment: gauche ou droite,
- ce qui permet d'affecter le triangle d'un + ou d'un -,
- qui peuvent être inversés à la fin du parcours, selon le sens de rotation
global: le + sera vers le centre de gravité.
En procédant ainsi, la surface complète doit a priori (c'est ce que je
n'avais pas fini de vérifier) être la réunion des triangles + amputée de la
réunion des triangles -.
Et donc le diagnostic pour le point P se fait par comparaison avec la liste
des triangles. L'appartenance à un triangle est plus facile à déterminer.
> "Les utopies sont réalisables. La vie marche vers les utopies"
Pas toutes, il y a des critères. Une étude technique s'impose :-)
http://www.espacestemps.net/document6813.html
--
Cordialement.
* Patrick BRUNET www.ipzb.fr www.ipzb-pro.com
* E-mail: lien sur http://zener131.eu/ContactMe
Michel Olagnon
> Bonjour,
>
> Je voudrais vous soumettre un problème pour lequel je n'ai même pas
> le
> début du commencemnt d'une solution.
> Je sais cela part mal mais bon. Je vous présente la chose.
> J'ai un ensemble de points de coordonnées (x,y) sérié et qui définit
> une surface.
> J'ai par ailleurs un point de coordonnées aléatoire.
> Existe-t-il un méthode simple permettant de définir si le point P
> appartient à la surface ?
> Le nombre de points définissant la surface peut varier de 100 à 300.
> La forme de la surface peut être :
>
>
> Sinon vers quelle direction dois-je me tourner.
>
> Une première piste consiste à définir une demi-droite partant du point
> et
> de compter le nombre d'intersection avec le contour. Si le résultat
> est impair le point est à l'intérieur, sinon il est à l'extérieur.
> Mais à moins d'être passer à coté, cela sous entend de connaître
> la fonction qui définit le contour. Or je ne dispose que d'une série
> de
> coordonnées.
>
Ben il suffit de prendre les segments un a un et de regarder (par exemple)
s'ils intersectent le demi-axe horizontal [P, +infini]. La condition est
assez simple pour un segment, si je ne me trompe :
max(y1,y2) > yp > min (y1, y2) et x1 + (x2-x1)(yp-y1)/(y2-y1) > xp
Le probleme est juste de traiter avec soin les cas d'egalite (par exemple
si le demi-axe passe par un des points du polygone, ou si on a un segment
porte par le demi-axe).
Pascal J. Bourguignon
> Bonjour.
>
> "dvanhee" <d.va...@free.fr> a �crit dans le message
> de news db0f2cfc-047c-4be6...@q2g2000vbr.googlegroups.com
>> Bonjour,
>>
>> Je voudrais vous soumettre un probl�me pour lequel je n'ai m�me pas
>> le d�but du commencemnt d'une solution.
>> Je sais cela part mal mais bon. Je vous pr�sente la chose.
>> J'ai un ensemble de points de coordonn�es (x,y) s�ri� et qui d�finit
>> une surface.
>> J'ai par ailleurs un point de coordonn�es al�atoire.
>> Existe-t-il un m�thode simple permettant de d�finir si le point P
>> appartient � la surface ?
>> Le nombre de points d�finissant la surface peut varier de 100 � 300.
>> [...]
>> Si une personne a une id�e g�niale, merci d'avance.
>>
>
> J'avais �bauch� un truc de ce genre il y a longtemps, � base de g�om�trie
> constructive...
>
> De m�moire: on parcours les points du contour (polygone) en consid�rant pour
> chaque nouveau point:
> - le triangle qu'il forme avec les deux pr�c�dents,
> - le changement de direction pour le nouveau segment: gauche ou droite,
> - ce qui permet d'affecter le triangle d'un + ou d'un -,
> - qui peuvent �tre invers�s � la fin du parcours, selon le sens de rotation
> global: le + sera vers le centre de gravit�.
>
> En proc�dant ainsi, la surface compl�te doit a priori (c'est ce que je
> n'avais pas fini de v�rifier) �tre la r�union des triangles + amput�e de la
> r�union des triangles -.
>
> Et donc le diagnostic pour le point P se fait par comparaison avec la liste
> des triangles. L'appartenance � un triangle est plus facile � d�terminer.
D'un autre c�t�, si on a un point O � l'int�rieur du polygone, on peut
aussi d�terminer si un point quelconque P est dans le polygone ou non
en tra�ant le segment OP et en comptant les intersections avec les
c�t�s du polygone. P est � l'int�rieur <=> le nombre d'intersections
est pair.
"Crossing Count Algorithm"
http://www.linuxjournal.com/article/2029
--
__Pascal Bourguignon__
Patrick 'Zener' Brunet
"Pascal J. Bourguignon" <p...@informatimago.com> a �crit dans le message
de news 7cljpmc...@pbourguignon.anevia.com
> "Patrick 'Zener' Brunet" <use.link.i...@ddress.invalid>
> writes:
>> "dvanhee" <d.va...@free.fr> a �crit dans le message
>> de news
>> db0f2cfc-047c-4be6...@q2g2000vbr.googlegroups.com
Je connaissais ce principe, que j'avais d�couvert (il y a longtemps) en
faisant de la programmation graphique avec le GDI de Windows.
Mais l� en fait j'avais un second but: je m'int�ressait globalement � la
g�om�trie constructive � base de r�gions, au-del� des polygones. Donc il
aurait pu y avoir aussi des (arcs d') ellipses ou autres B�ziers dans le
coup.
Dans un tel contexte, seule la g�om�trie constructive permet de g�rer le
probl�me avec des primitives de base.
Par contre, par rapport � ce que je disais, je me suis aper�u que la
diff�rence brute ne suffit pas � trancher, en cas de recouvrements
complexes. Une somme alg�brique est n�cessaire.
Bertrand Lenoir-Welter
> D'un autre c�t�, si on a un point O � l'int�rieur du polygone, on peut
> aussi d�terminer si un point quelconque P est dans le polygone ou non
> en tra�ant le segment OP et en comptant les intersections avec les
> c�t�s du polygone. P est � l'int�rieur <=> le nombre d'intersections
> est pair.
Je fais �a en pla�ant O � l'ext�rieur du polygone (m�me coordonn�e X que
P et coordonn�e Y en-dessous du point le plus bas du polygone). Mais
attention � tenir compte du cas particulier d'une intersection de OP
avec l'un des points du contour. Si celui-ci fait une ar�te avec
rebroussement, ne pas incr�menter le nombre d'intersections.
P /
| /
| /
*
| \
| \
|
+0
P /
| /
| /
*
/|
/ |
|
+1
Olivier Miakinen
>
> [...]
> attention ￜ tenir compte du cas particulier d'une intersection de OP
> avec l'un des points du contour. Si celui-ci fait une arï¿œte avec
> rebroussement, ne pas incrï¿œmenter le nombre d'intersections.
>
> P /
> | /
> | /
> *
> | \
> | \
> |
> +0
>
>
> P /
> | /
> | /
> *
> /|
> / |
> |
> +1
Le problï¿œme est le mï¿œme quand une arï¿œte du polygone est portï¿œe par la
droite.
P /
| /
|/
*
|
|
*
|\
| \
|
+0
P /
| /
|/
*
|
|
*
/|
/ |
|
+1
zwim
Patrick 'Zener' Brunet a �crit
>Bonjour.
>
>"dvanhee" <d.va...@free.fr> a �crit dans le message
> de news db0f2cfc-047c-4be6...@q2g2000vbr.googlegroups.com
>> Bonjour,
>>
>> Je voudrais vous soumettre un probl�me pour lequel je n'ai m�me pas
>> le d�but du commencemnt d'une solution.
>> Je sais cela part mal mais bon. Je vous pr�sente la chose.
>> J'ai un ensemble de points de coordonn�es (x,y) s�ri� et qui d�finit
>> J'ai par ailleurs un point de coordonn�es al�atoire.
>> appartient � la surface ?
>> Le nombre de points d�finissant la surface peut varier de 100 � 300.
>> [...]
>> Si une personne a une id�e g�niale, merci d'avance.
Si tu as le contour de ta surface, et m�me avec des trous dedans, il y
a des algos connus pour �a.
A defaut tu peux faire l'enveloppe convexe ou une triangulation de
Delaunay de ton ensemble de points afin d'obtenir un contour.
L'algo de base est celui-ci :
int pointInPoly(Point2D M,Polygon *P)
{
int i,j,c;
double xi,xj,yi,yj;
c=0;
for(i=0,j=P->num_vertice-1; i<P->num_vertice; j=i,i++)
{
xi = P->vertex[i].x;
yi = P->vertex[i].y;
xj = P->vertex[j].x;
yj = P->vertex[j].y;
if (( ( (yi<=M.y) && (M.y<yj) ) || ( (yj<=M.y) &&
(M.y<yi) ))
&& (M.x<(xj-xi)*(M.y-yi)/(yj-yi)+xi) ) c=!c;
}
return c;
}
Il y a d'autres impl�mentations plus �labor�es l� ->
--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...