Updated to include LineToPoly collisions.
Code archives/Algorithms/Concave/convex polygon collisions and other useful functions.
This code has been declared by its author to be Public Domain code.
Download source code
| Polygon collision functions. TFormPolyToTFormPoly() Checks for collisions between two transformed polygons. PolyToTFormPoly() Checks for collisions between a standard polygon and a transformed polygon. PolyToPoly() Checks for collision between two standard polygon arrays. CircleToTFormPoly() Checks for collision between a circle and a transformed polygon. CircleToPoly() Checks for collision between a circle and a standard polygon array. LineToTFormPoly() Checks for collision between a line and a transformed polygon. LineToPoly() Checks for collision between a line and a standard polygon array. PointInTFormPoly() Checks if the given point is in a transformed polygon. PointInPoly() Checks if the given point is in a standard polygon array. TFormPoly() Returns a transformed polygon from a standard polygon array. TFormGlobalToLocal() Transforms a point from global/screen coordinates too local/polygon/image coordinates. TFormLocalToGlobal() Transforms a point from local/polygon/image coordinates to global/screen coordinates. LinesCross() Checks if two lines intersect. Adapted from code by Fredborg. LineToCircle() Checks for collision between a line and a circle. Adapted from code by TomToad. DrawPoly() An improved DrawPoly command. For more info see here. |
'Code by Dave 'Oddball' Williamson Strict Function TFormPolyToTFormPoly( p1_xy:Float[], p1_x:Float=0, p1_y:Float=0,.. p1_rot:Float=0, p1_scale_x:Float=1, p1_scale_y:Float=1,.. p1_handle_x:Float=0, p1_handle_y:Float=0,.. p1_origin_x:Float=0, p1_origin_y:Float=0,.. p2_xy:Float[], p2_x:Float=0, p2_y:Float=0,.. p2_rot:Float=0, p2_scale_x:Float=1, p2_scale_y:Float=1,.. p2_handle_x:Float=0, p2_handle_y:Float=0,.. p2_origin_x:Float=0, p2_origin_y:Float=0) If p1_xy.length<6 Or (p1_xy.length&1) Return False If p2_xy.length<6 Or (p2_xy.length&1) Return False Local tform1_xy:Float[]=TFormPoly(p1_xy,p1_x,p1_y,p1_rot,p1_scale_x,p1_scale_y,.. p1_handle_x,p1_handle_y,p1_origin_x,p1_origin_y) Local tform2_xy:Float[]=TFormPoly(p2_xy,p2_x,p2_y,p2_rot,p2_scale_x,p2_scale_y,.. p2_handle_x,p2_handle_y,p2_origin_x,p2_origin_y) If PolyToPoly(tform1_xy,tform2_xy) Return True Else Return False EndIf End Function Function PolyToTFormPoly( p1_xy:Float[], p2_xy:Float[],.. p2_x:Float=0, p2_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) If p1_xy.length<6 Or (p1_xy.length&1) Return False If p2_xy.length<6 Or (p2_xy.length&1) Return False Local tform_xy:Float[]=TFormPoly(p2_xy,p2_x,p2_y,rot,scale_x,scale_y,.. handle_x,handle_y,origin_x,origin_y) If PolyToPoly(p1_xy,tform_xy) Return True Else Return False EndIf End Function Function PolyToPoly( p1_xy:Float[], p2_xy:Float[] ) If p1_xy.length<6 Or (p1_xy.length&1) Return False If p2_xy.length<6 Or (p2_xy.length&1) Return False For Local i:Int=0 Until p1_xy.Length Step 2 If PointInPoly(p1_xy[i],p1_xy[i+1],p2_xy) Then Return True Next For Local i:Int=0 Until p2_xy.Length Step 2 If PointInPoly(p2_xy[i],p2_xy[i+1],p1_xy) Then Return True Next Local l1_x1:Float=p1_xy[p1_xy.Length-2] Local l1_y1:Float=p1_xy[p1_xy.Length-1] For Local i1:Int=0 Until p1_xy.Length Step 2 Local l1_x2=p1_xy[i1] Local l1_y2=p1_xy[i1+1] Local l2_x1:Float=p2_xy[p2_xy.Length-2] Local l2_y1:Float=p2_xy[p2_xy.Length-1] For Local i2:Int=0 Until p2_xy.Length Step 2 Local l2_x2=p2_xy[i2] Local l2_y2=p2_xy[i2+1] If LinesCross(l1_x1,l1_y1,l1_x2,l1_y2,l2_x1,l2_y1,l2_x2,l2_y2) Return True EndIf l2_x1=l2_x2 l2_y1=l2_y2 Next l1_x1=l1_x2 l1_y1=l1_y2 Next Return False End Function Function CircleToTFormPoly( circle_x:Float, circle_y:Float, radius:Float,.. xy:Float[], poly_x:Float=0, poly_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) If xy.length<6 Or (xy.length&1) Return False Local tform_xy:Float[]=TFormPoly(xy,poly_x,poly_y,rot,scale_x,scale_y,.. handle_x,handle_y,origin_x,origin_y) Return CircleToPoly(circle_x,circle_y,radius,tform_xy) End Function Function CircleToPoly( circle_x:Float, circle_y:Float, radius:Float, xy:Float[] ) If xy.length<6 Or (xy.length&1) Return False If PointInPoly(circle_x,circle_y,xy) Then Return True Local x1:Float=xy[xy.Length-2] Local y1:Float=xy[xy.Length-1] For Local i:Int=0 Until Len xy Step 2 Local x2:Float=xy[i] Local y2:Float=xy[i+1] If LineToCircle(x1,y1,x2,y2,circle_x,circle_y,radius) Then Return True x1=x2 y1=y2 Next Return False End Function Function LineToTFormPoly( line_x1:Float, line_y1:Float, line_x2:Float, line_y2:Float,.. xy:Float[], poly_x:Float=0, poly_y:Float=0,.. rot:Float=0, scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) If xy.length<6 Or (xy.length&1) Return False TFormGlobalToLocal(line_x1,line_y1,poly_x,poly_y,rot,scale_x,.. scale_y,handle_x,handle_y,origin_x,origin_y) TFormGlobalToLocal(line_x2,line_y2,poly_x,poly_y,rot,scale_x,.. scale_y,handle_x,handle_y,origin_x,origin_y) Return LineToPoly(line_x1,line_y1,line_x2,line_y2,xy) End Function Function LineToPoly( line_x1:Float, line_y1:Float, line_x2:Float, line_y2:Float, xy:Float[] ) If xy.length<6 Or (xy.length&1) Return False If PointInPoly(line_x1,line_y1,xy) Then Return True Local poly_x1:Float=xy[xy.Length-2] Local poly_y1:Float=xy[xy.Length-1] For Local i:Int=0 Until Len xy Step 2 Local poly_x2:Float=xy[i] Local poly_y2:Float=xy[i+1] If LinesCross(line_x1,line_y1,line_x2,line_y2,.. poly_x1,poly_y1,poly_x2,poly_y2) Then Return True poly_x1=poly_x2 poly_y1=poly_y2 Next Return False End Function Function PointInTFormPoly( point_x:Float, point_y:Float, xy:Float[],.. poly_x:Float=0, poly_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) If xy.length<6 Or (xy.length&1) Return False TFormGlobalToLocal(point_x,point_y,poly_x,poly_y,rot,scale_x,.. scale_y,handle_x,handle_y,origin_x,origin_y) Return PointInPoly(point_x,point_y,xy) End Function Function PointInPoly( point_x:Float, point_y:Float, xy:Float[] ) If xy.length<6 Or (xy.length&1) Return False Local x1:Float=xy[xy.Length-2] Local y1:Float=xy[xy.Length-1] Local cur_quad:Int=GetQuad(point_x,point_y,x1,y1) Local next_quad:Int Local total:Int For Local i=0 Until Len xy Step 2 Local x2:Float=xy[i] Local y2:Float=xy[i+1] next_quad=GetQuad(point_x,point_y,x2,y2) Local diff:Int=next_quad-cur_quad Select diff Case 2,-2 If ( x2 - ( ((y2 - point_y) * (x1 - x2)) / (y1 - y2) ) )<point_x diff=-diff EndIf Case 3 diff=-1 Case -3 diff=1 End Select total:+diff cur_quad=next_quad x1=x2 y1=y2 Next If Abs(total)=4 Then Return True Else Return False End Function Function TFormPoly:Float[]( xy:Float[], tform_x:Float=0, tform_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) If xy.length<6 Or (xy.length&1) Return Null Local tform_xy:Float[]=xy[..] For Local i=0 Until tform_xy.Length Step 2 TFormLocalToGlobal(tform_xy[i],tform_xy[i+1],tform_x,tform_y,rot,.. scale_x,scale_y,handle_x,handle_y,origin_x,origin_y) Next Return tform_xy End Function Function TFormGlobalToLocal( point_x:Float Var, point_y:Float Var,.. tform_x:Float=0, tform_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) point_x:-origin_x point_y:-origin_y point_x:-tform_x point_y:-tform_y Local mag:Float=Sqr(point_x*point_x+point_y*point_y) Local ang:Float=ATan2(point_y,point_x) point_x=Cos(ang-rot)*mag point_y=Sin(ang-rot)*mag point_x:/scale_x point_y:/scale_y point_x:+handle_x point_y:+handle_y End Function Function TFormLocalToGlobal( point_x:Float Var, point_y:Float Var,.. tform_x:Float=0, tform_y:Float=0, rot:Float=0,.. scale_x:Float=1, scale_y:Float=1,.. handle_x:Float=0, handle_y:Float=0,.. origin_x:Float=0, origin_y:Float=0 ) point_x:-handle_x point_y:-handle_y point_x:*scale_x point_y:*scale_y Local mag:Float=Sqr(point_x*point_x+point_y*point_y) Local ang:Float=ATan2(point_y,point_x) point_x=Cos(ang+rot)*mag point_y=Sin(ang+rot)*mag point_x:+tform_x point_y:+tform_y point_x:+origin_x point_y:+origin_y End Function 'Adapted from Fredborg's code Function LinesCross( x0:Float, y0:Float , x1:Float, y1:Float,.. x2:Float ,y2:Float, x3:Float, y3:Float ) Local n:Float=(y0-y2)*(x3-x2)-(x0-x2)*(y3-y2) Local d:Float=(x1-x0)*(y3-y2)-(y1-y0)*(x3-x2) If Abs(d) < 0.0001 ' Lines are parallel! Return False Else ' Lines might cross! Local Sn:Float=(y0-y2)*(x1-x0)-(x0-x2)*(y1-y0) Local AB:Float=n/d If AB>0.0 And AB<1.0 Local CD:Float=Sn/d If CD>0.0 And CD<1.0 ' Intersection Point Local X=x0+AB*(x1-x0) Local Y=y0+AB*(y1-y0) Return True End If End If ' Lines didn't cross, because the intersection was beyond the end points of the lines EndIf ' Lines do Not cross! Return False End Function 'Adapted from TomToad's code Function LineToCircle( x1:Float, y1:Float, x2:Float, y2:Float, px:Float, py:Float, r:Float ) Local sx:Float = x2-x1 Local sy:Float = y2-y1 Local q:Float = ((px-x1) * (x2-x1) + (py - y1) * (y2-y1)) / (sx*sx + sy*sy) If q < 0.0 Then q = 0.0 If q > 1.0 Then q = 1.0 Local cx:Float=(1-q)*x1+q*x2 Local cy:Float=(1-q)*y1 + q*y2 If PointToPointDist(px,py,cx,cy) < r Return True Else Return False EndIf End Function Function PointToPointDist:Float( x1:Float, y1:Float, x2:Float, y2:Float ) Local dx:Float = x1-x2 Local dy:Float = y1-y2 Return Sqr(dx*dx + dy*dy) End Function Function GetQuad(axis_x:Float,axis_y:Float,vert_x:Float,vert_y:Float) If vert_x<axis_x If vert_y<axis_y Return 1 Else Return 4 EndIf Else If vert_y<axis_y Return 2 Else Return 3 EndIf EndIf End Function ?win SetGraphicsDriver GLMax2DDriver() ? Graphics 800,600,32,60 HideMouse Local verts:Float[]=[-25.0,0.0,-75.0,75.0,0.0,50.0,100.0,100.0,.. 50.0,25.0,100.0,0.0,50.0,-25.0,100.0,-100.0,0.0,-50.0,-75.0,-75.0] Local cursor:Float[]=[0.0,-50.0,100.0,-100.0,50.0,0.0,100.0,100.0,.. 0.0,50.0,-100.0,100.0,-50.0,0.0,-100.0,-100.0] Local ang:Float=0 Local coltype:Int=0 Local rad:Float=20 Repeat If KeyHit(KEY_1) Then coltype=0 If KeyHit(KEY_2) Then coltype=1 If KeyHit(KEY_3) Then coltype=3 If KeyHit(KEY_4) Then coltype=2 Local x:Float=400 Local y:Float=300 Local rot:Float=ang/2 Local sx:Float=Cos(ang)/2+1.5 Local sy:Float=Sin(ang)/2+1.5 Local hx:Float=Cos(ang)*50 Local hy:Float=Sin(ang)*50 Local ox:Float=Cos(ang/2)*50 Local oy:Float=Sin(ang/2)*50 Local lx:Float=400+Cos(-ang)*300 Local ly:Float=300+Sin(-ang)*300 SetRotation rot SetScale sx,sy SetHandle hx,hy SetOrigin ox,oy Local mx:Int=MouseX() Local my:Int=MouseY() Cls Select coltype Case 0 If PointInTFormPoly(mx,my,verts,x,y,rot,sx,sy,hx,hy,ox,oy) SetColor 0,255,255 Else SetColor 0,128,128 EndIf Case 1 If CircleToTFormPoly(mx,my,rad,verts,x,y,rot,sx,sy,hx,hy,ox,oy) SetColor 0,255,255 Else SetColor 0,128,128 EndIf Case 2 If TFormPolyToTFormPoly(verts,x,y,rot,sx,sy,hx,hy,ox,oy,cursor,mx,my,-rot,0.5,0.5) SetColor 0,255,255 Else SetColor 0,128,128 EndIf Case 3 If LineToTFormPoly(mx,my,lx,ly,verts,x,y,rot,sx,sy,hx,hy,ox,oy) SetColor 0,255,255 Else SetColor 0,128,128 EndIf End Select DrawPoly verts,True,x,y SetRotation 0 SetScale 1,1 SetHandle 0,0 SetOrigin 0,0 SetColor 255,255,255 DrawText "Select 1, 2, 3 or 4",5,0 DrawText "1: PointToTFormPoly",5,20 DrawText "2: CircleToTFormPoly",5,35 DrawText "3: LineToTFormPoly",5,50 DrawText "4: TFormPolyToTFormPoly",5,65 SetColor 255,0,0 Select coltype Case 0 DrawLine mx,my-10,mx,my+10,True DrawLine mx-10,my,mx+10,my,True Case 1 DrawOval mx-rad,my-rad,rad*2,rad*2 Case 2 SetRotation -rot SetScale 0.5,0.5 DrawPoly cursor,True,mx,my Case 3 DrawLine mx,my,lx,ly,True End Select Flip ang:+1 Until KeyHit(KEY_ESCAPE) Function DrawPoly( xy:Float[], fill:Int=True, x:Float=0, y:Float=0 ) Local origin_x:Float Local origin_y:Float GetOrigin origin_x,origin_y Local handle_x:Float Local handle_y:Float GetHandle handle_x,handle_y If fill _max2dDriver.DrawPoly xy,.. -handle_x,-handle_y,.. x+origin_x,y+origin_y Else Local x1:Float=xy[xy.Length-2] Local y1:Float=xy[xy.Length-1] For Local i:Int=0 Until Len xy Step 2 Local x2:Float=xy[i] Local y2:Float=xy[i+1] _max2dDriver.DrawLine.. -handle_x+x1,-handle_y+y1,.. -handle_x+x2,-handle_y+y2,.. x+origin_x-0.5,y+origin_y-0.5 x1=x2 y1=y2 Next EndIf End Function |
Comments
Fixed rounding bug in LineToCircle.
This looks most interesting - never knew it was here - I didn't spot the post 4 months ago.
This is very cool - thanks!
Great Work! You'll be properly credited when I use it.
Thanks for the comments guys.
sorry wrong post
Corrected an error in DrawPoly function. Doesn't effect any of the other functions, but the example code should work correctly now.
Thanks for making this available. Is there any chance of a basic example using these functions? Would love to see it in action. (Prolly too much to ask?) ;)
Check the source, there is already a sample included.
This is radical, thanks!
Some nice looking stuff here I may be able to make good use of, thanks.
One thing I noticed in the LineToCircle function - you can replace this line:
with this:
to elimante the call to PointToPointDist and thus also elimate the use of Sqr.
One thing I noticed in the LineToCircle function - you can replace this line:
If PointToPointDist(px,py,cx,cy) < r
with this:
dx:Float = px - cx dy:Float = py - cy If (dx * dx + dy * dy) < (r * r)
to elimante the call to PointToPointDist and thus also elimate the use of Sqr.