1. 问题背景与需求分析LeetCode 587题安装栅栏是一个经典的计算几何问题要求我们找到一组二维平面点的最小凸包。这个问题在实际中有很多应用场景比如农场主需要围住所有树木的最小围栏长度军事上部署雷达站的最小覆盖范围城市规划中确定建筑群的外边界给定一组树的坐标trees[i] [xi, yi]我们需要返回构成凸包的树的位置。凸包的定义是包含所有点的最小凸多边形其中凸多边形是指多边形内部任意两点连线都在多边形内部。2. 凸包算法选型与比较解决凸包问题有几种常见算法我们需要先了解它们的优缺点2.1 Graham扫描法时间复杂度O(nlogn)需要先找到一个基点然后按极角排序最后用栈维护凸包。优点是效率高但实现相对复杂。2.2 Jarvis步进法礼品包装算法时间复杂度O(nh)其中h是凸包上的点数。从最左边的点开始逐步包裹所有点。实现简单但最坏情况下效率低。2.3 Andrew算法这是本问题推荐的方法可以看作是Graham扫描的改进版将所有点按x坐标排序x相同则按y分别构建下凸包和上凸包合并两部分得到完整凸包时间复杂度O(nlogn)实现相对简单且效率稳定。3. Andrew算法实现详解以下是使用Andrew算法解决该问题的Java实现public int[][] outerTrees(int[][] trees) { if (trees.length 3) return trees; // 按x升序排序x相同则按y升序 Arrays.sort(trees, (a, b) - { if (a[0] b[0]) return a[1] - b[1]; return a[0] - b[0]; }); Listint[] hull new ArrayList(); // 构建下凸包 for (int[] tree : trees) { while (hull.size() 2 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), tree) 0) { hull.remove(hull.size()-1); } hull.add(tree); } // 构建上凸包 for (int i trees.length-1; i 0; i--) { while (hull.size() 2 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), trees[i]) 0) { hull.remove(hull.size()-1); } hull.add(trees[i]); } // 去除重复点 HashSetint[] set new HashSet(hull); return set.toArray(new int[set.size()][]); } // 计算向量叉积 private int cross(int[] a, int[] b, int[] c) { return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0]); }4. 关键代码解析4.1 叉积计算cross函数计算的是向量ab和向量bc的叉积结果0点c在向量ab的左侧结果0点c在向量ab的右侧结果0三点共线这是判断点是否在凸包上的核心数学工具。4.2 凸包构建过程下凸包构建时我们从左向右处理点每次尝试将当前点加入凸包如果新点导致凸包凹陷叉积0就移除前一个点直到满足凸性条件上凸包构建同理只是从右向左处理。4.3 边界情况处理点数≤3时直接返回因为3个点必然形成凸包最后使用HashSet去重因为起点会被两次加入5. 测试用例与验证验证算法正确性需要设计多种测试场景// 常规情况 int[][] test1 {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}}; // 所有点共线 int[][] test2 {{1,1},{2,2},{3,3},{4,4}}; // 矩形分布 int[][] test3 {{0,0},{0,4},{4,0},{4,4},{2,2}}; // 重复点 int[][] test4 {{1,1},{1,1},{1,1}};对于共线点的情况Andrew算法会将它们全部包含在凸包中这是题目要求的。实际应用中可能需要根据需求调整。6. 算法优化与变种6.1 处理共线点如果希望凸包只包含端点可以修改判断条件// 将 0 改为 0 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), tree) 06.2 性能优化对于大规模数据使用快速排序替代Arrays.sort预分配List大小减少扩容开销对于已知分布的数据可以采用分治策略6.3 三维凸包扩展虽然本题是二维的但算法可以扩展到三维空间使用类似的思想处理面而不是边。7. 实际应用中的注意事项浮点精度问题实际工程中坐标可能是浮点数直接使用叉积判断时要注意精度误差可以设置一个很小的epsilon值。退化情况所有点共线或重合时要有特殊处理避免算法陷入死循环。内存管理对于极大点数要注意Java的自动装箱和GC影响可以考虑使用原生数组。并行化可能排序阶段和上下凸包构建可以并行处理但要注意线程安全。我在实际项目中遇到过一个问题当点数超过10万时默认的排序方法会成为瓶颈。解决方案是改用基于基数排序的方法将时间复杂度从O(nlogn)降到O(n)。 
长河君 · 2026/11/2 7:20:15 · 阅读 1.2k LeetCode 587题解析：Andrew算法实现二维凸包计算
1. 问题背景与需求分析LeetCode 587题安装栅栏是一个经典的计算几何问题要求我们找到一组二维平面点的最小凸包。这个问题在实际中有很多应用场景比如农场主需要围住所有树木的最小围栏长度军事上部署雷达站的最小覆盖范围城市规划中确定建筑群的外边界给定一组树的坐标trees[i] [xi, yi]我们需要返回构成凸包的树的位置。凸包的定义是包含所有点的最小凸多边形其中凸多边形是指多边形内部任意两点连线都在多边形内部。2. 凸包算法选型与比较解决凸包问题有几种常见算法我们需要先了解它们的优缺点2.1 Graham扫描法时间复杂度O(nlogn)需要先找到一个基点然后按极角排序最后用栈维护凸包。优点是效率高但实现相对复杂。2.2 Jarvis步进法礼品包装算法时间复杂度O(nh)其中h是凸包上的点数。从最左边的点开始逐步包裹所有点。实现简单但最坏情况下效率低。2.3 Andrew算法这是本问题推荐的方法可以看作是Graham扫描的改进版将所有点按x坐标排序x相同则按y分别构建下凸包和上凸包合并两部分得到完整凸包时间复杂度O(nlogn)实现相对简单且效率稳定。3. Andrew算法实现详解以下是使用Andrew算法解决该问题的Java实现public int[][] outerTrees(int[][] trees) { if (trees.length 3) return trees; // 按x升序排序x相同则按y升序 Arrays.sort(trees, (a, b) - { if (a[0] b[0]) return a[1] - b[1]; return a[0] - b[0]; }); Listint[] hull new ArrayList(); // 构建下凸包 for (int[] tree : trees) { while (hull.size() 2 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), tree) 0) { hull.remove(hull.size()-1); } hull.add(tree); } // 构建上凸包 for (int i trees.length-1; i 0; i--) { while (hull.size() 2 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), trees[i]) 0) { hull.remove(hull.size()-1); } hull.add(trees[i]); } // 去除重复点 HashSetint[] set new HashSet(hull); return set.toArray(new int[set.size()][]); } // 计算向量叉积 private int cross(int[] a, int[] b, int[] c) { return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0]); }4. 关键代码解析4.1 叉积计算cross函数计算的是向量ab和向量bc的叉积结果0点c在向量ab的左侧结果0点c在向量ab的右侧结果0三点共线这是判断点是否在凸包上的核心数学工具。4.2 凸包构建过程下凸包构建时我们从左向右处理点每次尝试将当前点加入凸包如果新点导致凸包凹陷叉积0就移除前一个点直到满足凸性条件上凸包构建同理只是从右向左处理。4.3 边界情况处理点数≤3时直接返回因为3个点必然形成凸包最后使用HashSet去重因为起点会被两次加入5. 测试用例与验证验证算法正确性需要设计多种测试场景// 常规情况 int[][] test1 {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}}; // 所有点共线 int[][] test2 {{1,1},{2,2},{3,3},{4,4}}; // 矩形分布 int[][] test3 {{0,0},{0,4},{4,0},{4,4},{2,2}}; // 重复点 int[][] test4 {{1,1},{1,1},{1,1}};对于共线点的情况Andrew算法会将它们全部包含在凸包中这是题目要求的。实际应用中可能需要根据需求调整。6. 算法优化与变种6.1 处理共线点如果希望凸包只包含端点可以修改判断条件// 将 0 改为 0 cross(hull.get(hull.size()-2), hull.get(hull.size()-1), tree) 06.2 性能优化对于大规模数据使用快速排序替代Arrays.sort预分配List大小减少扩容开销对于已知分布的数据可以采用分治策略6.3 三维凸包扩展虽然本题是二维的但算法可以扩展到三维空间使用类似的思想处理面而不是边。7. 实际应用中的注意事项浮点精度问题实际工程中坐标可能是浮点数直接使用叉积判断时要注意精度误差可以设置一个很小的epsilon值。退化情况所有点共线或重合时要有特殊处理避免算法陷入死循环。内存管理对于极大点数要注意Java的自动装箱和GC影响可以考虑使用原生数组。并行化可能排序阶段和上下凸包构建可以并行处理但要注意线程安全。我在实际项目中遇到过一个问题当点数超过10万时默认的排序方法会成为瓶颈。解决方案是改用基于基数排序的方法将时间复杂度从O(nlogn)降到O(n)。