凸包的算法

首先需要获得Y轴数值最大的点（对于计算机屏幕的坐标系），如果有同样大则取X轴最小的，记为zero。
然后以zero为原点，将所有其他点按极坐标从小到大排列。

使排列后极角度最小的2个点入栈，使用向量的叉积判断转向，先使下一个点入栈，依次判断下一个点的转向，如果是非左转就出栈。最后的栈就是凸包的顶点。







这就是著名的Graham scan算法。

算法实现

为了操作栈，我们需要使用.net的stack类，再自己编写一些函数。

NEXT_TO_TOP ： 获得栈顶的下一个值。

代码：

Public Class StackClass

    Dim _stack As New Stack(Of Point)

    Public Function PUSH(ByVal item As Point) As Boolean
        _stack.Push(item)
        Return True
    End Function

    Public Function POP() As Boolean
        _stack.Pop()
        Return True
    End Function

    Public Function TOP() As Point
        Return _XXXXXXXXek
    End Function

    Public Function NEXT_TO_TOP() As Point
        Dim _tmp As Point
        Dim _result As Point
        _tmp = _stack.Pop()
        _result = _XXXXXXXXek
        _stack.Push(_tmp)
        Return _result
    End Function

    Public Function StackToArray() As Point()
        Return _XXXXXXXXArray
    End Function

End Class


下面是凸包类：

Public Class Convex
    Public Structure POINT_STR

        Dim p As Point
        Dim drg As Double

    End Structure


    Public Sub BubbleSort(ByVal array_in() As POINT_STR)
        Dim c As Long
        Dim i As Integer, temp As POINT_STR, w As Integer
        For c = 2 To array_in.Length
            For i = 0 To UBound(array_in) - 1
                If (array_in(i).drg > array_in(i + 1).drg) Then
                    temp = array_in(i)
                    array_in(i) = array_in(i + 1)
                    array_in(i + 1) = temp
                End If
            Next

        Next
    End Sub

    Public Function ConvexHull(ByVal input_point() As Point) As Point()
        Dim max As Integer = 0
        Dim _zero As Point
        Dim point_var(input_point.Length - 1) As POINT_STR
        Dim loopvar As Integer

        For Each item As Point In input_point
            If item.Y > max Then
                max = item.Y
                _zero = item
            End If
        Next


        Dim c As Integer = 0

        For Each item As Point In input_point

            If _zero.X = item.X And _zero.Y = item.Y Then
                point_var(c).drg = 9999
                point_var(c).p = _zero
            Else
                point_var(c).drg = GetDrg(_zero, item)
                point_var(c).p = item
            End If

            c += 1
        Next

        ReDim Preserve point_var(point_var.Length - 2)

        BubbleSort(point_var)

        Dim loli As New StackClass
        loli.PUSH(point_var(0).p)
        loli.PUSH(point_var(1).p)


        For loopvar = 2 To UBound(point_var)
            If Not CROSS_PRODUCK(XXXXXXXXT_TO_TOP, XXXXXXXP, point_var(loopvar).p) Then
                loli.POP()
            End If
            loli.PUSH(point_var(loopvar).p)
        Next
        Dim result() As Point
        result = XXXXXXXackToArray
        Return result
    End Function

    Public Function CROSS_PRODUCK(ByVal p0 As Point, ByVal p1 As Point, ByVal p2 As Point) As Boolean

        Dim _produck As Integer
        _produck = (p1.X - p0.X) * (p2.Y - p0.Y) - (p2.X - p0.X) * (p1.Y - p0.Y)

        If _produck <= 0 Then Return True Else
        Return False

    End Function


    Public Function GetDrg(ByVal p0 As Point, ByVal p1 As Point) As Double
        Dim _zero As Point
        _zero = New Point(Math.Abs(p1.X - p0.X), Math.Abs(p1.Y - p0.Y))
        Dim tmp As Double
        tmp = XXXXXXXan(_zero.Y / _zero.X) * (180 / Math.PI)
        If p1.X < p0.X Then tmp = 90 - tmp + 90
        Return tmp
    End Function
End Class

由于只是简单的实现，对特殊情况没有考虑，各位请自行修改。