Klaus
Nombre de messages : 12301
Age : 75
Localisation : Ile de France
Date d'inscription : 29/12/2009
 | | Sujet: Tester si un point est dans un polygone Dim 21 Déc 2014 - 14:05 | |
| Question:Sur un plan en deux dimensions, comment vérifier si un point quelconque se trouve à l'intérieur ou à l'extérieur d'un polygone irrégulier ? Réponse: Il faut construire une droite verticale passant par le point à tester et dénombrer les segments du polygone coupés par cette droite. On compte séparément les intersections au-dessus et en-dessous du point à tester. Ces nombres, quels qu'ils soient, sont soit pairs soit impairs. Si ces nombres sont impairs, le point à tester est dans le polygone, et en-dehors sinon. J'ai fait un petit programme qui visualise cela. Un Scene2d prend presque toute la surface de l'écran. Il y a les boutons suivants: "Ajouter un point" : passe le programme en mode "ajout". Tout clic dans la scene2d ajoute ensuite un point à la liste, en dessinant le polygone au fur et à mesure, en couleur noire. La liste des coordonnées s'affiche dans le mémo en haut à droite. "Enlever un point": passe le programme en mode "suppression". Tout clic sur un point déjà dessiné l'enlève du dessin en redessinant le polygone résultant. "Effacer tout": fait ce que le libellé indique. "Point à tester": un point bleu est placé à l'endroit du prochain clic dans la scene2d. En cliquant ailleurs, le point bleu se déplace. Les coordonnées du point sont affichées en-dessous de ce bouton. "Vérifier": affiche le résultat de la vérification pour la position du point bleu par rapport au polygone. Il n'est pas utile de fermer le polygone - le programme le fait automatiquement avec un trait rouge, évitant ainsi la difficulté de viser un pixel précis pour fermer le polygone. Voici le code, le tout en Panoramic pur en 200 lignes: - Code:
-
' test_point_dans_polygone.bas
label add, del, test, eff, padd, pdel, ptest, verif
dim ptest%(1), polygon%(100,1), npoints%, x%, y%, s$, i%, j%
dim x1%,x2%, y1%, y2%, yp, nhaut%, nbas%, ferme%
full_space 0 : caption 0,"Verifier si un point est dans un polygone"
picture 1 : full_space 1 : height 1,height(1) - 100 : top 1,100
button 2 : top 2,10 : left 2,10 : caption 2,"Ajouter un point"
width 2,100 : on_click 2,add
button 3 : top 3,40 : left 3,10 : caption 3,"Enlever un point"
width 3,100 : on_click 3,del
button 31 : top 31,70 : left 31,10 : caption 31,"Effacer tout"
width 31,100 : on_click 31,eff
memo 12 : top 12,10 : left 12,300 : width 12,width(0)-360 : bar_both 12
height 12,80
button 4 : top 4,10 : left 4,150 : caption 4,"Point à tester"
width 4,100 : on_click 4,test
alpha 14 : top 14,40 : left 14,150
button 5 : top 5,70 : left 5,150 : caption 5,"Vérifier"
width 5,100 : on_click 5,verif
2d_target_is 1
end
add:
off_click 1
on_click 1,padd
return
del:
off_click 1
on_click 1,pdel
return
test:
off_click 1
on_click 1,ptest
return
eff:
npoints% = 0
ptest%(0) = -1
ptest%(1) = -1
2d_clear
clear 12
caption 14,""
off_click 1
return
padd:
if npoints%=100
message "Trops de points !"
return
end_if
if ferme%=1
2d_pen_color 255,255,255
2d_poly_from polygon%(npoints%,0),polygon%(npoints%,1)
2d_poly_to polygon%(1,0),polygon%(1,1)
2d_pen_color 0,0,0
ferme% = 0
end_if
x% = mouse_x_left_down(1)
y% = mouse_y_left_down(1)
s$ = "("+str$(x%)+","+str$(y%)+")"
if count(12)>0
s$ = item_read$(12,1)+","+s$
clear 12
end_if
item_add 12,s$
npoints% = npoints% + 1
polygon%(npoints%,0) = x%
polygon%(npoints%,1) = y%
if npoints%=1
2d_point x%,y%
else
2d_poly_from polygon%(npoints%-1,0),polygon%(npoints%-1,1)
2d_poly_to x%,y%
end_if
2d_circle x%,y%,3
return
pdel:
if npoints%=0 then return
x% = mouse_x_left_down(1)
y% = mouse_y_left_down(1)
for i%=1 to npoints%
if abs(polygon%(i%,0)-x%)<5
if abs(polygon%(i%,1)-y%)<5
if i%<npoints%
for j%=i% to npoints%
polygon%(j%,0) = polygon%(j%+1,0)
polygon%(j%,1) = polygon%(j%+1,1)
next j%
end_if
npoints% = npoints% - 1
2d_clear
if npoints%>0
2d_circle polygon%(1,0),polygon%(1,1),3
if npoints%>1
for j%=1 to npoints%-1
2d_poly_from polygon%(j%,0),polygon%(j%,1)
2d_poly_to polygon%(j%+1,0),polygon%(j%+1,1)
2d_circle polygon%(j%+1,0),polygon%(j%+1,1),3
next j%
end_if
end_if
if ptest%(0)>=0
2d_fill_color 0,0,255
2d_fill_on
2d_circle ptest%(0),ptest%(1),3
2d_fill_off
2d_fill_color 255,255,255
end_if
end_if
end_if
next i%
return
ptest:
x% = mouse_x_left_down(1)
y% = mouse_y_left_down(1)
s$ = "("+str$(x%)+","+str$(y%)+")"
caption 14,s$
if ptest%(0)>=0
2d_pen_color 255,255,255
2d_fill_on
2d_circle ptest%(0),ptest%(1),3
2d_fill_off
2d_pen_color 0,0,0
end_if
ptest%(0) = x%
ptest%(1) = y%
2d_fill_color 0,0,255
2d_fill_on
2d_circle x%,y%,3
2d_fill_off
2d_fill_color 255,255,255
return
verif:
' le point est "dedans" si une ligne horizontale ou verticale
' passant par le point coupe un nombre impair de segments du polygone.
' formule du segment: yp=((y2-y1)/(x2-x1))*(xp-x1)+y1
' formule de la droite par le point à tester: x = xp
' il faut tester si min(y1,y2)<=yp<=max(y1,y2)
' si oui, la droite verticale par le point coupe le segment
if ptest%(0)<0 then return
if npoints%<3 then return
nhaut% = 0
nbas% = 0
x% = ptest%(0)
y% = ptest%(1)
2d_pen_color 255,0,0
2d_poly_from polygon%(npoints%,0),polygon%(npoints%,1)
2d_poly_to polygon%(1,0),polygon%(1,1)
2d_pen_color 0,0,0
ferme% = 1
for i%=1 to npoints%
x1% = polygon%(i%,0)
y1% = polygon%(i%,1)
if i%<npoints%
x2% = polygon%(i%+1,0)
y2% = polygon%(i%+1,1)
else
x1% = polygon%(1,0)
y1% = polygon%(1,1)
end_if
if min(x1%,x2%)<=x%
if x%<=max(x1%,x2%)
yp = ((y2%-y1%)/(x2%-x1%))*(x%-x1%)+y1%
if min(y1%,y2%)<=yp
if yp<=max(y1%,y2%)
' message "segment "+str$(i%)+" est coupé."
if yp>=y%
nhaut% = nhaut%+1
else
nbas% = nbas% + 1
end_if
end_if
end_if
end_if
end_if
next i%
' message "haut: "+str$(nhaut%)+" bas: "+str$(nbas%)
if odd(nhaut%)=1
message "Le point à tester est à l'intérieur du polygone !"
else
message "Le point à tester est à l'extérieur du polygone !"
end_if
return
| |
|
Calendrier
