587 安装栅栏（计算几何-凸包）

快来打我* 2022-08-31 14:29 222阅读 0赞

**1. 问题描述：**

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

**示例 1:**

输入: \[\[1,1\],\[2,2\],\[2,0\],\[2,4\],\[3,3\],\[4,2\]\]  
输出: \[\[1,1\],\[2,0\],\[4,2\],\[3,3\],\[2,4\]\]  
解释:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**示例 2:**

输入: \[\[1,2\],\[2,2\],\[4,2\]\]  
输出: \[\[1,2\],\[2,2\],\[4,2\]\]  
解释:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1][]

即使树都在一条直线上，你也需要先用绳子包围它们。

**注意:**

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。输入的整数在 0 到 100 之间。花园至少有一棵树。所有树的坐标都是不同的。输入的点没有顺序。输出顺序也没有要求。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/erect-the-fence

**2. 思路分析：**

这道题目属于计算几何中凸包的裸题，求解凸包一般有两种常见的算法，分别为**Graham算法**和**Andrew算法**，这两种算法都是类似的，下面采用的是Graham算法求解凸包，首先计算凸包需要一个前置知识：两个向量的外积（二维平面中的叉积），外积属于一个向量，二维平面的叉积|a||b|sinθ的数值表示两个向量围成的三角形面积的一半，也等于平行四边形的面积，并且在二维平面中可以使用坐标来表示一个向量，所以二维平面的叉积又可以表示为x1 \* y2 - x2 \* y1

![20210726103814879.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 2][]

利用二维平面的叉积坐标表示我们就可以通过两个向量的坐标运算结果判断出两个向量的相对位置，也即一个向量是另外一个的顺时钟方向还是逆时钟方向，判断是顺时钟方向还是逆时钟方向我们可以通过举出例子来判断（不用额外记住）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 3][]

有了上面的二维平面坐标的叉积我们就可以正式开始Graham算法了，Graham算法主要分为两个步骤：

*  将所有点按照双关键字排序，首先对横坐标排序，横坐标相同那么纵坐标的小的排在前面
 *  通过两遍扫描二维平面上的点，第一遍求解出凸包的上半部分，第二遍逆序扫描求解凸包的下半部分，这样通过两遍扫描就可以求解出凸包中的所有点

其中在扫描的时候我们需要借助于一个栈，python可以使用list实现，c++可以使用vector实现，当栈中大于等于两个元素时，也即开始遍历第三个点以及第三个点之后的点的时候就需要判断栈顶的两个点以及当前遍历的点构成的向量的相对位置，也即是顺时钟位置还是逆时钟位置，下面的图比较直观显示了这个过程，当我们发现向量ac位于向量ab的逆时钟位置的时候说明栈顶的点就需要删除，注意这是一个迭代删除点的过程（当前向量位于逆时钟的位置，因为可能栈中的多个点需要删除，直到不能删为止），当前向量位于顺时钟方向说明需要保留栈中的点，并且将当前遍历的点加入到凸包中，这样当我们扫描一遍点的时候就可以求解出凸包中的上半部分的点，需要注意当我们将点加入凸包之后那么需要将当前的点标记为已访问，然后我们需要逆序扫描第二遍对剩余之前没有标记过的点进行遍历，也是类似于正序遍历的过程，顺时钟方向则保留，逆时钟方向则需要删除栈顶元素。这里需要注意的一点是对于0这个需要加入两次到凸包中这样结果才是正确的，最后将多余0那个点删掉即可，画一下图其实很好理解的，核心是判断两个向量的相对位置

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 4][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 计算两个向量的外积
        def cross(self, x1: int, y1: int, x2: int, y2: int):
            return x1 * y2 - x2 * y1
        
        # 求解当前点与栈中两个构成的向量向量是逆时针方向还是顺时钟方向
        def area(self, a: List[int], b: List[int], c: List[int]):
            return self.cross(b[0] - a[0], b[1] - a[1], c[0] - a[0], c[1] - a[1])
    
        def outerTrees(self, points: List[List[int]]) -> List[List[int]]:
            # 双关键字排序
            points.sort(key=lambda x:(x[0], x[1]))
            n = len(points)
            used = [0] * n
            # 凸包的下标是从1开始的
            hull = [0] * (n + 2)
            top = 0
            # 从前往后扫描一遍凸包
            for i in range(n):
                while top >= 2 and self.area(points[hull[top - 1]], points[hull[top]], points[i]) > 0:
                    used[hull [top]] = 0
                    top -= 1
                top += 1
                used[i] = 1
                hull [top] = i
            # 注意一定要将0加入两遍, 例如：[[0,0],[0,100],[100,100],[100,0],[50,50]]就是要加入0这个点两次
            # 将0置为未被访问这样才可以加入这个点两次
            used[0] = 0
            # 逆序遍历一下点求解凸包的下半部分
            for i in range(n - 1, -1, -1):
                # 当前的点之前已经访问那么跳过即可
                if used[i] == 1: continue
                while top >= 2 and self.area(points[hull[top - 1]], points[hull[top]], points[i]) > 0:
                    top -= 1
                top += 1
                hull [top] = i
            # 0加入两次那么需要减1
            top -= 1
            res = list()
            # 将凸包的点加入的到答案中
            for i in range(1, top + 1):
                res.append(points[hull[i]])
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/4fcbc1af07b84ad88862459831069ba5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1]: /images/20220829/67abebcc29454ac691b50129c39be833.png
[20210726103814879.png]: /images/20220829/b45389aa3461484db86d8069ad649795.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 2]: /images/20220829/7d2385fe6de74adf965d4f4204e99b7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 3]: /images/20220829/e527d75a9a324514a6ebc4635d461bbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 4]: /images/20220829/19be85637f0d430b8660e651398e08e7.png