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"
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"
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.
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.
;-)
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
Je ne connaissais pas ce groupe. Je vais y transférer ma requête en
la
complétant de vos remarques.
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.
C'eut été l'Amérique. Mais bon. On va creuser.
Merci pour ta réponse.
D. Vanhée
------------------------------------------------------------------------
"Les utopies sont réalisables. La vie marche vers les utopies"
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
wrote:
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"
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
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:
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.