petit probleme de geographie

[dvanhee]

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 cla 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
xxxxxxxxx x
x x
P x x
x x
xxxxx x
xx x
x x
x x
x x
xx xx
xxxxxxx


Si une personne a une idée géniale, merci d'avance.
Sinon vers quelle direction dois-je me tourner.

D. Vanhée
------------------------------------------------------------------------
<***@vanhee.fr> - <http://www.vanhee.fr/>
"Les utopies sont réalisables. La vie marche vers les utopies"

[Olivier Miakinen]

Bonjour,

Post by 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 cla 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 ?

C'est un problème classique. Si tu ne t'intéresses qu'à l'algo, outre
que c'est hors charte ici et que ça aurait été en charte dans le groupe
fr.comp.algorithmes, j'imagine que la réponse a dû être donnée là-bas un
certain nombre de fois.

En gros, tu considères une demi-droite partant du point (par exemple une
demi-droite horizontale, ce qui simplifie les calculs) et tu comptes
combien de fois cette demi-droite traverse le contour. Si le résultat
est impair le point est à l'intérieur, sinon il est à l'extérieur.
Il y a quelques cas particuliers lorsque la demi-droite se confond en
partie avec l'un des segments du contour, et aussi des difficultés
éventuelles si tu fais les calculs en virgule flottante.

Cela dit, puisque tu demandes ça dans fr.comp.lang.php, c'est je suppose
que tu cherches une fonction déjà programmée dans ce langage. Je suis à
peu près sûr que ça doit exister, mais je ne saurais pas te dire où
chercher.

En désespoir de cause, tu peux toujours utiliser l'astuce suivante, mais
ça doit être déplorable en temps de calcul :
- Créer une image noire avec GD <http://fr2.php.net/gd>
- Dessiner le polygone en blanc avec imagefilledpolygon()
- Récupérer la couleur du point qui t'intéresse avec imagecolorat()
Si le point est blanc, il est dedans ; noir, il est dehors.

;-)

[dvanhee]

Post by Olivier Miakinen
Bonjour,
C'est un problème classique. Si tu ne t'intéresses qu'à l'algo, outre
que c'est hors charte ici et que ça aurait été en charte dans le groupe
fr.comp.algorithmes, j'imagine que la réponse a dû être donnée là-bas un
certain nombre de fois.

Je ne connaissais pas ce groupe. Je vais y transférer ma requête en
la
complétant de vos remarques.

Post by Olivier Miakinen
En gros, tu considères une demi-droite partant du point (par exemple une
demi-droite horizontale, ce qui simplifie les calculs) et tu comptes
combien de fois cette demi-droite traverse le contour. Si le résultat
est impair le point est à l'intérieur, sinon il est à l'extérieur.
Il y a quelques cas particuliers lorsque la demi-droite se confond en
partie avec l'un des segments du contour, et aussi des difficultés
éventuelles si tu fais les calculs en virgule flottante.

C'est bien la piste que l'on m'avait indiqué, mais je butte sur la
fonction qui doit définir
la surface. Je ne connais pas son expression; Je ne dispose qu'une
série de coordonnées.

Post by Olivier Miakinen
Cela dit, puisque tu demandes ça dans fr.comp.lang.php, c'est je suppose
que tu cherches une fonction déjà programmée dans ce langage. Je suis à
peu près sûr que ça doit exister, mais je ne saurais pas te dire où
chercher.

C'eut été l'Amérique. Mais bon. On va creuser.

Post by Olivier Miakinen
En désespoir de cause, tu peux toujours utiliser l'astuce suivante, mais
- Créer une image noire avec GD <http://fr2.php.net/gd>
- Dessiner le polygone en blanc avec imagefilledpolygon()
- Récupérer la couleur du point qui t'intéresse avec imagecolorat()
Si le point est blanc, il est dedans ; noir, il est dehors.

Merci pour ta réponse.

D. Vanhée
------------------------------------------------------------------------
<***@vanhee.fr> - <http://www.vanhee.fr/>
"Les utopies sont réalisables. La vie marche vers les utopies"

[Denis Beauregard]

Post by dvanhee
C'est bien la piste que l'on m'avait indiqué, mais je butte sur la
fonction qui doit définir
la surface. Je ne connais pas son expression; Je ne dispose qu'une
série de coordonnées.

http://ca2.php.net/manual/fr/function.imagefilledpolygon.php

bool imagefilledpolygon ( resource $image , array $points , int
$num_points , int $color )

Avec l'algorythme proposé, cela devrait faire le travail en se
rappelant tout de même que l'image que peut créer PHP est de grandeur
limitée et il faudra éventuellement faire une mise à l'échelle.

Et si c'est l'Amérique, alors on peut supposer que le polygone ne
se recoupe pas lui-même mais ne fait que la frontière.


Denis

[dvanhee]

On 24 avr, 19:06, Denis Beauregard <denis.b-at-

Post by Denis Beauregard

Post by dvanhee
C'est bien la piste que l'on m'avait indiqué, mais je butte sur la
fonction qui doit définir
la surface. Je ne connais pas son expression; Je ne dispose qu'une
série de coordonnées.

http://ca2.php.net/manual/fr/function.imagefilledpolygon.php
bool imagefilledpolygon  ( resource $image  , array $points  , int
$num_points  , int $color  )
Avec l'algorythme proposé, cela devrait faire le travail en se
rappelant tout de même que l'image que peut créer PHP est de grandeur
limitée et il faudra éventuellement faire une mise à l'échelle.
Et si c'est l'Amérique, alors on peut supposer que le polygone ne
se recoupe pas lui-même mais ne fait que la frontière.
Denis

Cela peut le faire.
Un copain va encore me traiter de bourin, mais j'ai l'habitude.
Avec un boucle de furieux, je devrais pouvoir tester les 96 polygones.
Cela entraînera un grosse charge de calcul. A tester.

Merci

D. Vanhée
------------------------------------------------------------------------
<***@vanhee.fr> - <http://www.vanhee.fr/>
"Les utopies sont réalisables. La vie marche vers les utopies"

[Denis Beauregard]

Post by dvanhee
On 24 avr, 19:06, Denis Beauregard <denis.b-at-

Post by Denis Beauregard
Et si c'est l'Amérique, alors on peut supposer que le polygone ne
se recoupe pas lui-même mais ne fait que la frontière.

Cela peut le faire.
Un copain va encore me traiter de bourin, mais j'ai l'habitude.
Avec un boucle de furieux, je devrais pouvoir tester les 96 polygones.
Cela entraînera un grosse charge de calcul. A tester.

Si ce sont toujours les mêmes polygones, il y a un algorithme fort
simple (en partant de la suggestion d'Olivier, soit de faire des
polygones). Il suffirait d'avoir 96 couleurs différentes et de
dessiner tous les polygones sur la même image (ou une série d'images
juxtaposées). En regardant la couleur du point, on identifie le
polygone !

Tout de même, il y a aussi MAP qui est fait pour cela il me semble...


Denis

[Tonio]

Je le ferai dans postgres/postgis (ou tout autre extension spatiale).
Tu crée un polygon, puis avec la within de postgis tu teste
l'appartenance de ton point au polygone.

Ce sera très bon niveau perf.

Tonio

On Apr 25, 10:37 pm, Denis Beauregard <denis.b-at-

Post by Denis Beauregard

Post by dvanhee
On 24 avr, 19:06, Denis Beauregard <denis.b-at-

Post by Denis Beauregard
Et si c'est l'Amérique, alors on peut supposer que le polygone ne
se recoupe pas lui-même mais ne fait que la frontière.

Cela peut le faire.
Un copain va encore me traiter de bourin, mais j'ai l'habitude.
Avec un boucle de furieux, je devrais pouvoir tester les 96 polygones.
Cela entraînera un grosse charge de calcul. A tester.

Si ce sont toujours les mêmes polygones, il y a un algorithme fort
simple (en partant de la suggestion d'Olivier, soit de faire des
polygones).  Il suffirait d'avoir 96 couleurs différentes et de
dessiner tous les polygones sur la même image (ou une série d'images
juxtaposées).  En regardant la couleur du point, on identifie le
polygone !
Tout de même, il y a aussi MAP qui est fait pour cela il me semble...
Denis

[Pascal PONCET]

Post by dvanhee
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 ?

Bonjour,

C'est plutôt un pb de géométrie, et même de mathématiques pures, non ?
A mon avis, on ne peut résoudre ce pb que si la surface a été définie
par une fonction, et si on connait son expression.
Des pistes ? Oui, revoir au moins une saison dvd de Numbers ! ;-)

Cordialement,
Pascal

[b***@gmail.com]

La suggestion de la demi-droite est la bonne. Si tu n'a pas de
fonction (ce serait presque heureux en l'occurence) il suffit de
calculer les intersections avec les segments formés par deux points
points voisins dans ta série et appliquer la règle pair/impair pour
dehors/dedans.