triangulating 2d-polygons

hi,
i try to make a simple polygonbased paintprogram.
the problem i have is the DrawPoly function.
it only works with convex polys.
so i need to triangulate the 2d-polygon.

has anyone a simple explanation to solve the problem?
the explanations i can find on the internet are bit to theoretical.

i think a lot of people have my problems with DrawPoly.

You're going to have to divide it up into triangles or slice it horizontally/vertically into convex pieces. It's not a simple task.

You can trace around the edge of your polygon definition point-by-point and if you find that the exterior angle between any two sides is <180 degrees then that's where you need to do a split of some kind.

I needed to do this a while ago. I assume you've looked at the wikipedia page about this - http://en.wikipedia.org/wiki/Polygon_triangulation - look at the "subtracting ears method"
If you're still having trouble, I can write up a simple example.

oh thats funny.
i´ve searched so many websites about that and thought that trapezoid decomposition is THE way to make triangles. but for me it was to complicate to program. so i thougt about a method that was very close to "subtracting ears method".
now i have to implement "subtracting ears method" in blitzmax. i hope i can make it. not so easy for a beginner...
first i have to figure out how to check if the new drawn line is in the polygon.

thanks for the help so far.

Funny. I was looking at the exact same problem also. I’m having some problems understanding the ear-finding algorithm, and I was wandering if someone could explain it a little or post a sample. Cheers,
VinceA

Here you go:

'TRIANGULATING A POLYGON BY SUBTRACTING EARS!

'Triangulation is the problem of how to cut up a polygon into triangles, so that all the triangles together make up the whole polygon.

'This method works by noticing that a polygon with no holes in it always has two ears.
'An 'ear' is a triangle consisting of two edges from the boundary of the polygon, and a third line on the inside of the polygon
'joining them up, but not crossing the boundary on the way.

'If you clip an ear off the polygon, you are left with a smaller polygon (or, more importantly, a polygon with fewer vertices)
'which you can perform the subtracting ears operation on again. You repeat the process until you are left with a 3-sided polygon,
'which of course is already triangulated!

'The set of all the ears you've clipped off forms a triangulation of the polygon.



Function triangulate:TList(points:TList) 
'this function takes a list of the vertices of a polygon (in order) as input, and returns a list of triangles.

	points = points.Copy()   'this algorithm works by removing points from the list, so we make a copy of it and leave the original intact
	
	c = points.count()  'we keep track of how many points are in our working polygon so that we know when to stop!
	If c < 3 Return New TList 'error-checking: fewer than 3 points doesn't make a polygon
	
	l:TList = New TList 'this list will store all our triangles
	While c>3	
		Local array:point[]
		array = point[] (points.toarray())  'make an array from the list of points, for easier referencing
	
		
		i = 0
		go = 0
		While Not go
			p1:point=array[i]
			p2:point=array[(i+1) Mod c]
			p3:point = array[(i + 2) Mod c] 
			
			'p1,p2,p3 are consecutive points on the boundary of the polygon.
			'consider the triangle p1->p2->p3
			
			midx:Float = (p1.x + p2.x + p3.x) / 3.0	'(midx,midy) is a point inside the candidate triangle
			midy:Float = (p1.y + p2.y + p3.y) / 3.0
			
			'here we check if (midx,midy) is inside the polygon. An 'S'-bend in the polygon can cause the candidate triangle
			'to actually be on the outside of the polygon, making it useless in a triangulation.
			'This check works by counting the number of times a horizontal ray originating from (midx,midy) crosses the boundary of the polygon
			'if hits is odd, then (midx,midy) is inside the polygon.
			hits=0
			For ii = 0 To c - 1
				x1#=array[ii].x
				y1#=array[ii].y
				x2#=array[(ii+1) Mod c].x
				y2#=array[(ii+1) Mod c].y
				If (y1-midy)*(y2-midy)<0
					ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
					If ix<midx hits:+1
				EndIf
			Next

			If (hits Mod 2) 'tri is inside polygon
			
				'We now know the triangle is inside the polygon, so the last thing we need to check is that the line p3->p1
				'doesn't cross the boundary at any point.
				
				x1#=p1.x
				y1#=p1.y
				x2#=p3.x
				y2#=p3.y
				dx1#=x2-x1
				dy1#=y2-y1
				
				go=1
				n=(i+3) Mod c
				While n<>i
					x3#=array[n].x
					y3#=array[n].y
					dx2#=x3-x2
					dy2#=y3-y2
					
					If dx1<>dx2 Or x1<>x2 Or dy1<>dy2 Or y1<>y2
						lambda#=(y2-y1+dy2*(x1-x2)/dx2)/(dy1-dx1*dy2/dx2)
						mu#=(x1-x2+lambda*dx1)/dx2
						If lambda>0 And lambda<1
							If mu>=0 And mu<=1
								go=0
							EndIf
						EndIf
					EndIf
					x2=x3
					y2=y3
					n=(n+1) Mod c
				Wend
			EndIf
			
			If Not go 'if go=0, then our line crossed the boundary at some point, so this triangle isn't an ear.
				i=(i+1) Mod c
				If i=0 Return Null
			EndIf
		Wend

		'by the time we get out of that while loop, we know that the triangle p1->p2->p3 is an ear, so can be clipped
		t:tri = tri.Create(p1, p2, p3) 
		
		'this is just some drawing code so you can see the algorithm working
		draweverything(points, l) 
		SetColor 255, 0, 0
		t.draw() 
		SetColor 255, 255, 255
				
		Flip
		Cls
		Delay 500

		
		'remove p2 from the list of points - this is the same as removing the whole ear from the polygon - now there is no way 
		'p1->p2->p3 will be considered again.
		points.remove p2
		
		l.addlast t	'add the triangle to our list of ears
		c:-1	'we've removed a point

	Wend
	
	'we're left with a single triangle, but it's not in our list of ears yet, so we need to add it
	array=point[](points.toarray())
	t:tri=tri.Create(array[0],array[1],array[2])
	l.addlast t
	
	'done! return the list of triangles
	Return l
	
End Function


Function draweverything(points:TList, triangles:TList) 
	For t:tri = EachIn triangles
		t.draw() 
	Next
	
	op:point = Null
	For p:point = EachIn points
		p.draw() 
		If op
			DrawLine op.x, op.y, p.x, p.y
		End If
		op = p
	Next
	If op
		p = point(points.First()) 
		DrawLine op.x, op.y, p.x, p.y
	EndIf
End Function

Type tri
	Field p1:point,p2:point,p3:point
	
	Function Create:tri(p1:point,p2:point,p3:point)
		t:tri=New tri
		t.p1=p1
		t.p2=p2
		t.p3=p3
		Return t
	End Function
	
	Method draw()
		Local poly:Float[] 
		SetAlpha.5
		poly =[p1.x, p1.y, p2.x, p2.y, p3.x, p3.y] 
		DrawPoly poly
		SetAlpha 1
		DrawLine p1.x, p1.y, p2.x, p2.y
		DrawLine p2.x, p2.y, p3.x, p3.y
		DrawLine p3.x, p3.y, p1.x, p1.y
	End Method
End Type

Type point
	Field x#,y#
	
	Function Create:point(x:Float, y:Float) 
		p:point=New point
		p.x=x
		p.y=y
		Return p
	End Function
	
	Method draw()
		DrawRect x-1,y-1,3,3
	End Method
End Type


'Demo - left click to place points, then right click when you have 3 or more to run the triangulation algorithm.

Graphics 600, 600, 0
SetBlend ALPHABLEND
points:TList = New TList
triangles:TList = New TList
While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) 

	If MouseHit(1) 
		points.AddLast point.Create(MouseX(), MouseY()) 
	End If
	
	If MouseHit(2) And points.Count() >= 3
		triangles = triangulate(points) 
	End If
	
	draweverything(points, triangles) 
		
	Flip
	Cls
WEnd

Thanks so much, i'm impressed. Great demo and comments!
Really nice..

Thank you very much for your help!
Very impressive.
I hope someday i can help people on this forum too.

Warpy
at the moment i try to understand your code.
i have some difficulties with

				If (y1-midy)*(y2-midy)<0
					ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
					If ix<midx hits:+1
				EndIf

i understand the line
If (y1-midy)*(y2-midy)<0
if the horizontal ray originating from (midx,midy) hits the edge Points of the line that is checked hits will be zero. so "mid" is outside the polygon. i´ve made a little sketch of 3 cases i can imagine that are difficult.



case 1 hits will be zero -> point ist outside the polygon
case 2 hits will be zero -> point ist outside the polygon
case 3 seems to make trouble. hits will be 1 but it is outside the polygon.

the horizontal ray will hit two edge points both will make hits zero an then a normal line that will make hits to one. the result will be 1 and so it is inside the polygon.

another difficulty i have is to understand

ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
If ix<midx hits:+1

i don´t get it. what are you calculating here?


the result of your code seems to have a bug. it seems that the last point i set is causing trouble



i really try to understand your code.

thanks for your great effort so far!!!

We're scanning horizontally across the screen, from (0,midy) to (midx,midy), and counting how many times it intersects the boundary of the polygon.

For each line, we have two endpoints, (x1,y1) and (x2,y2).

If (y1-midy)*(y2-midy)<0
	ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
	If ix<midx hits:+1
EndIf

The first line of code checks if y1 and y2 are on opposite sides of the line. (y1 - midy) will be positive or negative depending on if y1 is higher or lower than midy. The product (y1 - midy)*(y2 - midy) will be positive if y1 and y2 are both higher or both lower than midy, or negative if they're on opposite sides.
So once we know these points are on opposite sides of the line y=midy, we know that this line intersects our scan line, and we need to find out the x-coordinate of the point of intersection.

Now, if this x-coordinate is to the left of midx, then our scan line has to cross this line before it gets to (midx,midy), so we add a "hit" to our tally. Every time we cross a line, we switch from being inside the polygon to outside it, and vice versa. So, if we have an odd number of hits by the time we get to (midx,midy), then that point must be inside the polygon.


Looking at your trouble cases, yes, we need to deal with those. We can deal with case 2 by rejecting lines where y1=y2.
Looking at cases 1 and 3, the difference between them seems to be that in case 1, the two lines touching the scanline are both above it, whereas in case 3 one is below. It stands to reason that when ever you have a vertex of the polygon lying exactly on the scanline, there are exactly two lines coming out of it, so if we only count the ones pointing down, we can deal with case 3.

Here's a modified version of the code above, taking all this into account:

If y1<>y2             'deal with case 2
	side#=(y1-midy)*(y2-midy)
	If side<0
		ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
		If ix<midx hits:+1
	ElseIf side=0               'deal with cases 1 and 3
		If y1>midy hits:+1
		If y2>midy hits:+1
	EndIf
EndIf

I'm sure it'll be a known method, but while bored at work a few years ago, I came up with another way of doing this, though I'm struggling to implement it in code as a general function. (Help me, Warpy-Wan.) It goes "something" like this...

· Have a defined set of outer points and, optionally, separate sets of inner points (for holes in the polygon), specified in your chosen order;
· Go through each outer point one-by-one, rendering a test line to every other point (inner and outer);
· If any test line passes through an existing line, discard it, otherwise, draw it (or add to a triangle list);
· After checking all outer points, check all inner points against all outer points*.

This seems to work in the cases I've tried (including the images above). For example (showing the first step):



Copy this into Paint and try it with the line tool, from Step 2 onwards (remember not to cross any lines you've drawn, outer lines included). Step 2 will connect only to the 4th red dot, clockwise, for example, while the 3rd won't connect to any more, so you move along, etc.

* Only tested with one 'hole' so not sure whether each inner point should check other inner points... ?

Actually, I think you'd have to define each inner point in a specific order (eg. clockwise), defined as part of a separate hole, so you can tell whether you're hitting a point without crossing the hole.

It'd avoid having to scan pixel-by-pixel...

How about using a polygon rasterizing technique and somehow chop polygons horizontally?

BlitzSupport
i think your method should work but would be very slow.
the benefit of clipping ears is tht the polygon will be less complex each time you found a triangle.
your method will be much complexer each time you have found a triangle.
in step 2 you have to deal with all outer lines and your new drawn lines.

Yeah, you're probably right. Still, I'm quite proud of myself for working it out! I'll have to try and code it one day just to see...

I agree with Tempus - while your algorithm can work, James, it's not very efficient.

Yeah, I guess so. Still, it'd cover holes in polys (I think!), and I imagine most triangulation scenarios wouldn't need to be real time anyway (?). Not to worry, I'm still glad I worked it out!

speaking of faster algorithm i wonder if my version is faster

If midy > y1
  If midy < y2
   If x1 > midx And x2 > midx 
    hits:+1
   Else 
    ix# = x1+(midy-y1)*(x2-x1)/(y2-y1)
    If ix# <= midx hits:+1
   EndIf
  EndIf
EndIf

If midy > y2
  If mpy < y1
   If x1 > midx And x2 > midx 
    hits:+1
   Else 
    ix# = x1+(midy-y1)*(x2-x1)/(y2-y1)
    If ix# <= midx hits:+1
   EndIf
  EndIf
EndIf

If midy = y1
  If mpy < y2 hits:+1
EndIf

If midy = y2
  If mpy < y1 hits:+1
EndIf

i don´t know if this is faster than

If y1<>y2             'deal with case 2
	side#=(y1-midy)*(y2-midy)
	If side<0
		ix#=x1+(x2-x1)*(midy-y1)/(y2-y1)
		If ix<midx hits:+1
	ElseIf side=0               'deal with cases 1 and 3
		If y1>midy hits:+1
		If y2>midy hits:+1
	EndIf
EndIf

my version is much longer and not so elegant but it has more cases where the computer only has to compare some variables instead of computing almost everytime (y1-midy)*(y2-midy)

another thing is that the code is based of a coordinate system with it's y-origin at the bottom of the screen. it seems to work but doesn´t the y-coordinates begin at the top of the screen?

I can well believe that your version is faster. I never code for speed, the satisfaction for me is just in making it work.

it doesn't really matter which way round the y-axis goes - we only want to know that the lines are pointing in *some* direction, we're free to choose which one that is.