Polygon merging or substracting

BlitzMax Forums/BlitzMax Programming/Polygon merging or substracting

Space_guy

(Posted 2011) [#1]

example link:
http://www.cs.man.ac.uk/~toby/alan/software/

Is there any module or tips on how to merge two polygon shapes together.

Thankfull for any tips!

beanage

(Posted 2011) [#2]

This is awefully complicated, and there wont be a trivial way to do this (unless you feel more like a genius than me :).. couldnt you port some parts of the GPC?

Space_guy

(Posted 2011) [#3]

Yes it is hard. Ive been thinking about this many times the last few years but i always gave up on it. Im not experienced in porting code either. :(

But perhaps someone has something?

Oddball

(Posted 2011) [#4]

Here's something to get you started

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 500.0,250.0, 500.0,350.0, 200.0,300.0 ]
Global poly2:Float[]=[ 300.0,300.0, 700.0,250.0, 700.0,350.0, 300.0,400.0 ]

Global merged:Float[]

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=AddPoly(poly1,poly2)

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "Merged Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function AddPoly:Float[]( p1:Float[], p2:Float[] )
	Local m:Float[p1.length+p2.length]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	Local countm:Int=0
	Local count1:Int=start
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			m[countm]=p1[count1]
			m[countm+1]=p1[count1+1]
			
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,p1[count1],p1[count1+1],p1[(count1+2) Mod p1.length],p1[(count1+3) Mod p1.length], p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					countm:+2
					m[countm]=tmpx
					m[countm+1]=tmpy
					count2=(count2+count+2) Mod p2.length
					flag=1
					Exit
				EndIf
			Next
			count1:+2
			If count1>=p1.length Then count1=0
		Else
			m[countm]=p2[count2]
			m[countm+1]=p2[count2+1]
			
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,p2[count2],p2[count2+1],p2[(count2+2) Mod p2.length],p2[(count2+3) Mod p2.length], p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					countm:+2
					m[countm]=tmpx
					m[countm+1]=tmpy
					count1=(count1+count+2) Mod p1.length
					flag=0
					Exit
				EndIf
			Next
			count2:+2
			If count2>=p2.length Then count2=0
		EndIf
		countm:+2
	Until count1=start
	
	Return m[..countm]
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

It's not perfect but it's a start.

Oddball

(Posted 2011) [#5]

How about this one?

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 100.0,250.0, 700.0,250.0, 700.0,350.0, 100.0,350.0 ]'[ 200.0,200.0, 500.0,250.0, 500.0,350.0, 200.0,300.0 ]
Global poly2:Float[]=[ 300.0,100.0, 500.0,100.0, 500.0,500.0, 300.0,500.0 ]'[ 300.0,300.0, 700.0,250.0, 700.0,350.0, 300.0,400.0 ]

Global merged:Float[]

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=AddPoly(poly1,poly2)

SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "Merged Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function AddPoly:Float[]( p1:Float[], p2:Float[] )
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					If (tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])<(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
						mx=tmpx
						my=tmpy
						i=count
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					If (tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])<(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
						mx=tmpx
						my=tmpy
						i=count
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
		
	Until count1=start
	
	Return m[..countm]
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

It's a little better. It can handle multiple line crosses along a single line.

Last edited 2011

Oddball

(Posted 2011) [#6]

Ok, now it has a limited form of polygon subtraction

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 500.0,250.0, 500.0,350.0, 200.0,300.0 ]
Global poly2:Float[]=[ 300.0,300.0, 700.0,250.0, 700.0,350.0, 300.0,400.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If sub
		Local tmp:Float[p2.length]
		For Local count:Int=0 Until p2.length Step 2
			tmp[count]=p2[p2.length-count-2]
			tmp[count+1]=p2[p2.length-count-1]
		Next
		p2=tmp
	EndIf
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					If (tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])<(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
						mx=tmpx
						my=tmpy
						i=count
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			For Local count:Int=0 To p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					If (tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])<(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
						mx=tmpx
						my=tmpy
						i=count
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
		
	Until count1=start
	
	Return m[..countm]
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

Still far from perfect, but not bad for 20 minutes coding. I'm sure you can take it from here and customise it to your needs.

Have fun!

Last edited 2011

Oddball

(Posted 2011) [#7]

I should add that the points in the polygons should run clockwise for this to work correctly.

Warpy

(Posted 2011) [#8]

To detect if the points in a triangle are clockwise:

Function makeClockwise(tri#[])
   Local cp# = (tri[2]-tri[0])*(tri[5]-tri[1]) - (tri[4]-tri[0])*(tri[3]-tri[1])
   If cp > 0
     Local x# = tri[2], y# = tri[3]
     tri[2] = tri[4]
     tri[4] = x
     tri[3] = tri[5]
     tri[5] = y
   EndIf
End Function

I'm sure I had a page bookmarked which explained the algorithm for polygon operations, but I can't find it. This livejournal post seems to give a brief summary of the process.

Oddball

(Posted 2011) [#9]

Do you have a version of that for polygons of any number of points? It would help make the function more robust. Anyway there is a serious bug in my last example so here it is all fixed up

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 500.0,250.0, 400.0,300.0, 500.0,350.0, 200.0,300.0 ]
Global poly2:Float[]=[ 300.0,300.0, 700.0,250.0, 700.0,350.0, 300.0,400.0, 100.0,250.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If sub
		Local tmp:Float[p2.length]
		For Local count:Int=0 Until p2.length Step 2
			tmp[count]=p2[p2.length-count-2]
			tmp[count+1]=p2[p2.length-count-1]
		Next
		p2=tmp
	EndIf
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	If count1>=p1.length Then count1=0
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p1.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
		
	Until count1=start
	
	Return m[..countm]
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

That's the last one I promise. I shouldn't really be messing with this stuff anyway, but it piqued my interest and I couldn't help myself.

Last edited 2011

Space_guy

(Posted 2011) [#10]

:) This is awsome! Thanks alot!
I hope to have a play with this tonight

ImaginaryHuman

(Posted 2011) [#11]

You could do it in realtime using the stencil buffer in opengl.

Warpy

(Posted 2011) [#12]

Oddball: just look at the first three points. Assuming the polygon doesn't self-intersect, if the first three points are clockwise the whole polygon has to be. If the polygon does self-intersect, being clockwise or anticlockwise has no meaning.

Oddball

(Posted 2011) [#13]

D'oh! Good call Warpy. Makes perfect sense, if only I'd taken a moment to think about it.

Warpy

(Posted 2011) [#14]

I was wrong: if you choose a concave bit it won't work.

Oddball

(Posted 2011) [#15]

That's nothing a quick tweak won't fix.

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 100.0,50.0, 300.0,400.0, 700.0,350.0, 700.0,250.0, 300.0,100.0, 300.0,300.0 ]
Global poly2:Float[]=[ 200.0,300.0, 500.0,350.0, 400.0,300.0, 500.0,250.0, 200.0,200.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If Not IsClockwise(p1) Then p1=ReversePoly(p1)
	If (sub And IsClockwise(p2)) Or (Not sub And Not IsClockwise(p2)) Then p2=ReversePoly(p2)
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	If count1>=p1.length Then count1=0
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p1.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
		
	Until count1=start
	
	Return m[..countm]
End Function

Function ReversePoly:Float[]( poly:Float[] )
	Local tmp:Float[poly.length]
	For Local count:Int=0 Until poly.length Step 2
		tmp[count]=poly[poly.length-count-2]
		tmp[count+1]=poly[poly.length-count-1]
	Next
	Return tmp
End Function

'Adapted from Wary's code
Function IsClockwise:Int( poly:Float[] )
	Local vex:Int=PointInPoly( (poly[0]+poly[2]+poly[4])*.333, (poly[1]+poly[3]+poly[5])*.333, poly )
	Local cp:Float = (poly[2]-poly[0])*(poly[5]-poly[1]) - (poly[4]-poly[0])*(poly[3]-poly[1])
	If (cp>0 And vex) Or (cp<=0 And Not vex)
		Return True
	EndIf
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

Now works with polygons running in either direction. Far from perfect, but still pretty good I'd say.

Space_guy

(Posted 2011) [#16]

I did not have the time i hoped for last night but in the time i had i must say it works very good! Thanks alot for sharing this Oddball!

Space_guy

(Posted 2011) [#17]

As Im back into this polygon code i discovered a bug.
Whenever i try add or substract from the final line in the p1 polygon it just ignores it.

Any thougths?

Also im thinking if a polygon gets split in 2 parts by the second poly it would be very cool to be able to get both polygons :) Any ideas where I could start?

And thanks again for this code. Its almost perfect for my needs :)

Warpy

(Posted 2011) [#18]

The algorithm on the livejournal blog I posted before is the only proper algorithm to do this. I wish I could find the much more detailed page I can remember seeing, but I can't find it.

Difference

(Posted 2011) [#19]

This might be what he came up with : https://github.com/revarbat/TkCAD/blob/master/tksrc/lib/geometry.tcl ?

It does seem to be his github: https://github.com/revarbat

Last edited 2011

Space_guy

(Posted 2011) [#20]

If you use these polys you will see what the bug I mentioned.
I tried to find the bug my self but nothing i change seems to fix this.

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 250.0,100.0, 300.0,250.0, 500.0,100.0 ]

And that livejournal is very interesting. I just wish i could this code though as it works good enough for me. Exept that bug ofcourse :)

Oddball

(Posted 2011) [#21]

I'm just making this stuff up as I'm going along so I doubt it's the best way of doing it. It's just the problem piqued my interest and I couldn't rest until I'd given it a go.

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 250.0,100.0, 300.0,250.0, 500.0,100.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If Not IsClockwise(p1) Then p1=ReversePoly(p1)
	If (sub And IsClockwise(p2)) Or (Not sub And Not IsClockwise(p2)) Then p2=ReversePoly(p2)
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	If count1>=p1.length Then count1=0
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p1.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
		
	Until count1=start+2
	
	Return m[..countm]
End Function

Function ReversePoly:Float[]( poly:Float[] )
	Local tmp:Float[poly.length]
	For Local count:Int=0 Until poly.length Step 2
		tmp[count]=poly[poly.length-count-2]
		tmp[count+1]=poly[poly.length-count-1]
	Next
	Return tmp
End Function

'Adapted from Wary's code
Function IsClockwise:Int( poly:Float[] )
	Local vex:Int=PointInPoly( (poly[0]+poly[2]+poly[4])*.333, (poly[1]+poly[3]+poly[5])*.333, poly )
	Local cp:Float = (poly[2]-poly[0])*(poly[5]-poly[1]) - (poly[4]-poly[0])*(poly[3]-poly[1])
	If (cp>0 And vex) Or (cp<=0 And Not vex)
		Return True
	EndIf
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

The last line bug should be fixed now, but I'm sure the function is still far from totally bug free.

Last edited 2011

Space_guy

(Posted 2011) [#22]

Thanks but when i move the polygon to the right of the box then it wont work again :(

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 450.0,240.0, 250.0,300.0, 450.0,380.0 ]

Oddball

(Posted 2011) [#23]

Yep, I kinda messed that fix up. Try this one on for size.

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 450.0,240.0, 250.0,300.0, 450.0,380.0 ] 

'Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
'Global poly2:Float[]=[ 250.0,100.0, 300.0,250.0, 500.0,100.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If Not IsClockwise(p1) Then p1=ReversePoly(p1)
	If (sub And IsClockwise(p2)) Or (Not sub And Not IsClockwise(p2)) Then p2=ReversePoly(p2)
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	If count1>=p1.length Then count1=0
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
				If count1=start+2 Then Exit
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p1.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
	Forever	
	
	Return m[..countm]
End Function

Function ReversePoly:Float[]( poly:Float[] )
	Local tmp:Float[poly.length]
	For Local count:Int=0 Until poly.length Step 2
		tmp[count]=poly[poly.length-count-2]
		tmp[count+1]=poly[poly.length-count-1]
	Next
	Return tmp
End Function

'Adapted from Wary's code
Function IsClockwise:Int( poly:Float[] )
	Local vex:Int=PointInPoly( (poly[0]+poly[2]+poly[4])*.333, (poly[1]+poly[3]+poly[5])*.333, poly )
	Local cp:Float = (poly[2]-poly[0])*(poly[5]-poly[1]) - (poly[4]-poly[0])*(poly[3]-poly[1])
	If (cp>0 And vex) Or (cp<=0 And Not vex)
		Return True
	EndIf
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

Hopefully that should fix the issue without creating ay new ones... I hope.

GW	(Posted 2011) [#24]

Awesome!

Space_guy

(Posted 2011) [#25]

Seems to work perfectly :)

Thank you very much!

Space_guy

(Posted 2011) [#26]

Thanks again for the code! Its really usefull!

However I noticed one more bug that I tried to fix but was not yet able to.
There seems to be a way for it to get stuck in a loop that ends with a crash.

What happens is atleast that countm counter keeps going up and up but it will never exit. This seems to be rare. But too frequent for me to ignore.

GW	(Posted 2011) [#27]

This seems help illustrate the bug.

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 250.0-110,100.0, 300.0-110,250.0, 500.0-110,100.0 ]

Oddball

(Posted 2011) [#28]

Those polys add and subtract flawlessly for me.

SuperStrict

Graphics 800,600

Global poly1:Float[]=[ 200.0,200.0, 200.0,450.0, 400.0,450.0, 400.0,200.0 ]
Global poly2:Float[]=[ 250.0-110,100.0, 300.0-110,250.0, 500.0-110,100.0 ]

Global merged:Float[]

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
Flip

WaitKey()

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1+P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

merged=BoolPoly(poly1,poly2,True)

Cls
SetColor 0,255,0
DrawText "Polygon 1",0,0
DrawPoly poly1,False
SetColor 0,0,255
DrawText "Polygon 2",0,15
DrawPoly poly2,False
SetColor 255,0,0
DrawText "P1-P2 Polygon",0,30
DrawPoly merged,False
Flip

WaitKey()

Function BoolPoly:Float[]( p1:Float[], p2:Float[], sub:Int=False )
	If Not IsClockwise(p1) Then p1=ReversePoly(p1)
	If (sub And IsClockwise(p2)) Or (Not sub And Not IsClockwise(p2)) Then p2=ReversePoly(p2)
	Local m:Float[1024]
	
	Local start:Int=0
	While PointInPoly(p1[start],p1[start+1],p2) And start<p1.length
		start:+2
	Wend
	If start>=p1.length Then Return p2
	
	m[0]=p1[start];m[1]=p1[start+1]
	Local countm:Int=2
	Local count1:Int=start+2
	If count1>=p1.length Then count1=0
	Local count2:Int=0
	Local flag:Int=0
	Repeat
		If flag=0
			
			Local mx:Float=p1[count1]
			Local my:Float=p1[count1+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p2.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p2[(count2+count) Mod p2.length],p2[(count2+count+1) Mod p2.length],p2[(count2+count+2) Mod p2.length],p2[(count2+count+3) Mod p2.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=1
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=0
				count1:+2
				If count1>=p1.length Then count1=0
				If count1=start+2 Then Exit
			Else
				count2=(count2+i+2) Mod p2.length
			EndIf
		Else
			
			Local mx:Float=p2[count2]
			Local my:Float=p2[count2+1]
			Local i:Int
			Local md:Float=(mx-m[countm-2])*(mx-m[countm-2])+(my-m[countm-1])*(my-m[countm-1])
			For Local count:Int=0 Until p1.length Step 2
				Local tmpx:Float
				Local tmpy:Float
				If LinesCross(tmpx,tmpy,m[countm-2],m[countm-1],mx,my, p1[(count1+count) Mod p1.length],p1[(count1+count+1) Mod p1.length],p1[(count1+count+2) Mod p1.length],p1[(count1+count+3) Mod p1.length] )
					Local d:Float=(tmpx-m[countm-2])*(tmpx-m[countm-2])+(tmpy-m[countm-1])*(tmpy-m[countm-1])
					If d>.001 And d<md
						mx=tmpx
						my=tmpy
						i=count
						md=d
						flag=0
					EndIf
				EndIf
			Next
			m[countm]=mx
			m[countm+1]=my
			countm:+2
			If flag=1
				count2:+2
				If count2>=p2.length Then count2=0
			Else
				count1=(count1+i+2) Mod p1.length
			EndIf
		EndIf
	Forever	
	
	Return m[..countm]
End Function

Function ReversePoly:Float[]( poly:Float[] )
	Local tmp:Float[poly.length]
	For Local count:Int=0 Until poly.length Step 2
		tmp[count]=poly[poly.length-count-2]
		tmp[count+1]=poly[poly.length-count-1]
	Next
	Return tmp
End Function

'Adapted from Wary's code
Function IsClockwise:Int( poly:Float[] )
	Local vex:Int=PointInPoly( (poly[0]+poly[2]+poly[4])*.333, (poly[1]+poly[3]+poly[5])*.333, poly )
	Local cp:Float = (poly[2]-poly[0])*(poly[5]-poly[1]) - (poly[4]-poly[0])*(poly[3]-poly[1])
	If (cp>0 And vex) Or (cp<=0 And Not vex)
		Return True
	EndIf
End Function

'Adapted from Fredborg's code
Function LinesCross:Int( rx:Float Var, ry:Float Var, 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
				rx=x0+AB*(x1-x0)
		       	ry=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

Function PointInPoly:Int( 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:Int=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 GetQuad:Int(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

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

Last edited 2011