凸包问题的五种解法-白红宇

凸包问题的五种解法

阅读量：4284 次

发布时间：2019-05-27

本文共 12315 字，大约阅读时间需要 41 分钟。

前言：

首先，什么是凸包？
假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图：
这里写图片描述

然后，什么是凸包问题？
我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。
现给出点的数目13，和各个点的坐标。求构成凸包的点？

解一：穷举法（蛮力法）

时间复杂度：O(n³）。
思路：两点确定一条直线，如果剩余的其它点都在这条直线的同一侧，则这两个点是凸包上的点，否则就不是。
步骤：

将点集里面的所有点两两配对，组成 n(n-1)/2 条直线。

对于每条直线，再检查剩余的 (n-2) 个点是否在直线的同一侧。

如何判断一个点 p3 是在直线 p1p2 的左边还是右边呢？（坐标：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)）

这里写图片描述
当上式结果为正时，p3在直线 p1p2 的左侧；当结果为负时，p3在直线 p1p2 的右边。

解二：分治法

时间复杂度：O(n㏒n)。
思路：应用分治法思想，把一个大问题分成几个结构相同的子问题，把子问题再分成几个更小的子问题……。然后我们就能用递归的方法，分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。
步骤：

把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点（为什么呢？用反证法很容易证明，这里不详讲）。直线 P1Pn 把点集分成了两部分，即 X 轴上面和下面两部分，分别叫做上包和下包。

对上包：求距离直线 P1Pn 最远的点，即下图中的点 Pmax 。

作直线 P1Pmax 、PnPmax，把直线 P1Pmax 左侧的点当成是上包，把直线 PnPmax 右侧的点也当成是上包。

重复步骤 2、3。

对下包也作类似操作。

这里写图片描述

然而怎么求距离某直线最远的点呢？我们还是用到解一中的公式：
这里写图片描述
设有一个点 P3 和直线 P1P2 。（坐标：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)）
对上式的结果取绝对值，绝对值越大，则距离直线越远。

注意：在步骤一，如果横坐标最小的点不止一个，那么这几个点都是凸包上的点，此时上包和下包的划分就有点不同了，需要注意。

解三：Jarvis步进法

时间复杂度：O(nH)。（其中 n 是点的总个数，H 是凸包上的点的个数）
思路：

纵坐标最小的那个点一定是凸包上的点，例如图上的 P0。

从 P0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。

怎么找下一个点呢？利用夹角。假设现在已经找到 {P0，P1，P2} 了，要找下一个点：剩下的点分别和 P2 组成向量，设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了，此处为 P3 。

这里写图片描述

注意：

找第二个点 P1 时，因为已经找到的只有 P0 一个点，所以向量只能和水平线作夹角 α，当 α 最小时求得第二个点。

共线情况：如果直线 P2P3 上还有一个点 P4，即三个点共线，此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点，并且把距离 P2 最远的那个点（即图中的P4）作为最后搜索到的点，继续找它的下一个连接点。

解四：Graham扫描法

时间复杂度：O(n㏒n)
思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。
这里写图片描述
步骤：

把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。

把所有点的坐标平移一下，使 P0 作为原点，如上图。

计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。
（以上是准备步骤，以下开始求凸包）
以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：

连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。

如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。

当前点是凸包上的点，把它压入栈，执行步骤7。

检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。

最后，栈中的元素就是凸包上的点了。
以下为用Graham扫描法动态求解的过程：
这里写图片描述

解五：Melkman算法

1. 问题描述

给定一组二维坐标的集合，求从这个集合中找出这些二维坐标的外围边界。经过查询，确定了这是一个二维凸包的问题，属于计算几何的范畴。

2. `Melkman` 算法

经过查询，发现二维凸包的解法有很多种，其中 Melkman 算法是其中比较好的解决方案。Melkman 算法在点排序后可以以 O(n) 的时间复杂度计算凸包。同时 Melkman 还是一种在线的算法，虽然我这里用不到这个特性。

Melkman 算法的大致思想是这样的：首先找出所有点集合中某一个维度上的最大或者最小值，然后按照顺时针或者逆时针的方向逐个遍历集合中剩余的点。要找出集合中最外围的点，有一个不变的特性必须要保持住：

假设 $P_i,P_j,P_k$ 是凸包上逆时针方向上的连续 3 个点，那么它们必然保持一种左转的趋势，即：

$\overrightarrow{P_iP_j}\times\overrightarrow{P_jP_k}>0$

如果用 $(x_i,y_i),(x_j,y_j),(x_k,y_k)$ 来表示这三个点，亦即：

$\overrightarrow{P_iP_j}=(x_j-x_i,y_j-y_i)$

$\overrightarrow{P_jP_k}=(x_k-x_j,y_k-y_j)$

那么根据向量叉积公式必须满足：

$(x_j-x_i)<em>(y_k-y_j)-(x_k-x_j)</em>(y_j-y_i)>0$

3. 算法描述

Melkman 算法使用双端队列来实现这个原理，假设双端队列为 $D$ 。所有队列操作可以用入队首、出队首、入队尾、出队尾来描述，实际操作过程可以描述为：

假设点集合的坐标可以表示为 $(x,y)$ ，那么首先找出 $x$ 值最小的点记为 $P_0$ 。

然后选定一个方向，比如逆时针方向。然后计算所有剩余的每一个点 $P_0$ 与 $P_x$ 形成的向量 $\overrightarrow{P_0P_x}$ 与 $y$ 轴负方向的夹角。根据向量的点积公式计算出夹角之后根据夹角从小到大就行排序得到有序集合 $S={P_0,P_1,P_2…P_{n-1}}$ 。

记某一时刻 $D$ 的状态为： $P_tP_{t-1}…P_0...P_{b-1}P_b$ ，对于 $S$ 中的每一个点进行遍历：

3.1 如果是 $P_0$ 则首先将 $P_0$ 入队尾，如果是 $P_1$ 则入队尾，如果是 $P_2$ 则入队首并且入队尾。

3.2 假设遍历到当前节点 $P_i$ ：
3.2.1 如果 $P_{b-1}P_bP_i$ 能保持左转特性则继续，否则 $P_b$ 出队尾，如此往复直到 $P_{b-m-1}P_{b-m}P_i$ 能够满足左转特性， $P_i$ 入队尾。

3.2.2 如果 $P_iP_tP_{t-1}$ 能保持左转特性则继续，否则 $P_t$ 出队首，如此往复直到 $P_iP_{t-n}P_{t-n-1}$ 能够满足左转特性， $P_i$ 入队首。

返回 $D$ 。

4. 算法实现

首先给出数据结构，Point 和 Polygon：

Point.java：

package com.xxx.dvp.rest.domain.model;/** * User: wuzhiyu. * Date: 16/12/21. * Time: 15:18. */public class Point {  private double lng;  private double lat;  /* Constructors */  /* Setters and Getters */}

Polygon.java：

package com.xxx.dvp.rest.domain.model;import com.google.common.collect.Lists;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;/** * The type Melkman polygon. */public class Polygon {  private List
   
     points;  /* Constructors  */  /* Setter and Getter */  /**   * Contains boolean.   * 源代码来自 .NET Framework。多边形边界上的点不算多边形内   *   * @param point the melkman point   * @return the boolean   */  public boolean contains(Point point) {    int crossings = 0;    for (int index = 0; index < getPoints().size() - 1; index++) {      double slope = getPoints().get(index + 1).getSlope(          getPoints().get(index));      boolean cond1 = (getPoints().get(index).getLng() <= point.getLng())          && (point.getLng() < getPoints().get(index + 1).getLng());      boolean cond2 = (getPoints().get(index + 1).getLng() <= point.getLng())          && (point.getLng() < getPoints().get(index).getLng());      boolean above = ((point.getLng() - getPoints().get(index).getLng()) * slope          + getPoints().get(index).getLat()) > point.getLat();      if ((cond1 || cond2) && above) {        crossings++;      }    }    return (crossings % 2 != 0);  }  /**   * On border boolean.   *   * @param point the point   * @return the boolean   */  public boolean onBorder(Point point) {    for (int index = 0; index < getPoints().size() - 1; index++) {      double slope = getPoints().get(index + 1).getSlope(getPoints().get(index));      double latOnLine = (point.getLng() - this.points.get(index).getLng()) * slope          + this.points.get(index).getLat();      if (latOnLine == point.getLat()) {        return true;      }    }    return false;  }  @Override  public String toString() {    return "Polygon{" + "points=" + points + '}';  }}

Melkman 算法：

package com.xxx.dvp.rest.domain.service;import com.xxx.dvp.rest.domain.model.Boundary;import com.xxx.dvp.rest.domain.model.Point;import com.xxx.dvp.rest.domain.model.Polygon;import com.xxx.dvp.rest.infra.persistence.conf.DataExampleConfig;import com.fasterxml.jackson.databind.ObjectMapper;import org.geojson.Feature;import org.geojson.FeatureCollection;import java.io.IOException;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Comparator;import java.util.Deque;import java.util.List;import java.util.Set;import java.util.stream.Collectors;/** * User: wuzhiyu. * Date: 16/12/26. * Time: 10:45. */public class PointService {  public static void main(String[] argv) throws IOException {    PointService pointService = new PointService();    FeatureCollection collection = new FeatureCollection();    String fileName = "cluster_%d.txt";    for (int i = 0; i < 8; i++) {      List
   
     points = DataExampleConfig.getPoints(String.format(fileName, i));      Polygon polygon = pointService.getConvexHullWithMelkman(points);      Boundary boundaryOfPolygon = GeoService.getBoundaryOfPolygon(polygon);      Set
    
      gridsOfPolygon = GridService.getGrids(boundaryOfPolygon);      gridsOfPolygon = GridService.getGridsInPolygon(gridsOfPolygon, polygon);      List
     
       edgeOfGrids = GridService.getEdgeOfGrids(gridsOfPolygon);      Polygon newPolygon = new Polygon(edgeOfGrids);      GridService.outputBoundaryGrids(boundaryOfPolygon);      GridService.outputPoints(edgeOfGrids);      Feature polygonFeature = GeoService.getPolygonFeature(newPolygon);      collection.add(polygonFeature);      List
      
        errorPoints = points.stream()          .filter(point -> !polygon.contains(point))          .filter(point -> !polygon.onBorder(point))          .collect(Collectors.toList());      System.out.println("errorPoints = " + errorPoints);    }    ObjectMapper objectMapper = new ObjectMapper();    System.out.println(objectMapper.writeValueAsString(collection));  }  public Polygon getConvexHullWithMelkman(List
       
         pointList) {    if (pointList.size() < 3) {      return null;    }    sortByAngle(pointList);    Deque
        
          deque = new ArrayDeque<>(); pointList.forEach(point -> { switch (deque.size()) { case 0: case 1: deque.offerLast(point); return; case 2: deque.offerLast(point); deque.offerFirst(point); return; default: Point lastRightVertex = deque.pollLast(); Point lastLeftVertex = deque.pollFirst(); if (this.isLeftTurn(deque.peekLast(), lastRightVertex, point) && this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) { return; } while (!this.isLeftTurn(deque.peekLast(), lastRightVertex, point)) { lastRightVertex = deque.pollLast(); } deque.offerLast(lastRightVertex); deque.offerLast(point); while (!this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) { lastLeftVertex = deque.pollFirst(); } deque.offerFirst(lastLeftVertex); deque.offerFirst(point); return; } }); return new Polygon(new ArrayList<>(deque)); } private void sortByAngle(List
         
           pointList) { Point minLngPoint = pointList.stream() .min(Comparator.comparing(Point::getLng)).get(); pointList.remove(minLngPoint); pointList.sort(new Comparator
          
           () { @Override public int compare(Point o1, Point o2) { return Double.compare(angleWithSouth(minLngPoint, o1), angleWithSouth(minLngPoint, o2)); } }); pointList.add(0, minLngPoint); } public boolean isLeftTurn(Point point1, Point point2, Point point3) { return crossProduct(point1, point2, point3) > 0; } public double crossProduct(Point point1, Point point2, Point point3) { double x1 = point2.getLng() - point1.getLng(); double y1 = point2.getLat() - point1.getLat(); double x2 = point3.getLng() - point2.getLng(); double y2 = point3.getLat() - point2.getLat(); return x1 * y2 - x2 * y1; } public double dotProduct(Point point1, Point point2, Point point3) { double x1 = point2.getLng() - point1.getLng(); double y1 = point2.getLat() - point1.getLat(); double x2 = point3.getLng() - point2.getLng(); double y2 = point3.getLat() - point2.getLat(); return x1 * x2 + y1 * y2; } public double angleWithSouth(Point point1, Point point2) { Point point = new Point(point1.getLng(), point1.getLat() + 1); return Math.acos(this.dotProduct(point, point1, point2) / (this.norm(point, point1) * this.norm(point1, point2))); } public double norm(Point point1, Point point2) { double deltaLat = point2.getLat() - point1.getLat(); double deltaLng = point2.getLng() - point1.getLng(); return Math.sqrt(deltaLat * deltaLat + deltaLng * deltaLng); }}

上文的代码引用了一个依赖：


   
       
    
     de.grundid.opendatalab
        
    
     geojson-jackson
        
    
     1.7

输出的 json 结果可以在做可视化展示。

5. 参考文献

算法在线演示说明：http://maxgoldste.in/melkman/

http://w3.impa.br/~rdcastan/Cgeometry/

漫话二维凸包

http://www.ams.sunysb.edu/~jsbm/courses/345/13/melkman.pdf

扩展：

以上讨论的只是二维的凸包，如果延生为三维、多维的凸包问题呢？如何求解？
不过首先，二维凸包可以用来解决围栏问题、城市规划问题、聚类分析等等。但是三维、多维的凸包可能的使用范畴有哪些？

附：快包算法代码（C语言）：

#include
   
    #include
    
     int g_result[240][2];/*getResult()实现功能：以坐标P0(x1,y1)和Pn(x2,y2)为直线，找出pack里面里这条直线最远的点Pmax*并找出直线P0Pmax和PmaxPn的上包，进行递归。*注：Pack[0][0]存放点的个数，pack[1]开始存放点的坐标。*全局变量g_result[][]用来存放凸包上的点，即最终所要的答案。同样g_result[0][0]存放的是已找到的点的个数。**/void getResult(int Pack[240][2], int x1, int y1, int x2, int y2){    int i,t,x3,y3,R,Rmax,tmax;    int ResultPack[240][2];    ResultPack[0][0] = 0;    if(Pack[0][0] <= 1)        return;     x3 = Pack[1][0];    y3 = Pack[1][1];    R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;    Rmax = R;    tmax = 1;    for(i=2;i<=Pack[0][0];i++)    {        x3 = Pack[i][0];        y3 = Pack[i][1];        R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;        if(R >= 0)        {            t = ++ResultPack[0][0];            ResultPack[t][0] = x3;            ResultPack[t][1] = y3;        }        if(R > Rmax)        {            Rmax = R;            tmax = i;        }    }    if(Rmax <= 0)    {        for(i=1;i
     
       x2)        {            x2 = x3;            y2 = y3;        }    }    g_result[1][0] = x1;    g_result[1][1] = y1;    g_result[2][0] = x2;    g_result[2][1] = y2;    g_result[0][0] += 2;    getResult(Point, x1, y1, x2, y2);    getResult(Point, x2, y2, x1, y1);    printf("\n\n构成凸包的点有：\n");    for(i=1;i<=g_result[0][0];i++)        printf("(%d,%d)\n",g_result[i][0],g_result[i][1]);    system("pause");} 
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  10 
  11 
  12 
  13 
  14 
  15 
  16 
  17 
  18 
  19 
  20 
  21 
  22 
  23 
  24 
  25 
  26 
  27 
  28 
  29 
  30 
  31 
  32 
  33 
  34 
  35 
  36 
  37 
  38 
  39 
  40 
  41 
  42 
  43 
  44 
  45 
  46 
  47 
  48 
  49 
  50 
  51 
  52 
  53 
  54 
  55 
  56 
  57 
  58 
  59 
  60 
  61 
  62 
  63 
  64 
  65 
  66 
  67 
  68 
  69 
  70 
  71 
  72 
  73 
  74 
  75 
  76 
  77 
  78 
  79 
  80 
  81 
  82 
  83 
  84 
  85 
  86 
  87 
  88 
  89 
  90 
  91 
  92 
  93 
  94 
  95 
  96 
  97 
  98 
  99 
  100 
  101 
  102 
  103 
  104 
  105 
  106 
  107 
  108 
  109 
  
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  10 
  11 
  12 
  13 
  14 
  15 
  16 
  17 
  18 
  19 
  20 
  21 
  22 
  23 
  24 
  25 
  26 
  27 
  28 
  29 
  30 
  31 
  32 
  33 
  34 
  35 
  36 
  37 
  38 
  39 
  40 
  41 
  42 
  43 
  44 
  45 
  46 
  47 
  48 
  49 
  50 
  51 
  52 
  53 
  54 
  55 
  56 
  57 
  58 
  59 
  60 
  61 
  62 
  63 
  64 
  65 
  66 
  67 
  68 
  69 
  70 
  71 
  72 
  73 
  74 
  75 
  76 
  77 
  78 
  79 
  80 
  81 
  82 
  83 
  84 
  85 
  86 
  87 
  88 
  89 
  90 
  91 
  92 
  93 
  94 
  95 
  96 
  97 
  98 
  99 
  100 
  101 
  102 
  103 
  104 
  105 
  106 
  107 
  108 
  109