凸壳算法

Convex hull algorithms

Posted by Jerry on May 4, 2017

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

凸壳算法(二维的)

凸壳算法是指构造(或者说找到)包括一系列的对象的边界。本文中针对二维的平面上的点,求其凸多边形的边界。

Gift wrapping algorithm

礼品包装算法是用来计算给定点的集合求其凸多边形边界的方法。算法的时间复杂度为O(n*h)其中n为点的数量,h为最后求得边界的点的数量。该算法的求解过程可以从下图中看出: https://upload.wikimedia.org/wikipedia/commons/9/9c/Animation_depicting_the_gift_wrapping_algorithm.gif

求解过程如下: 1.首先选择最左边的的点p0 2.循环 2.1.随便一个设一个值为下一个点(可以为重复)p1 2.2.遍历集合里的点(这里需要排除之前选的那些点)p,判断p0、p1、p三点组成的p1p0p角最值,然后更新p1。 2.3.更新p0,然后判断新的p0是否是等于刚刚开始的那个最左边的点,如果是的话退出循环 3.得出边界顶点集合

解决实际算法题

leetcode的求给定点集合的边界

There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

public class Solution {
    public List<Point> outerTrees(Point[] points) {
        Point first = points[0];
        int firstIndex = 0;
        // Find the leftmost point
        for (int i = 0; i < points.length; i++) {
            Point point = points[i];
            if (point.x < first.x) {
                first = point;
                firstIndex = i;
            }
        }
        
        Set<Point> answer = new HashSet<>();
        Point cur = first;
        int curIndex = firstIndex;
        answer.add(first);
        
        do {
            Point next = points[0];
            int nextIndex = 0;
            for (int i = 1; i < points.length; i++) {
                if (i == curIndex) continue;
                Point p = points[i];
                int cross = crossProductLength(p, cur, next);
                if (nextIndex == curIndex || cross > 0 ||
                        // Handle multi points in a line
                        (cross == 0 && distance(p, cur) > distance(next, cur))) {
                    next = p;
                    nextIndex = i;
                }
            }
            // Handle multi points in a line
            for (int i = 0; i < points.length; i++) {
                Point p = points[i];
                int cross = crossProductLength(p, cur, next);
                if (i != curIndex && cross == 0) {
                    answer.add(p);
                }
            }

            cur = next;
            curIndex = nextIndex;
        } while (curIndex != firstIndex);
        
        return new ArrayList<>(answer);
    }
    
    private int crossProductLength(Point A, Point B, Point C) {
        // Get the vectors' coordinates.
        int BAx = A.x - B.x;
        int BAy = A.y - B.y;
        int BCx = C.x - B.x;
        int BCy = C.y - B.y;
    
        // Calculate the Z coordinate of the cross product.
        return (BAx * BCy - BAy * BCx);
    }

    private int distance(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
}

判断一个多边形是否为凸多边形

只需要向量的叉积同号即可。

public class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        // For each set of three adjacent points A, B, C, find the cross product AB · BC. If the sign of
        // all the cross 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.
        boolean gotNegative = false;
        boolean gotPositive = false;
        int numPoints = points.size();
        int B, C;
        for (int A = 0; A < numPoints; A++) {
            // Trick to calc the last 3 points: n - 1, 0 and 1.
            B = (A + 1) % numPoints;
            C = (B + 1) % numPoints;
    
            int crossProduct =
                crossProductLength(
                    points.get(A).get(0), points.get(A).get(1),
                    points.get(B).get(0), points.get(B).get(1),
                    points.get(C).get(0), points.get(C).get(1));
            if (crossProduct < 0) {
                gotNegative = true;
            }
            else if (crossProduct > 0) {
                gotPositive = true;
            }
            if (gotNegative && gotPositive) return false;
        }
    
        // If we got this far, the polygon is convex.
        return true;
    }
    
    // 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.
    private int crossProductLength(int Ax, int Ay, int Bx, int By, int Cx, int Cy)
    {
        // Get the vectors' coordinates.
        int BAx = Ax - Bx;
        int BAy = Ay - By;
        int BCx = Cx - Bx;
        int BCy = Cy - By;
    
        // Calculate the Z coordinate of the cross product.
        return (BAx * BCy - BAy * BCx);
    }
}

参考资料

  1. wiki
  2. leetcode习题
  3. https://discuss.leetcode.com/topic/70706/beyond-my-knowledge-java-solution-with-in-line-explanation