Calculate the angles at each of the polygon's corners. If all of the angles have the same sign (either positive or negative depending on the orientation), then the polygon is convex. In the figure, for example, the angles have opposite signs (one is drawn clockwise and the other counterclockwise) so this polygon is not convex.
|
' Return True if the polygon is convex.
Public Function PolygonIsConvex() As Boolean
Dim pt As Integer
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
|