如何在二维整数网格中查找凸包边界上的点

现有代码的错误点 #

• 遍历了所有凸包顶点组合，没有限制为相邻顶点：非相邻凸包顶点的连线是凸包内部的弦，线上的点属于内部点，不属于边界
• 只有共线判断，没有验证点是否落在两个顶点的线段范围内：共线的点可能在线段的延长线上，不属于凸包边界
• 逻辑参数写反：collinear函数内错误判断是否要把凸包顶点q加入数组，你需要筛选的是传入的points数组中的点，而非凸包顶点

正确实现逻辑 #

凸包的边界就是所有相邻顶点连接成的闭合线段集合，只需要筛选出落在这些线段上的点即可：

1. 确保你的hull数组是按顺时针/逆时针顺序存储的凸包顶点（所有常规凸包算法的输出默认都是有序的）
2. 遍历每一对相邻凸包顶点，最后一个顶点和第一个顶点配对，形成闭合边界
3. 对每对相邻顶点，遍历所有待检查的点，同时满足「和两个顶点共线」、「坐标落在两个顶点的线段范围内」两个条件的，就是边界点
4. 对结果去重，避免相邻边的公共顶点被重复统计

修正后的代码 #

// 计算三点叉乘，返回值为0代表三点共线
function cross(p, q, r) {
  return p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y);
}

// 判断点r是否落在p、q组成的线段范围内
function isOnSegment(p, q, r) {
  return (r.x >= Math.min(p.x, q.x) && r.x <= Math.max(p.x, q.x))
      && (r.y >= Math.min(p.y, q.y) && r.y <= Math.max(p.y, q.y));
}

// 初始化边界点数组，凸包顶点本身就是边界点
const boundaryPoints = [...hull];
const hullLength = hull.length;

for (let i = 0; i < hullLength; i++) {
  const p = hull[i];
  // 取相邻顶点，最后一个顶点的下一个是第一个顶点，形成闭合边
  const q = hull[(i + 1) % hullLength];
  for (const r of points) {
    // 跳过已经加入边界数组的点，避免重复
    if (boundaryPoints.some(item => item.x === r.x && item.y === r.y)) continue;
    // 同时满足共线、在线段上两个条件，即为边界点
    if (cross(p, q, r) === 0 && isOnSegment(p, q, r)) {
      boundaryPoints.push(r);
    }
  }
}

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