Thanks Damon. After I run out of fingers and toes, math becomes Greek too me. Even so, I did learn a few things and your reply helped me narrow down my search for information. I found this and it seems to work thus far...
In a module:
<table width="100%" border="1" bgcolor="White" style="filter
rogid:DXImageTransform.Microsoft.Gradient(endColorstr='#C0CFE2', startColorstr='#FFFFFF', gradientType='0');"><tr><TD><font size="2" face=Courier New> <font color="#0000A0">Option</font> <font color="#0000A0">Explicit</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Const</font> PI = 3.14159265
<font color="#0000A0">Public</font> <font color="#0000A0">Type</font> POINTAPI
x <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
y <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">End</font> <font color="#0000A0">Type</font>
<font color="#0000A0">Public</font> m_NumPoints <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Public</font> m_Points() <font color="#0000A0">As</font> POINTAPI
<font color="#008000">' Copy of points used for triangulation.</font>
<font color="#0000A0">Public</font> m_NumCopyPoints <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Public</font> m_CopyPoints() <font color="#0000A0">As</font> POINTAPI
<font color="#008000">' Triangles.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Type</font> Triangle
Points(1 <font color="#0000A0">To</font> 3) <font color="#0000A0">As</font> POINTAPI
<font color="#0000A0">End</font> <font color="#0000A0">Type</font>
<font color="#0000A0">Public</font> m_NumTriangles <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Public</font> m_Triangles() <font color="#0000A0">As</font> Triangle
<font color="#008000">' Find the polygon's centroid.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Sub</font> FindCentroid(ByRef x <font color="#0000A0">As</font> Single, <font color="#0000A0">ByRef</font> y <font color="#0000A0">As</font> Single)
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> second_factor <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> polygon_area <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Add the first point at the end of the array.</font>
<font color="#0000A0">ReDim</font> <font color="#0000A0">Preserve</font> m_Points(1 <font color="#0000A0">To</font> m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)
<font color="#008000"> ' Find the centroid.</font>
x = 0
y = 0
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> m_NumPoints
second_factor = _
m_Points(pt).x * m_Points(pt + 1).y - _
m_Points(pt + 1).x * m_Points(pt).y
x = x + (m_Points(pt).x + m_Points(pt + 1).x) * _
second_factor
y = y + (m_Points(pt).y + m_Points(pt + 1).y) * _
second_factor
<font color="#0000A0">Next</font> pt
<font color="#008000"> ' Divide by 6 times the polygon's area.</font>
polygon_area = PolygonArea
x = x / 6 / polygon_area
y = y / 6 / polygon_area
<font color="#008000"> ' If the values are negative, the polygon is</font>
<font color="#008000"> ' oriented counterclockwise. Reverse the signs.</font>
<font color="#0000A0">If</font> x < 0 <font color="#0000A0">Then</font>
x = -x
y = -y
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
<font color="#008000">' Find the indexes of three points that form an ear.</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Sub</font> FindEar(ByRef A <font color="#0000A0">As</font> Double, <font color="#0000A0">ByRef</font> B <font color="#0000A0">As</font> Double, <font color="#0000A0">ByRef</font> C <font color="#0000A0">As</font> Double)
<font color="#0000A0">For</font> A = 1 <font color="#0000A0">To</font> m_NumCopyPoints
<font color="#0000A0">If</font> FormsEar(A, A + 1, A + 2) <font color="#0000A0">Then</font>
B = A + 1
<font color="#0000A0">If</font> B > m_NumCopyPoints <font color="#0000A0">Then</font> B = 1
C = B + 1
<font color="#0000A0">If</font> C > m_NumCopyPoints <font color="#0000A0">Then</font> C = 1
<font color="#0000A0">Exit</font> <font color="#0000A0">Sub</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">Next</font> A
<font color="#008000"> ' We should never get here because there should</font>
<font color="#008000"> ' always be at least two ears.</font>
<font color="#0000A0">Stop</font>
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
<font color="#008000">' Return True if the three points form an ear.</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Function</font> FormsEar(ByVal A <font color="#0000A0">As</font> Double, <font color="#0000A0">ByVal</font> B <font color="#0000A0">As</font> Double, <font color="#0000A0">ByVal</font> C <font color="#0000A0">As</font> Double) <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> test_points(1 <font color="#0000A0">To</font> 3) <font color="#0000A0">As</font> POINTAPI
<font color="#008000"> ' Assume the points form an ear.</font>
FormsEar = <font color="#0000A0">True</font>
<font color="#008000"> ' See if the angle ABC is concave.</font>
<font color="#0000A0">If</font> GetAngle( _
m_CopyPoints(A).x, m_CopyPoints(A).y, _
m_CopyPoints(B).x, m_CopyPoints(B).y, _
m_CopyPoints(C).x, m_CopyPoints(C).y) > 0 _
<font color="#0000A0">Then</font>
<font color="#008000"> ' This is a concave corner so the triangle</font>
<font color="#008000"> ' cannot be an ear.</font>
FormsEar = <font color="#0000A0">False</font>
<font color="#0000A0">Exit</font> <font color="#0000A0">Function</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#008000"> ' Make the triangle A, B, C.</font>
test_points(1) = m_CopyPoints(A)
test_points(2) = m_CopyPoints(B)
test_points(3) = m_CopyPoints(C)
<font color="#008000"> ' Check the other points to see if they lie in the</font>
<font color="#008000"> ' triangle A, B, C.</font>
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> m_NumCopyPoints
<font color="#0000A0">If</font> pt <> A <font color="#0000A0">And</font> pt <> B <font color="#0000A0">And</font> pt <> C <font color="#0000A0">Then</font>
<font color="#0000A0">With</font> m_CopyPoints(pt)
<font color="#0000A0">If</font> PointInPolygon(.x, .y, 3, test_points) <font color="#0000A0">Then</font>
<font color="#008000"> ' This point is in the triangle so</font>
<font color="#008000"> ' this is not an ear.</font>
FormsEar = <font color="#0000A0">False</font>
<font color="#0000A0">Exit</font> <font color="#0000A0">For</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">End</font> <font color="#0000A0">With</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">Next</font> pt
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' If the polygon is oriented counterclockwise,</font>
<font color="#008000">' reverse the order of its points.</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Sub</font> OrientPolygonClockwise(ByVal num_polygon_points <font color="#0000A0">As</font> Double, polygon_points() <font color="#0000A0">As</font> POINTAPI)
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> temp_point <font color="#0000A0">As</font> POINTAPI
<font color="#0000A0">If</font> <font color="#0000A0">Not</font> PolygonIsOrientedClockwise() <font color="#0000A0">Then</font>
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> num_polygon_points \ 2
temp_point = polygon_points(pt)
polygon_points(pt) = polygon_points(num_polygon_points - pt + 1)
polygon_points(num_polygon_points - pt + 1) = temp_point
<font color="#0000A0">Next</font> pt
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
<font color="#008000">' Return True if the point is in the polygon.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> PointInPolygon(ByVal x <font color="#0000A0">As</font> Double, <font color="#0000A0">ByVal</font> y _
<font color="#0000A0">As</font> Double, <font color="#0000A0">ByVal</font> num_polygon_points <font color="#0000A0">As</font> Double, _
polygon_points() <font color="#0000A0">As</font> POINTAPI) <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> total_angle <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Get the angle between the point and the</font>
<font color="#008000"> ' first and last vertices.</font>
total_angle = GetAngle( _
polygon_points(num_polygon_points).x, _
polygon_points(num_polygon_points).y, _
x, y, _
polygon_points(1).x, polygon_points(1).y)
<font color="#008000"> ' Add the angles from the point to each other</font>
<font color="#008000"> ' pair of vertices.</font>
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> num_polygon_points - 1
total_angle = total_angle + GetAngle( _
polygon_points(pt).x, polygon_points(pt).y, _
x, y, _
polygon_points(pt + 1).x, polygon_points(pt + _
1).y)
<font color="#0000A0">Next</font> pt
<font color="#008000"> ' The total angle should be 2 * PI or -2 * PI if</font>
<font color="#008000"> ' the point is in the polygon and close to zero</font>
<font color="#008000"> ' if the point is outside the polygon.</font>
PointInPolygon = (Abs(total_angle) > PI)
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return True if the polygon is oriented clockwise.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> PolygonIsOrientedClockwise() <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
PolygonIsOrientedClockwise = SignedPolygonArea() < 0
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return the polygon's area in "square" pixels.</font>
<font color="#008000">' Add the areas of the trapezoids defined by the</font>
<font color="#008000">' polygon's edges dropped to the X-axis. When the</font>
<font color="#008000">' program considers a bottom edge of a polygon, the</font>
<font color="#008000">' calculation gives a negative area so the space</font>
<font color="#008000">' between the polygon and the axis is subtracted,</font>
<font color="#008000">' leaving the polygon's area. This method gives odd</font>
<font color="#008000">' results for non-simple polygons.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> PolygonArea() <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Return the absolute value of the signed area.</font>
<font color="#008000"> ' The signed area is negative if the polyogn is</font>
<font color="#008000"> ' oriented clockwise.</font>
PolygonArea = Abs(SignedPolygonArea())
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return True if the polygon is convex.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> PolygonIsConvex() <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> cross_product <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> got_negative <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
<font color="#0000A0">Dim</font> got_positive <font color="#0000A0">As</font> <font color="#0000A0">Boolean</font>
<font color="#008000"> ' For each set of three adjacent points A, B, C,</font>
<font color="#008000"> ' find the dot product AB · BC. If the sign of</font>
<font color="#008000"> ' all the dot products is the same, the angles</font>
<font color="#008000"> ' are all positive or negative (depending on the</font>
<font color="#008000"> ' order in which we visit them) so the polygon</font>
<font color="#008000"> ' is convex.</font>
<font color="#008000"> ' Assume the polygon is non-convex.</font>
PolygonIsConvex = <font color="#0000A0">False</font>
<font color="#008000"> ' Look at the first set of points.</font>
cross_product = CrossProductLength( _
m_Points(m_NumPoints - 1).x, m_Points(m_NumPoints - 1).y, _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y)
<font color="#0000A0">If</font> cross_product < 0 <font color="#0000A0">Then</font>
got_negative = <font color="#0000A0">True</font>
<font color="#0000A0">ElseIf</font> cross_product > 0 <font color="#0000A0">Then</font>
got_positive = <font color="#0000A0">True</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#008000"> ' Look at the second set of points.</font>
cross_product = CrossProductLength( _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y, _
m_Points(2).x, m_Points(2).y)
<font color="#0000A0">If</font> cross_product < 0 <font color="#0000A0">Then</font>
got_negative = <font color="#0000A0">True</font>
<font color="#0000A0">ElseIf</font> cross_product > 0 <font color="#0000A0">Then</font>
got_positive = <font color="#0000A0">True</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">If</font> got_negative <font color="#0000A0">And</font> got_positive <font color="#0000A0">Then</font> <font color="#0000A0">Exit</font> <font color="#0000A0">Function</font>
<font color="#008000"> ' Look at the remaining triples of points.</font>
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> m_NumPoints - 2
cross_product = CrossProductLength( _
m_Points(pt).x, m_Points(pt).y, _
m_Points(pt + 1).x, m_Points(pt + 1).y, _
m_Points(pt + 2).x, m_Points(pt + 2).y)
<font color="#0000A0">If</font> cross_product < 0 <font color="#0000A0">Then</font>
got_negative = <font color="#0000A0">True</font>
<font color="#0000A0">ElseIf</font> cross_product > 0 <font color="#0000A0">Then</font>
got_positive = <font color="#0000A0">True</font>
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">If</font> got_negative <font color="#0000A0">And</font> got_positive <font color="#0000A0">Then</font> <font color="#0000A0">Exit</font> <font color="#0000A0">Function</font>
<font color="#0000A0">Next</font> pt
<font color="#008000"> ' If we got this far, the polygon is convex.</font>
PolygonIsConvex = <font color="#0000A0">True</font>
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return the angle with tangent opp/hyp. The returned</font>
<font color="#008000">' value is between PI and -PI.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> ATan2(ByVal opp <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> adj <font color="#0000A0">As</font> Single) <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> angle <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Get the basic angle.</font>
<font color="#0000A0">If</font> Abs(adj) < 0.0001 <font color="#0000A0">Then</font>
angle = PI / 2
<font color="#0000A0">Else</font>
angle = Abs(Atn(opp / adj))
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#008000"> ' See if we are in quadrant 2 or 3.</font>
<font color="#0000A0">If</font> adj < 0 <font color="#0000A0">Then</font>
<font color="#008000"> ' angle > PI/2 or angle < -PI/2.</font>
angle = PI - angle
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#008000"> ' See if we are in quadrant 3 or 4.</font>
<font color="#0000A0">If</font> opp < 0 <font color="#0000A0">Then</font>
angle = -angle
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#008000"> ' Return the result.</font>
ATan2 = angle
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return the cross product AB x BC.</font>
<font color="#008000">' The cross product is a vector perpendicular to AB</font>
<font color="#008000">' and BC having length |AB| * |BC| * Sin(theta) and</font>
<font color="#008000">' with direction given by the right-hand rule.</font>
<font color="#008000">' For two vectors in the X-Y plane, the result is a</font>
<font color="#008000">' vector with X and Y components 0 so the Z component</font>
<font color="#008000">' gives the vector's length and direction.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> CrossProductLength( _
<font color="#0000A0">ByVal</font> Ax <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Ay <font color="#0000A0">As</font> Single, _
<font color="#0000A0">ByVal</font> Bx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> By <font color="#0000A0">As</font> Single, _
<font color="#0000A0">ByVal</font> Cx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Cy <font color="#0000A0">As</font> <font color="#0000A0">Single</font> _
) <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BAx <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BAy <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BCx <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BCy <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Get the vectors' coordinates.</font>
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By
<font color="#008000"> ' Calculate the Z coordinate of the cross product.</font>
CrossProductLength = BAx * BCy - BAy * BCx
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return the dot product AB · BC.</font>
<font color="#008000">' Note that AB · BC = |AB| * |BC| * Cos(theta).</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Function</font> DotProduct( _
<font color="#0000A0">ByVal</font> Ax <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Ay <font color="#0000A0">As</font> Single, _
<font color="#0000A0">ByVal</font> Bx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> By <font color="#0000A0">As</font> Single, _
<font color="#0000A0">ByVal</font> Cx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Cy <font color="#0000A0">As</font> <font color="#0000A0">Single</font> _
) <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BAx <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BAy <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BCx <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> BCy <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Get the vectors' coordinates.</font>
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By
<font color="#008000"> ' Calculate the dot product.</font>
DotProduct = BAx * BCx + BAy * BCy
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Return the angle ABC.</font>
<font color="#008000">' Return a value between PI and -PI.</font>
<font color="#008000">' Note that the value is the opposite of what you might</font>
<font color="#008000">' expect because Y coordinates increase downward.</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Function</font> GetAngle(ByVal Ax <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Ay <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Bx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> By <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Cx <font color="#0000A0">As</font> Single, <font color="#0000A0">ByVal</font> Cy <font color="#0000A0">As</font> Single) <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> dot_product <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> cross_product <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Get the dot product and cross product.</font>
dot_product = DotProduct(Ax, Ay, Bx, By, Cx, Cy)
cross_product = CrossProductLength(Ax, Ay, Bx, By, Cx, Cy)
<font color="#008000"> ' Calculate the angle.</font>
GetAngle = ATan2(cross_product, dot_product)
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Remove an ear from the polygon.</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Sub</font> RemoveEar()
<font color="#0000A0">Dim</font> A <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> B <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> C <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> old_point <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> new_point <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#008000"> ' Find an ear.</font>
FindEar A, B, C
<font color="#008000"> ' Create a new triangle for the ear.</font>
m_NumTriangles = m_NumTriangles + 1
<font color="#0000A0">With</font> m_Triangles(m_NumTriangles)
.Points(1) = m_CopyPoints(A)
.Points(2) = m_CopyPoints(B)
.Points(3) = m_CopyPoints(C)
<font color="#0000A0">End</font> <font color="#0000A0">With</font>
<font color="#008000"> ' Remove the ear from the polygon.</font>
new_point = 0
<font color="#0000A0">For</font> old_point = 1 <font color="#0000A0">To</font> m_NumCopyPoints
<font color="#0000A0">If</font> old_point <> B <font color="#0000A0">Then</font>
new_point = new_point + 1
m_CopyPoints(new_point) = m_CopyPoints(old_point)
<font color="#0000A0">End</font> <font color="#0000A0">If</font>
<font color="#0000A0">Next</font> old_point
m_NumCopyPoints = m_NumCopyPoints - 1
<font color="#008000"> ' Repeat the first two points.</font>
m_CopyPoints(m_NumCopyPoints + 1) = m_CopyPoints(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_CopyPoints(2)
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
<font color="#008000">' Return the polygon's area in "square" pixels.</font>
<font color="#008000">' Add the areas of the trapezoids defined by the</font>
<font color="#008000">' polygon's edges dropped to the X-axis. When the</font>
<font color="#008000">' program considers a bottom edge of a polygon, the</font>
<font color="#008000">' calculation gives a negative area so the space</font>
<font color="#008000">' between the polygon and the axis is subtracted,</font>
<font color="#008000">' leaving the polygon's area. This method gives odd</font>
<font color="#008000">' results for non-simple polygons.</font>
<font color="#008000">'</font>
<font color="#008000">' The value will be negative if the polyogn is</font>
<font color="#008000">' oriented clockwise.</font>
<font color="#0000A0">Private</font> <font color="#0000A0">Function</font> SignedPolygonArea() <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#0000A0">Dim</font> area <font color="#0000A0">As</font> <font color="#0000A0">Single</font>
<font color="#008000"> ' Add the first point to the end.</font>
<font color="#0000A0">ReDim</font> <font color="#0000A0">Preserve</font> m_Points(1 <font color="#0000A0">To</font> m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)
<font color="#008000"> ' Get the areas.</font>
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> m_NumPoints
area = area + _
(m_Points(pt + 1).x - m_Points(pt).x) * _
(m_Points(pt + 1).y + m_Points(pt).y) / 2
<font color="#0000A0">Next</font> pt
<font color="#008000"> ' Return the result.</font>
SignedPolygonArea = area
<font color="#0000A0">End</font> <font color="#0000A0">Function</font>
<font color="#008000">' Traingulate the polygon.</font>
<font color="#008000">'</font>
<font color="#008000">' For a nice, detailed explanation of this method,</font>
<font color="#008000">' see Ian Garton's Web page:</font>
<font color="#008000">' http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html</font>
<font color="#0000A0">Public</font> <font color="#0000A0">Sub</font> Triangulate()
<font color="#0000A0">Dim</font> pt <font color="#0000A0">As</font> <font color="#0000A0">Double</font>
<font color="#008000"> ' Copy the points into a new array.</font>
m_NumCopyPoints = m_NumPoints
<font color="#0000A0">ReDim</font> m_CopyPoints(1 <font color="#0000A0">To</font> m_NumCopyPoints + 2)
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> m_NumPoints
m_CopyPoints(pt) = m_Points(pt)
<font color="#0000A0">Next</font> pt
<font color="#008000"> ' Orient the polygon.</font>
OrientPolygonClockwise m_NumCopyPoints, m_CopyPoints
<font color="#008000"> ' Repeat the first two points.</font>
m_CopyPoints(m_NumCopyPoints + 1) = m_Points(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_Points(2)
<font color="#008000">''@</font>
<font color="#008000">'For pt = 1 To m_NumCopyPoints</font>
<font color="#008000">' With m_CopyPoints(pt)</font>
<font color="#008000">' EditorForm.CurrentX = .x</font>
<font color="#008000">' EditorForm.CurrentY = .y</font>
<font color="#008000">' EditorForm.Print pt</font>
<font color="#008000">' End With</font>
<font color="#008000">'Next pt</font>
<font color="#008000">''@</font>
<font color="#008000"> ' Make room for the triangles.</font>
m_NumTriangles = 0
<font color="#0000A0">ReDim</font> m_Triangles(1 <font color="#0000A0">To</font> m_NumPoints - 2)
<font color="#008000"> ' While the copy of the polygon has more than</font>
<font color="#008000"> ' three points, remove an ear.</font>
<font color="#0000A0">Do</font> <font color="#0000A0">While</font> m_NumCopyPoints > 3
<font color="#008000"> ' Remove an ear from the polygon.</font>
RemoveEar
<font color="#0000A0">Loop</font>
<font color="#008000"> ' Copy the last three points into their own triangle.</font>
m_NumTriangles = m_NumTriangles + 1
<font color="#0000A0">With</font> m_Triangles(m_NumTriangles)
<font color="#0000A0">For</font> pt = 1 <font color="#0000A0">To</font> 3
.Points(pt) = m_CopyPoints(pt)
<font color="#0000A0">Next</font> pt
<font color="#0000A0">End</font> <font color="#0000A0">With</font>
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
</FONT></td></tr></table><button onclick='document.all("125200783837368").value=document.all("125200783837368").value.replace(/<br \/>\s\s/g,"");document.all("125200783837368").value=document.all("125200783837368").value.replace(/<br \/>/g,"");window.clipboardData.setData("Text",document.all("125200783837368").value);'>Copy to Clipboard</BUTTON><textarea style="position:absolute;visibility:hidden" name="125200783837368" wrap="virtual">
Option Explicit
Public Const PI = 3.14159265
Public Type POINTAPI
x As Double
y As Double
End Type
Public m_NumPoints As Double
Public m_Points() As POINTAPI
' Copy of points used for triangulation.
Public m_NumCopyPoints As Double
Public m_CopyPoints() As POINTAPI
' Triangles.
Public Type Triangle
Points(1 To 3) As POINTAPI
End Type
Public m_NumTriangles As Double
Public m_Triangles() As Triangle
' Find the polygon's centroid.
Public Sub FindCentroid(ByRef x As Single, ByRef y As Single)
Dim pt As Double
Dim second_factor As Single
Dim polygon_area As Single
' Add the first point at the end of the array.
ReDim Preserve m_Points(1 To m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)
' Find the centroid.
x = 0
y = 0
For pt = 1 To m_NumPoints
second_factor = _
m_Points(pt).x * m_Points(pt + 1).y - _
m_Points(pt + 1).x * m_Points(pt).y
x = x + (m_Points(pt).x + m_Points(pt + 1).x) * _
second_factor
y = y + (m_Points(pt).y + m_Points(pt + 1).y) * _
second_factor
Next pt
' Divide by 6 times the polygon's area.
polygon_area = PolygonArea
x = x / 6 / polygon_area
y = y / 6 / polygon_area
' If the values are negative, the polygon is
' oriented counterclockwise. Reverse the signs.
If x < 0 Then
x = -x
y = -y
End If
End Sub
' Find the indexes of three points that form an ear.
Private Sub FindEar(ByRef A As Double, ByRef B As Double, ByRef C As Double)
For A = 1 To m_NumCopyPoints
If FormsEar(A, A + 1, A + 2) Then
B = A + 1
If B > m_NumCopyPoints Then B = 1
C = B + 1
If C > m_NumCopyPoints Then C = 1
Exit Sub
End If
Next A
' We should never get here because there should
' always be at least two ears.
Stop
End Sub
' Return True if the three points form an ear.
Private Function FormsEar(ByVal A As Double, ByVal B As Double, ByVal C As Double) As Boolean
Dim pt As Double
Dim test_points(1 To 3) As POINTAPI
' Assume the points form an ear.
FormsEar = True
' See if the angle ABC is concave.
If GetAngle( _
m_CopyPoints(A).x, m_CopyPoints(A).y, _
m_CopyPoints(B).x, m_CopyPoints(B).y, _
m_CopyPoints(C).x, m_CopyPoints(C).y) > 0 _
Then
' This is a concave corner so the triangle
' cannot be an ear.
FormsEar = False
Exit Function
End If
' Make the triangle A, B, C.
test_points(1) = m_CopyPoints(A)
test_points(2) = m_CopyPoints(B)
test_points(3) = m_CopyPoints(C)
' Check the other points to see if they lie in the
' triangle A, B, C.
For pt = 1 To m_NumCopyPoints
If pt <> A And pt <> B And pt <> C Then
With m_CopyPoints(pt)
If PointInPolygon(.x, .y, 3, test_points) Then
' This point is in the triangle so
' this is not an ear.
FormsEar = False
Exit For
End If
End With
End If
Next pt
End Function
' If the polygon is oriented counterclockwise,
' reverse the order of its points.
Private Sub OrientPolygonClockwise(ByVal num_polygon_points As Double, polygon_points() As POINTAPI)
Dim pt As Double
Dim temp_point As POINTAPI
If Not PolygonIsOrientedClockwise() Then
For pt = 1 To num_polygon_points \ 2
temp_point = polygon_points(pt)
polygon_points(pt) = polygon_points(num_polygon_points - pt + 1)
polygon_points(num_polygon_points - pt + 1) = temp_point
Next pt
End If
End Sub
' Return True if the point is in the polygon.
Public Function PointInPolygon(ByVal x As Double, ByVal y _
As Double, ByVal num_polygon_points As Double, _
polygon_points() As POINTAPI) As Boolean
Dim pt As Double
Dim total_angle As Single
' Get the angle between the point and the
' first and last vertices.
total_angle = GetAngle( _
polygon_points(num_polygon_points).x, _
polygon_points(num_polygon_points).y, _
x, y, _
polygon_points(1).x, polygon_points(1).y)
' Add the angles from the point to each other
' pair of vertices.
For pt = 1 To num_polygon_points - 1
total_angle = total_angle + GetAngle( _
polygon_points(pt).x, polygon_points(pt).y, _
x, y, _
polygon_points(pt + 1).x, polygon_points(pt + _
1).y)
Next pt
' The total angle should be 2 * PI or -2 * PI if
' the point is in the polygon and close to zero
' if the point is outside the polygon.
PointInPolygon = (Abs(total_angle) > PI)
End Function
' Return True if the polygon is oriented clockwise.
Public Function PolygonIsOrientedClockwise() As Boolean
PolygonIsOrientedClockwise = SignedPolygonArea() < 0
End Function
' Return the polygon's area in "square" pixels.
' Add the areas of the trapezoids defined by the
' polygon's edges dropped to the X-axis. When the
' program considers a bottom edge of a polygon, the
' calculation gives a negative area so the space
' between the polygon and the axis is subtracted,
' leaving the polygon's area. This method gives odd
' results for non-simple polygons.
Public Function PolygonArea() As Single
' Return the absolute value of the signed area.
' The signed area is negative if the polyogn is
' oriented clockwise.
PolygonArea = Abs(SignedPolygonArea())
End Function
' Return True if the polygon is convex.
Public Function PolygonIsConvex() As Boolean
Dim pt As Double
Dim cross_product As Single
Dim got_negative As Boolean
Dim got_positive As Boolean
' For each set of three adjacent points A, B, C,
' find the dot product AB · BC. If the sign of
' all the dot products is the same, the angles
' are all positive or negative (depending on the
' order in which we visit them) so the polygon
' is convex.
' Assume the polygon is non-convex.
PolygonIsConvex = False
' Look at the first set of points.
cross_product = CrossProductLength( _
m_Points(m_NumPoints - 1).x, m_Points(m_NumPoints - 1).y, _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If
' Look at the second set of points.
cross_product = CrossProductLength( _
m_Points(m_NumPoints).x, m_Points(m_NumPoints).y, _
m_Points(1).x, m_Points(1).y, _
m_Points(2).x, m_Points(2).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If
If got_negative And got_positive Then Exit Function
' Look at the remaining triples of points.
For pt = 1 To m_NumPoints - 2
cross_product = CrossProductLength( _
m_Points(pt).x, m_Points(pt).y, _
m_Points(pt + 1).x, m_Points(pt + 1).y, _
m_Points(pt + 2).x, m_Points(pt + 2).y)
If cross_product < 0 Then
got_negative = True
ElseIf cross_product > 0 Then
got_positive = True
End If
If got_negative And got_positive Then Exit Function
Next pt
' If we got this far, the polygon is convex.
PolygonIsConvex = True
End Function
' Return the angle with tangent opp/hyp. The returned
' value is between PI and -PI.
Public Function ATan2(ByVal opp As Single, ByVal adj As Single) As Single
Dim angle As Single
' Get the basic angle.
If Abs(adj) < 0.0001 Then
angle = PI / 2
Else
angle = Abs(Atn(opp / adj))
End If
' See if we are in quadrant 2 or 3.
If adj < 0 Then
' angle > PI/2 or angle < -PI/2.
angle = PI - angle
End If
' See if we are in quadrant 3 or 4.
If opp < 0 Then
angle = -angle
End If
' Return the result.
ATan2 = angle
End Function
' Return the cross product AB x BC.
' The cross product is a vector perpendicular to AB
' and BC having length |AB| * |BC| * Sin(theta) and
' with direction given by the right-hand rule.
' For two vectors in the X-Y plane, the result is a
' vector with X and Y components 0 so the Z component
' gives the vector's length and direction.
Public Function CrossProductLength( _
ByVal Ax As Single, ByVal Ay As Single, _
ByVal Bx As Single, ByVal By As Single, _
ByVal Cx As Single, ByVal Cy As Single _
) As Single
Dim BAx As Single
Dim BAy As Single
Dim BCx As Single
Dim BCy As Single
' Get the vectors' coordinates.
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By
' Calculate the Z coordinate of the cross product.
CrossProductLength = BAx * BCy - BAy * BCx
End Function
' Return the dot product AB · BC.
' Note that AB · BC = |AB| * |BC| * Cos(theta).
Private Function DotProduct( _
ByVal Ax As Single, ByVal Ay As Single, _
ByVal Bx As Single, ByVal By As Single, _
ByVal Cx As Single, ByVal Cy As Single _
) As Single
Dim BAx As Single
Dim BAy As Single
Dim BCx As Single
Dim BCy As Single
' Get the vectors' coordinates.
BAx = Ax - Bx
BAy = Ay - By
BCx = Cx - Bx
BCy = Cy - By
' Calculate the dot product.
DotProduct = BAx * BCx + BAy * BCy
End Function
' Return the angle ABC.
' Return a value between PI and -PI.
' Note that the value is the opposite of what you might
' expect because Y coordinates increase downward.
Public Function GetAngle(ByVal Ax As Single, ByVal Ay As Single, ByVal Bx As Single, ByVal By As Single, ByVal Cx As Single, ByVal Cy As Single) As Single
Dim dot_product As Single
Dim cross_product As Single
' Get the dot product and cross product.
dot_product = DotProduct(Ax, Ay, Bx, By, Cx, Cy)
cross_product = CrossProductLength(Ax, Ay, Bx, By, Cx, Cy)
' Calculate the angle.
GetAngle = ATan2(cross_product, dot_product)
End Function
' Remove an ear from the polygon.
Private Sub RemoveEar()
Dim A As Double
Dim B As Double
Dim C As Double
Dim old_point As Double
Dim new_point As Double
' Find an ear.
FindEar A, B, C
' Create a new triangle for the ear.
m_NumTriangles = m_NumTriangles + 1
With m_Triangles(m_NumTriangles)
.Points(1) = m_CopyPoints(A)
.Points(2) = m_CopyPoints(B)
.Points(3) = m_CopyPoints(C)
End With
' Remove the ear from the polygon.
new_point = 0
For old_point = 1 To m_NumCopyPoints
If old_point <> B Then
new_point = new_point + 1
m_CopyPoints(new_point) = m_CopyPoints(old_point)
End If
Next old_point
m_NumCopyPoints = m_NumCopyPoints - 1
' Repeat the first two points.
m_CopyPoints(m_NumCopyPoints + 1) = m_CopyPoints(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_CopyPoints(2)
End Sub
' Return the polygon's area in "square" pixels.
' Add the areas of the trapezoids defined by the
' polygon's edges dropped to the X-axis. When the
' program considers a bottom edge of a polygon, the
' calculation gives a negative area so the space
' between the polygon and the axis is subtracted,
' leaving the polygon's area. This method gives odd
' results for non-simple polygons.
'
' The value will be negative if the polyogn is
' oriented clockwise.
Private Function SignedPolygonArea() As Single
Dim pt As Double
Dim area As Single
' Add the first point to the end.
ReDim Preserve m_Points(1 To m_NumPoints + 1)
m_Points(m_NumPoints + 1) = m_Points(1)
' Get the areas.
For pt = 1 To m_NumPoints
area = area + _
(m_Points(pt + 1).x - m_Points(pt).x) * _
(m_Points(pt + 1).y + m_Points(pt).y) / 2
Next pt
' Return the result.
SignedPolygonArea = area
End Function
' Traingulate the polygon.
'
' For a nice, detailed explanation of this method,
' see Ian Garton's Web page:
'
http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
Public Sub Triangulate()
Dim pt As Double
' Copy the points into a new array.
m_NumCopyPoints = m_NumPoints
ReDim m_CopyPoints(1 To m_NumCopyPoints + 2)
For pt = 1 To m_NumPoints
m_CopyPoints(pt) = m_Points(pt)
Next pt
' Orient the polygon.
OrientPolygonClockwise m_NumCopyPoints, m_CopyPoints
' Repeat the first two points.
m_CopyPoints(m_NumCopyPoints + 1) = m_Points(1)
m_CopyPoints(m_NumCopyPoints + 2) = m_Points(2)
''@
'For pt = 1 To m_NumCopyPoints
' With m_CopyPoints(pt)
' EditorForm.CurrentX = .x
' EditorForm.CurrentY = .y
' EditorForm.Print pt
' End With
'Next pt
''@
' Make room for the triangles.
m_NumTriangles = 0
ReDim m_Triangles(1 To m_NumPoints - 2)
' While the copy of the polygon has more than
' three points, remove an ear.
Do While m_NumCopyPoints > 3
' Remove an ear from the polygon.
RemoveEar
Loop
' Copy the last three points into their own triangle.
m_NumTriangles = m_NumTriangles + 1
With m_Triangles(m_NumTriangles)
For pt = 1 To 3
.Points(pt) = m_CopyPoints(pt)
Next pt
End With
End Sub</textarea>
Usage:
<table width="100%" border="1" bgcolor="White" style="filter
rogid:DXImageTransform.Microsoft.Gradient(endColorstr='#C0CFE2', startColorstr='#FFFFFF', gradientType='0');"><tr><TD><font size="2" face=Courier New> <font color="#0000A0">Sub</font> Example()
<font color="#0000A0">Dim</font> r <font color="#0000A0">As</font> Range, PolyPoints() <font color="#0000A0">As</font> POINTAPI, x <font color="#0000A0">As</font> Long, y <font color="#0000A0">As</font> Long, hRgn <font color="#0000A0">As</font> <font color="#0000A0">Long</font>
<font color="#0000A0">On</font> <font color="#0000A0">Error</font> <font color="#0000A0">Resume</font> <font color="#0000A0">Next</font>
<font color="#0000A0">ReDim</font> PolyPoints(1 <font color="#0000A0">To</font> Range("A1:B51").Rows.Count)
<font color="#0000A0">For</font> <font color="#0000A0">Each</font> r <font color="#0000A0">In</font> Range("A1:B51").Rows
x = x + 1
PolyPoints(x).x = r.Cells(1).Value
PolyPoints(x).y = r.Cells(2).Value
<font color="#0000A0">Next</font>
MsgBox PointInPolygon(-84.6197, 39.2947, UBound(PolyPoints), PolyPoints)
<font color="#0000A0">End</font> <font color="#0000A0">Sub</font>
</FONT></td></tr></table><button onclick='document.all("12520078397347").value=document.all("12520078397347").value.replace(/<br \/>\s\s/g,"");document.all("12520078397347").value=document.all("12520078397347").value.replace(/<br \/>/g,"");window.clipboardData.setData("Text",document.all("12520078397347").value);'>Copy to Clipboard</BUTTON><textarea style="position:absolute;visibility:hidden" name="12520078397347" wrap="virtual">
Sub Example()
Dim r As Range, PolyPoints() As POINTAPI, x As Long, y As Long, hRgn As Long
On Error Resume Next
ReDim PolyPoints(1 To Range("A1:B51").Rows.Count)
For Each r In Range("A1:B51").Rows
x = x + 1
PolyPoints(x).x = r.Cells(1).Value
PolyPoints(x).y = r.Cells(2).Value
Next
MsgBox PointInPolygon(-84.6197, 39.2947, UBound(PolyPoints), PolyPoints)
End Sub</textarea>
I imagine that this could be whittled down by using some native function but it performs well enough as a UDF.
Please see my next post on this topic...