如何高效查找Vector2数组中的最外侧点以绘制点集外轮廓

你需要的是平面点集的凸包提取算法，以下是常用的高效实现方案：

核心算法推荐 #

你要找的最外侧点构成的封闭图形叫做凸包，下面两种是工业界最常用的高效实现，时间复杂度均为O(n log n)，完全满足普通图形渲染、游戏开发场景的性能需求：

1. Graham扫描法（中小点集首选，实现简单） #

执行步骤：

• 首先从所有点中筛选出y坐标最小的点，若存在多个y相同的点则取x最小的点，该点必然属于凸包，记为基准点P0
• 把剩余所有点按照和P0的极角从小到大排序，极角相同时距离P0更近的点排在前面
• 初始化一个栈结构，依次将P0、排序后的前两个点压入栈中
• 从排序后的第三个点开始遍历，每次判断栈顶两个点与当前遍历点形成的路径拐向：如果是顺时针拐（叉乘计算结果小于0），就弹出栈顶点，重复判断直到拐向为逆时针或栈内只剩2个点，再将当前点压入栈
• 遍历完所有点后，栈中留存的点就是所有外侧凸包点

2. Andrew单调链算法（大点集首选，性能更稳定） #

执行步骤：

• 将所有点按照x坐标排序，x相同的点按y坐标排序
• 构建下凸包：从左到右遍历排序后的点，每次判断当前点与栈末尾两个点的拐向，如果是顺时针拐就弹出栈顶点，否则将当前点加入栈
• 构建上凸包：从右到左遍历排序后的点，遵循同样的拐向判断规则弹出不符合的点，再将当前点加入栈
• 最终栈中会重复包含首尾两个点，去重后剩余的点即为凸包点

关键工具函数 #

判断拐向的核心逻辑依赖叉乘计算，以C#的Vector2为例，实现代码如下：

// 计算三点p0→p1→p2的叉乘
// 返回值>0：路径为逆时针拐；返回值<0：路径为顺时针拐；返回值=0：三点共线
float Cross(Vector2 p0, Vector2 p1, Vector2 p2)
{
    return (p1.X - p0.X) * (p2.Y - p0.Y) - (p1.Y - p0.Y) * (p2.X - p0.X);
}

注意事项 #

如果需要保留凸包边上的所有共线外侧点，把拐向判断的小于0条件改为小于等于0即可；如果只需要保留凸包的顶点，使用原小于0的判断即可。

内容的提问来源于stack exchange，提问作者Lachlan