I translated a program a while back, written by Ian Garton. The original program was written in Java.
Click with left to draw points, and with right to triangulate the polygon.
;/*-------------------------------------------------------------------*/
;/* 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
