Je crois que comtois avait posté un code similaire mais je ne l'ai pas retrouvé.
ça vous permet de savoir si un point est dans un polygone ou non (quelques soit le nombre de point)
2 méthodes différentes pour tester sont implémentées
The Crossing Number ou The Winding Number, vous pouvez switcher d'un mode a un autre avec [TAB]
Il y a aussi 2 formes en mémoire [F1] et [F2]
et pour finir vous pouvez rajouter un point avec un CLIC Gauche , et effacer tout les points avec un CLIC Droit !
Bon, par contre si vous avez une idée pour améliorer tout ça n’hésitez pas ...
Code : Tout sélectionner
NewList V.point()
; Source : http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm#wn_PinPolygon%28%29
;===================================================================
;- isLeft
;isLeft(): tests If a point is Left|On|Right of an infinite line.
; Input: three points P0, P1, And P2
; Return: >0 For P2 left of the line through P0 And P1
; =0 For P2 on the line
; <0 For P2 right of the line
; See: the January 2001 Algorithm "Area of 2D and 3D Triangles and Polygons"
;inline int
Procedure isLeft(*p0.point,*p1.point,*p2.point)
ProcedureReturn ( (*p1\x - *P0\x) * (*p2\y - *P0\y) - (*P2\x - *P0\x) * (*p1\y - *P0\y) );
EndProcedure
;===================================================================
;- The Winding Number
; wn_PnPoly(): winding number test For a point in a polygon
; Input: P = a point,
; V[] = vertex points of a polygon V[n+1] With V[n]=V[0]
; Return: wn = the winding number (=0 only If P is outside V[])
;===================================================================
Procedure wn_PnPoly( *P.point,List polylist.point())
Define wn.l = 0 ;the winding number counter
Define pa.point, pb.point
;loop through all edges of the polygon
For i=0 To ListSize(polylist())-1
SelectElement(polylist(),i)
pa\x=polylist()\x
pa\y=polylist()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(polylist())-1
SelectElement(polylist(),0)
Else
SelectElement(polylist(),i+1)
EndIf
pb\x=polylist()\x
pb\y=polylist()\y
If (pa\y <= *P\y) ; start y <= *P\y
If (pb\y > *P\y) ; an upward crossing
If (isLeft( pa, pb, *P) > 0) ; P left of edge
wn+1 ; have a valid up intersect
EndIf
EndIf
Else ; start y > *P\y (no test needed)
If (pb\y <= *P\y) ; a downward crossing
If (isLeft( pa, pb, *P) < 0) ; P right of edge
wn-1 ; have a valid down intersect
EndIf
EndIf
EndIf
Next
ProcedureReturn Wn
EndProcedure
;===================================================================
;- The Crossing Number
; cn_PnPoly(): crossing number test For a point in a polygon
; Input: P = a point,
; V[] = vertex points of a polygon V[n+1] With V[n]=V[0]
; Return: 0 = outside, 1 = inside
; This code is patterned after [Franklin, 2000]
;===================================================================
Procedure cn_PnPoly( *P.point,List polylist.point())
cn.l = 0 ;the crossing number counter
Define pa.point, pb.point
; loop through all edges of the polygon
For i=0 To ListSize(polylist())-1 ; edge from V[i] To V[i+1]
SelectElement(polylist(),i)
pa\x=polylist()\x
pa\y=polylist()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(polylist())-1
SelectElement(polylist(),0)
Else
SelectElement(polylist(),i+1)
EndIf
pb\x=polylist()\x
pb\y=polylist()\y
If (((pa\y <= *P\y) And (pb\y > *P\y)) Or ((pa\y > *P\y) And (pb\y <= *P\y))) ; an upward crossing Or // a downward crossing
; compute the actual edge-ray intersect x-coordinate
vt.f = (*P\y - pa\y) / (pb\y - pa\y);
If (*P\x < pa\x + vt * (pb\x - pa\x)) ; *P\x < intersect
cn+1; ; a valid crossing of y=*P\y right of *P\x
EndIf
EndIf
Next
ProcedureReturn (cn&1); // 0 if even (out), and 1 if odd (in)
EndProcedure
;===================================================================
;- TEST
;===================================================================
If InitSprite()
If InitKeyboard() And InitMouse()
winMain = OpenWindow(#PB_Any,0,0,800,600,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
OpenWindowedScreen(WindowID(winMain), 0, 0,800,600, 1, 0, 0)
UsePNGImageDecoder()
UseJPEGImageDecoder()
SetFrameRate(60)
EndIf
Else
MessageRequester("","Unable to initsprite") :
EndIf
Define pa.point, pb.point ; pa et pb pour tracer un segment du polygone
Define col.l=RGB(0,0,0) ;
Define EventID.l,mode.b,result.l
Repeat
Delay(1)
EventID = WindowEvent()
ExamineKeyboard()
ExamineMouse()
ClearScreen(col)
;pour switcher du mode The Crossing Number
If KeyboardPushed(#PB_Key_Tab)
mode=1-mode
Delay(200)
EndIf
If MouseButton(#PB_MouseButton_Left)
AddElement(V())
v()\x=MouseX()
v()\y=MouseY()
Delay(200)
EndIf
If MouseButton(#PB_MouseButton_Right)
ClearList(v())
Delay(200)
EndIf
If KeyboardPushed(#PB_Key_F1)
ClearList(V())
For z=0 To 18:angle=(360/19)*z:AddElement(V()):V()\x=400+200*Cos(Radian(angle)):V()\y=300+200*Sin(Radian(angle)):Next
AddElement(V()):V()\x=400:V()\y=300
EndIf
If KeyboardPushed(#PB_Key_F2)
ClearList(V())
AddElement(V()):V()\x=300:V()\y=250:n+1
AddElement(V()):V()\x=350:V()\y=250:n+1
AddElement(V()):V()\x=80:V()\y=10:n+1
AddElement(V()):V()\x=450:V()\y=250:n+1
AddElement(V()):V()\x=400:V()\y=300:n+1
AddElement(V()):V()\x=450:V()\y=280:n+1
AddElement(V()):V()\x=280:V()\y=400:n+1
AddElement(V()):V()\x=340:V()\y=280:n+1
EndIf
StartDrawing(ScreenOutput())
For i=0 To ListSize(V())-1
SelectElement(V(),i)
pa\x=V()\x
pa\y=V()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(V())-1
SelectElement(V(),0)
Else
SelectElement(V(),i+1)
EndIf
pb\x=V()\x
pb\y=V()\y
LineXY(pa\x,pa\y,pb\x,pb\y,#Green)
Circle(pa\x,pa\y,5,#Red)
Next
Circle(MouseX(),MouseY(),5,#Blue)
P.point
P\x=MouseX()
P\y=MouseY()
Select Mode
Case 0
modetxt.s="mode : The Crossing Number"
result=cn_PnPoly(P,V())
Case 1
modetxt.s="mode : The Winding Number"
result=wn_PnPoly(P,V())
EndSelect
If result<>0
modetxt.s+" return : "+Str(result)+" Vous êtes dans le polygone !"
col=RGB(0,0,0)
Else
modetxt.s+" return : "+Str(result)+" Vous n'êtes pas dans le polygone !"
col=RGB(50,50,50)
EndIf
DrawText(0,0,"[Tab] switch Crossing/Winding [F1][F2] polygone [Left mouse button] Add Point [Right mouse button] clear All Point")
DrawText((800-TextWidth(modetxt))/2,20,modetxt.s)
StopDrawing()
FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow
(clic gauche de la souris) le curseur est dessiné part un point bleu ! dit moi si ça marche.
(
)
