This is a translated java program written by Ian Garton. It triangulates a closed, simple polygon.
Open in online IDE;/*-------------------------------------------------------------------*/ ;/* BruteForceEarCut.java */ ;/* This file contains the class needed for the implementation */ ;/* of ear cutting for a simple polygon. */ ;/* */ ;/*- Modification History---------------------------------------------*/ ;/* When: Who: Comments: */ ;/* */ ;/* 97.12.09 Ian Garton Final Implementation */ ;/*-------------------------------------------------------------------*/ Type Triangle Field v0x# Field v0y# Field v1x# Field v1y# Field v2x# Field v2y# End Type Global npoints Global earCounter Global concaveCount Dim xpoints# (1000), ypoints# (1000) Dim xpointsTemp#(1000), ypointstemp#(1000) Dim ptType (1000) Dim ex#(4), ey#(4) Graphics 800, 600, 0, 3 SetBuffer BackBuffer() Dim xpoints(1000) Dim ypoints(1000) npoints = 0 Repeat Cls ;N If KeyHit(49) Then Delete Each triangle tel = 0 npoints = 0 ok = True done = False End If If MouseHit(1) Then xpoints(npoints) = MouseX() ypoints(npoints) = MouseY() npoints = npoints + 1 xpoints(npoints) = xpoints(0) ypoints(npoints) = ypoints(0) ok = True End If tl = 0 If done Then For ti.triangle = Each triangle filltri ti\v0x, ti\v0y, ti\v1x, ti\v1y, ti\v2x, ti\v2y, 0, 0, 255, 255, 255, 0 Line ti\v2x, ti\v2y, ti\v0x, ti\v0y tl = tl + 1 Next Else tel = npoints mtst = False For i = 0 To tel - 1 Color 0, 255, 0 Oval xpoints(i) - 5, ypoints(i) - 5, 10, 10 Text xpoints(i), ypoints(i) - 15, i, True, True tst = False For j = 0 To tel - 1 If j <> i Then tst = tst Or Kruisen(xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1), xpoints(j), ypoints(j), xpoints(j + 1), ypoints(j + 1)) Next If tst Then Color 255, 0, 0 Else Color 0, 0, 255 mtst = mtst Or tst Line xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1) Next End If If MouseHit(2) And (Not mtst) Then If polygonClockwise() Then For i = 0 To npoints - 1 xpointstemp(i) = xpoints((npoints - 1) - i) ypointstemp(i) = ypoints((npoints - 1) - i) ;pttpye Next For i = 0 To npoints - 1 xpoints(i) = xpointstemp(i) ypoints(i) = ypointstemp(i) Next End If If ok Then npoints = npoints + 1 xpoints(npoints - 1) = xpoints(0) ypoints(npoints - 1) = ypoints(0) ok = False End If on = npoints For i = 0 To on action "cut" Next done = True End If Text 0, 0, "Use LMB to draw 'simple' polygon" Text 0, 20, "Lines that are intersecting are marked Red" Text 0, 40, "If no lines are intersecting, use RMB to triangulate" Text 0, 60, "This code was written by Ian Garton" Flip Until KeyHit(1) End ; /* ; * main: This is to run outside of Netscape, using AppletFrame. ; */ ; public static void main (String args()) ; { ; runsInBrowser = False; ; AppletFrame.startApplet("BruteForceEarCut", ; "Brute Force Ear Cutting", ; args); ; } ; /* finishNotify: When user enters final point, variables are ; * initialized and the Cut Ear button is made ; * active. ; */ Function FinishNotify() earCounter = 0 End Function ; /* action: Performs actions according to button user activates. ; */ Function action(actie$) If actie$ = "clear" Then earCounter = 0 Cls End If If actie$ = "cut" Then If (npoints > 3) Then classifyPoints doCutEar ;repaint End If End If End Function ; /* paint: Displays modified polygon ; */ ;Function repaint() ; ; public void paint(Canvas caller, Graphics g) ; { ; if (transformedPoly == null) return; ; ; for (int i = 0; i < earCounter; i++) { ; g.setColor(Color.yellow); ; g.fillPolygon(earPoly(i)); ; g.setColor(Color.pink); ; g.drawPolygon(earPoly(i)); ; } ; ; if (npoints > 3) { ; g.setColor(Color.black); ; g.drawPolygon(transformedPoly); ; } ; } ; /* polygonClockwise: Returns true if user inputted polygon in ; * clockwise order, false if counterclockwise. ; * The Law of Cosines is used to determine the ; * angle. ; */ Function polygonClockwise2() Local aa#, bb#, cc#, b#, c#, theta# Local convex_turn# Local convex_sum# = 0 For i = 0 To npoints - 2 aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i))) bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i))) cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1))) b = Sqr(bb) c = Sqr(cc) theta = ACos((bb + cc - aa) / (2 * b * c)) If (convex(xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1),xpoints(i+2), ypoints(i+2))) Then convex_turn = Pi - theta convex_sum = convex_sum + convex_turn Else convex_sum = convex_sum - (Pi - theta) End If Next aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2))) bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2))) cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0))); b = Sqr(bb) c = Sqr(cc) theta = ACos((bb + cc - aa) / (2 * b * c)) If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(0), ypoints(0), xpoints(1), ypoints(1))) Then convex_turn = Pi - theta convex_sum = convex_sum + convex_turn Else convex_sum = convex_sum - (Pi - theta) End If If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False End Function ; /* classifyPoints: Classifies points as "convex" or "concave". ; * Convex points are represented as a "1" in the ; * ptType array; concave points are represented as a ; * "-1" in the array. ; */ Function classifyPoints() concaveCount = 0 ; /* Before cutting any ears, we must determine if the polygon was ; * inputted in clockwise order or not, since the algorithm for ; * cutting ears assumes that the polygon's points are in clockwise ; * order. If the points are in counterclockwise order, they are ; * simply reversed in the array. ; */ If (earCounter = 0) Then If (Not polygonClockwise()) Then For i = 0 To npoints - 1 xpointsTemp(i) = xpoints(npoints-1 - i) ypointsTemp(i) = ypoints(npoints-1 - i) Next For i = 0 To npoints - 1 xpointsTemp(i) = xpoints(i) ypointsTemp(i) = ypoints(i) Next End If End If For i = 0 To npoints - 1 If i = 0 Then If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then ptType(i) = 1 Else ptType(i) = -1 concaveCount = concaveCount + 1 End If Else If (convex(xpoints(i-1), ypoints(i-1), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then ptType(i) = 1; /* point is convex */ Else ptType(i) = -1 concaveCount = concaveCount + 1 End If End If Next End Function ; /* convex: returns True If point (x2, y2) is convex ; */ Function convex(x1#, y1#, x2#, y2#, x3#, y3#) If (area(x1, y1, x2, y2, x3, y3) < 0) Then Return True Else Return False End Function ; /* area: determines area of triangle formed by three points ; */ Function area(x1#, y1#, x2#, y2#, x3#, y3#) Local areaSum# = 0 areaSum = areaSum + (x1 * (y3 - y2)) areaSum = areaSum + (x2 * (y1 - y3)) areaSum = areaSum + (x3 * (y2 - y1)) ;/* for actual area, we need to multiple areaSum * 0.5, but we are ; * only interested in the sign of the area (+/-) ; */ Return areaSum End Function ; /* triangleContainsPoints: returns true if the triangle formed by ; * three points contains another point ; */ Function triangleContainsPoint(x1#, y1#, x2#, y2#, x3#, y3#) Local i = 0 Local area1#, area2#, area3# Local noPointInTriangle = True While ((i < npoints - 1) And (noPointInTriangle)) ;/* point is concave */ If ((ptType(i) = -1) And (((xpoints(i) <> x1) And (ypoints(i) <> y1)) Or ((xpoints(i) <> x2) And (ypoints(i) <> y2)) Or ((xpoints(i) <> x3) And (ypoints(i) <> y3)))) Then area1 = area(x1, y1, x2, y2, xpoints(i), ypoints(i)) area2 = area(x2, y2, x3, y3, xpoints(i), ypoints(i)) area3 = area(x3, y3, x1, y1, xpoints(i), ypoints(i)) If (area1 > 0) Then If ((area2 > 0) And (area3 > 0)) Then noPointInTriangle = False End If End If If (area1 < 0) Then If ((area2 < 0) And (area3 < 0)) Then noPointInTriangle = False End If End If End If i = i + 1 Wend Return Not (noPointInTriangle) End Function ; /* ear: returns true if the point (x2, y2) is an ear, false ; * otherwise ; */ Function ear(x1#, y1#, x2#, y2#, x3#, y3#) If (concaveCount <> 0) Then If (triangleContainsPoint(x1, y1, x2, y2, x3, y3)) Then Return False Else Return True Else Return True End If End Function ; /* cutEar: creates triangle that represents ear for graphics purposes ; */ Function cutEar(index) Local new_i = 0 Local i = 0 ;Dim ex#(4), ey#(4) If (index = 0) Then ex(0) = xpoints(npoints-2) ey(0) = ypoints(npoints-2) ex(1) = xpoints(index) ey(1) = ypoints(index) ex(2) = xpoints(index+1) ey(2) = ypoints(index+1) ElseIf ((index > 0) And (index < npoints-2)) Then ex(0) = xpoints(index-1) ey(0) = ypoints(index-1) ex(1) = xpoints(index) ey(1) = ypoints(index) ex(2) = xpoints(index+1) ey(2) = ypoints(index+1) ElseIf (index = npoints-2) Then ex(0) = xpoints(index-1) ey(0) = ypoints(index-1) ex(1) = xpoints(index) ey(1) = ypoints(index) ex(2) = xpoints(0) ey(2) = ypoints(0) End If ex(3) = ex(0) ey(3) = ey(0) earPoly.triangle = New Triangle earPoly\v0x = ex(0) earPoly\v0y = ey(0) earPoly\v1x = ex(1) earPoly\v1y = ey(1) earPoly\v2x = ex(2) earPoly\v2y = ey(2) earCounter = earCounter + 1 End Function ; /* updatePolygon: creates new polygon without the ear that was ; * cut ; */ Function updatePolygon(index) Local new_i = 0 Local i = 0 If (index = 0) Then i = i + 1 While (i < npoints - 1) If (i = index) Then i = i + 1 If (i < npoints - 1) Then xpoints(new_i) = xpoints(i) ypoints(new_i) = ypoints(i) new_i = new_i + 1 i = i + 1 End If Wend xpoints(npoints-2) = xpoints(0) ypoints(npoints-2) = ypoints(0) npoints = npoints - 1 End Function ; /* doCutEar: Performs all the functions needed to find and cut an ; * ear. ; */ Function doCutEar() Local earHasBeenCut = False Local i = 0 While ((i < npoints - 1) And (Not earHasBeenCut)) If (ptType(i) = 1) Then ;/* point is convex */ If (i = 0) Then If (ear(xpoints(npoints-2), ypoints(npoints-2),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then cutEar(i) updatePolygon(i) earHasBeenCut = True End If Else ;/* i > 0 */ If (ear(xpoints(i-1), ypoints(i-1),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then cutEar(i); updatePolygon(i); earHasBeenCut = True; End If End If End If i = i + 1 Wend End Function ;Doom3 2D-Fake ;8.10.2004 by Triton ;http://www.silzium-net.de ; Function filltri(x1,y1,x2,y2,x3,y3,r,g,b,borderr,borderg,borderb) For oft = 0 To 1 If x1 > x2 Then p=x2 x2=x1 x1=p q=y2 y2=y1 y1=q End If If x1 > x3 Then p=x3 x3=x1 x1=p q=y3 y3=y1 y1=q End If If x2 > x3 Then p=x3 x3=x2 x2=p q=y3 y3=y2 y2=q End If Next Color r,g,b For bx1# = x1 To x2 m13# = (Float(y3-y1)/(x3-x1)) n13# = -m13*x1+y1 by1# = m13*bx1+n13 m12# = (Float(y2-y1)/(x2-x1)) n12# = -m12*x1+y1 by2# = m12*bx1+n12 If by2-by1 > 0 Then Rect bx1,by1,1,by2-by1 If by2-by1 < 0 Then Rect bx1,by2,1,by1-by2 Next For bx2 = x2 To x3 m13# = (Float(y3-y1)/(x3-x1)) n13# = -m13*x3+y3 by3# = m13*bx2+n13 m23# = (Float(y3-y2)/(x3-x2)) n23# = -m23*x2+y2 by4# = m23*bx2+n23 If by4-by3 > 0 Then Rect bx2,by3,1,by4-by3 If by4-by3 < 0 Then Rect bx2,by4,1,by3-by4 Next Color borderr,borderg,borderb Line x1,y1,x2,y2 Line x1,y1,x3,y3 Line x2,y2,x3,y3 End Function ;kruisen, determines if line x1,y1-x2,y2 and line x3,y3-x4,y4 are intersecting Function Kruisen(x1#, y1#, x2#, y2#, x3#, y3#, x4#, y4#) If (y2 <> y1) Then dx1# = (x2 - x1) / (y2 - y1) If (y4 <> y3) Then dx2# = (x4 - x3) / (y4 - y3) grens3 = x1 + (y3 - y1) * dx1 grens4 = x1 + (y4 - y1) * dx1 grens1 = x3 + (y1 - y3) * dx2 grens2 = x3 + (y2 - y3) * dx2 If y4 < y3 Then m34 = y4: n34 = y3 Else m34 = y3: n34 = y4 If y2 < y1 Then m12 = y2: n12 = y1 Else m12 = y1: n12 = y2 If (y2 <> y1) Then test3 = (x3 < grens3) Else test3 = (x3 < x1) And (x3 < x2) If (y2 <> y1) Then test4 = (x4 < grens4) Else test4 = (x4 < x1) And (x4 < x2) If (y3 <> y4) Then test1 = (x1 < grens1) Else test1 = (x1 < x3) And (x1 < x4) If (y3 <> y4) Then test2 = (x2 < grens2) Else test2 = (x2 < x3) And (x2 < x4) ok3 = (y3 > m12) And (y3 < n12) ok4 = (y4 > m12) And (y4 < n12) ok1 = (y1 > m34) And (y1 < n34) ok2 = (y2 > m34) And (y2 < n34) test = True If ok1 And ok2 Then test = test1 = test2 If ok1 And ok3 Then test = test1 <> test3 If ok1 And ok4 Then test = test1 <> test4 If ok2 And ok1 Then test = test2 = test1 If ok2 And ok3 Then test = test2 <> test3 If ok2 And ok4 Then test = test2 <> test4 If ok3 And ok1 Then test = test3 <> test1 If ok3 And ok2 Then test = test3 <> test2 If ok3 And ok4 Then test = test3 = test4 If ok4 And ok1 Then test = test4 <> test1 If ok4 And ok2 Then test = test4 <> test2 If ok4 And ok3 Then test = test4 = test3 Return Not(test) End Function ; /* polygonClockwise: Returns true if user inputted polygon in ; * clockwise order, false if counterclockwise. ; * The Law of Cosines is used to determine the ; * angle. ; */ Function polygonClockwise() Local aa#, bb#, cc#, b#, c#, theta# Local convex_turn# Local convex_sum# = 0 For i = 0 To npoints - 2 aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i))) bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i))) cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1))) b = Sqr(bb) c = Sqr(cc) theta = ACos((bb + cc - aa) / (2 * b * c)) If (convex(xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1), xpoints(i+2), ypoints(i+2))) Then convex_turn = Pi - theta; convex_sum = convex_sum + convex_turn Else convex_sum = convex_sum - (Pi - theta) End If Next aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2))) bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2))) cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0))) b = Sqr(bb) c = Sqr(cc) theta = ACos((bb + cc - aa) / (2 * b * c)) If (convex(xpoints(npoints-2), ypoints(npoints-2),xpoints(0), ypoints(0),xpoints(1), ypoints(1))) Then convex_turn = Pi - theta convex_sum = convex_sum + convex_turn Else convex_sum = convex_sum - Pi - theta End If If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False End If End Function