petit probleme de geographie

Le
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

<dominique@vanhee.fr> - <http://www.vanhee.fr/>
"Les utopies sont réalisables. La vie marche vers les utopies"
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Olivier Miakinen
Le #19182421
Bonjour,

Le 24/04/2009 16:01, dvanhee a écrit :

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 - 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.

;-)
Pascal PONCET
Le #19182391
dvanhee a écrit :
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
dvanhee
Le #19182791
On 24 avr, 17:12, Olivier Miakinen
Bonjour,

Le 24/04/2009 16:01, dvanhee a écrit :

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.

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.

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.

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 - 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
------------------------------------------------------------------------
"Les utopies sont réalisables. La vie marche vers les utopies"
Denis Beauregard
Le #19183271
Le 24 Apr 2009 15:55:29 GMT, dvanhee fr.comp.lang.php:

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
Le #19188541
On 24 avr, 19:06, Denis Beauregard <denis.b-at-
wrote:
Le 24 Apr 2009 15:55:29 GMT, dvanhee fr.comp.lang.php:

>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
------------------------------------------------------------------------
"Les utopies sont réalisables. La vie marche vers les utopies"
Denis Beauregard
Le #19191321
Le 25 Apr 2009 13:37:10 GMT, dvanhee fr.comp.lang.php:

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



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
Le #19203321
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-
wrote:
Le 25 Apr 2009 13:37:10 GMT, dvanhee fr.comp.lang.php:

>On 24 avr, 19:06, Denis Beauregard <denis.b-at-
> wrote:
>> 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


bmayesky
Le #19430271
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.
Publicité
Poster une réponse
Anonyme