http://www.blitzbasic.com/Community/posts.php?topic=26708If only I could take that and add possibility of holes in the routine. I'm positive it's not a big thing to add that in, as the code seems really clean. I'l dig that up some more, but don't hold your breath...
EDIT: Actually that one is a little bogus as it doesn't seem to know the boundaries... I've had examples that I tried where it did what it tougth was right but messed it up bad. So I'll see what else I can dig up.
EDIT 2: Here's something that actually works well, but will need to add possibility of holes in the figure, and see if that will work. But it's like 3/4 of the way to what I need.
; BruteForceEarCut
; by Ian Garton (97.12.09)
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, 2
SetBuffer BackBuffer()
npoints = 0
Repeat
Cls
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
If done Then
For ti.triangle = Each triangle
draw_fill_triangle 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
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 line_intersects(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 polygon_clockwise() 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
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
For i = 0 To npoints
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"
Flip
Until KeyHit(1)
End
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
; 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 polygon_clockwise() = False 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
EndIf
EndIf
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
EndIf
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
EndIf
EndIf
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
; 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
EndIf
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
EndIf
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
EndIf
EndIf
EndIf
i = i + 1
Wend
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)
EndIf
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
; 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) And (area2 > 0) And (area3 > 0) Then
noPointInTriangle = False
EndIf
If (area1 < 0) And (area2 < 0) And (area3 < 0) Then
noPointInTriangle = False
EndIf
EndIf
i = i + 1
Wend
Return Not (noPointInTriangle)
End Function
;line_intersects: Determines if line x0,y0-x1,y1 and line x2,y2-x3,y3 are intersecting
Function line_intersects(x0#,y0#, x1#,y1#, x2#,y2#, x3#,y3#)
n# = (y0-y2) * (x3-x2) - (x0-x2) * (y3-y2)
d# = (x1-x0) * (y3-y2) - (y1-y0) * (x3-x2)
If Abs(d) < 0.0001 ; Lines are parallel
Return False
Else ; Lines might cross
Sn# = (y0-y2) * (x1-x0) - (x0-x2) * (y1-y0)
AB# = n / d
If AB > 0.0 And AB < 1.0
CD# = Sn / d
If CD>0.0 And CD<1.0 ; Intersection Point
X# = x0 + AB * (x1-x0)
Y# = y0 + AB * (y1-y0)
Return True
EndIf
EndIf
; Lines didn't cross, because the intersection was beyond the end points of the lines
EndIf
Return False ; Lines do not cross
End Function
; polygon_clockwise: Returns true if user inputted polygon in clockwise order, false if counterclockwise.
; The Law of Cosines is used to determine the angle.
Function polygon_clockwise()
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)))
theta = ACos((bb + cc - aa) / (2 * bb * bb * cc * cc))
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)))
theta = ACos((bb + cc - aa) / (2 * bb * bb * cc * cc))
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
EndIf
If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False
End Function
Function draw_fill_triangle(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
EndIf
If x1 > x3 Then
p = x3 : x3 = x1 : x1 = p : q = y3 : y3 = y1 : y1 = q
EndIf
If x2 > x3 Then
p = x3 : x3 = x2 : x2 = p : q = y3 : y3 = y2 : y2 = q
EndIf
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 Functionhttp://www.blitzbasic.com/Community/posts.php?topic=26539The notions I'm trying to find in this is about outer node and inner node, and see what can be done to add the feature there.
Here's something I meditate on:
http://www.cs.cmu.edu/~quake/triangle.htmlMore meditation:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Mesh_2/Chapter_main.html 