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
| ||
| Updated to include LineToPoly collisions. |
| ||
| 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: 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. |
| ||
| I know this is old, but just wanted to say thanks, this is going to save me a tonne of work! |
| ||
| Great work! Im just realizing the importance of this section in the forum |
Code Archives Forum
   |