多边形点集排序--针对凸多边形，按逆时针方向进行排序 -

    Public Shared Sub ClockwiseSortPoints(vPoints As List(Of Point3D))
        '计算重心
        Dim center As New Point3D()
        Dim X As Double = 0, Y As Double = 0
        Dim i As Integer = 0
        While i < vPoints.Count
            X += vPoints(i).X
            Y += vPoints(i).Y
            i += 1
        End While
        center.X = CType(X, Integer) / vPoints.Count
        center.Y = CType(Y, Integer) / vPoints.Count
        '冒泡排序
        Dim i As Integer = 0
        While i < vPoints.Count - 1
            Dim j As Integer = 0
            While j < vPoints.Count - i - 1
                If PointCmp(vPoints(j), vPoints(j + 1), center) Then
                    Dim tmp As Point3D = vPoints(j)
                    vPoints(j) = vPoints(j + 1)
                    vPoints(j + 1) = tmp
                End If
                j += 1
            End While
            i += 1
        End While
    End Sub

    '若点a大于点b,即点a在点b顺时针方向,返回true,否则返回false
    Private Shared Function PointCmp(a As Point3D, b As Point3D, center As Point3D) As Boolean
        If a.X >= 0 AndAlso b.X < 0 Then
            Return True
        End If
        If a.X = 0 AndAlso b.X = 0 Then
            Return a.Y > b.Y
        End If
        '向量OA和向量OB的叉积
        Dim det As Integer = Convert.ToInt32((a.X - center.X) * (b.Y - center.Y) - (b.X - center.X) * (a.Y - center.Y))
        If det < 0 Then
            Return True
        End If
        If det > 0 Then
            Return False
        End If
        '向量OA和向量OB共线，以距离判断大小
        Dim d1 As Double = (a.X - center.X) * (a.X - center.X) + (a.Y - center.Y) * (a.Y - center.Y)
        Dim d2 As Double = (b.X - center.X) * (b.X - center.Y) + (b.Y - center.Y) * (b.Y - center.Y)
        Return d1 > d2
    End Function

分享到： QQ空间新浪微博腾讯微博微信更多

暂时没有评论

发表评论 - 不要忘了输入验证码哦！

作者：

用户：密码：注册？验证：