点集凸包算法Convex Hull

收藏到CSDN网摘

求点集的凸包是经常会碰到的问题,下面是一个python实现.注意会自动忽略共线的多余点,只返回凸包的顶点坐标.

def _myDet(p, q, r):
    """Calc. determinant of a special matrix with three 2D points.

    The sign, "-" or "+", determines the side, right or left,
    respectivly, on which the point r lies, when measured against
    a directed vector from p to q.
    """
    # We use Sarrus' Rule to calculate the determinant.
    # (could also use the Numeric package...)
    sum1 = q[0]*r[1] + p[0]*q[1] + r[0]*p[1]
    sum2 = q[0]*p[1] + r[0]*q[1] + p[0]*r[1]
    return sum1 - sum2

def _isRightTurn((p, q, r)):
    "Do the vectors pq:qr form a right turn, or not?"
    assert p != q and q != r and p != r        
    if _myDet(p, q, r) < 0:
        return 1
    else:
        return 0

def _dist(p,q):
    "get distance of two points"
    return ((p[0]-q[0])**2+(p[1]-q[1])**2)**0.5

def covhull(data):
    """list[list[int, int],] -> list[int,]
    Find the convex hull.
    """
    "Calculate the convex hull of a set of points."
    # Get a local list copy of the points and sort them lexically.
    points = map(None, data)
    points.sort()
    # Build upper half of the hull.
    upper = [points[0], points[1]]
    for p in points[2:]:
        upper.append(p)
        while len(upper) > 2 and not _isRightTurn(upper[-3:]):
            del upper[-2]
    # Build lower half of the hull.
    points.reverse()
    lower = [points[0], points[1]]
    for p in points[2:]:
        lower.append(p)
        while len(lower) > 2 and not _isRightTurn(lower[-3:]):
            del lower[-2]
    # Remove duplicates.
    del lower[0]
    del lower[-1]
    # Concatenate both halfs and return.
    result = upper + lower
    print result
    return result