如何自动寻找2D点云或凸集的边界点（非仅顶点）

核心思路 #

要提取凸包上的所有点（包括顶点间线段上的点），分两步执行：

1. 先用标准凸包算法算出凸包的顶点集合（这一步你已经尝试过）
2. 遍历凸包的每条闭合边（相邻顶点构成的线段，包含最后一个顶点与第一个顶点的连线），筛选出所有位于该线段上的输入点

点在线段上的判断逻辑 #

对于线段端点p1=(x1,y1)、p2=(x2,y2)，以及待判断点p=(x,y)，同时满足以下两个条件即可判定p在该线段上：

• 叉乘为0：(x - x1)*(y2 - y1) == (y - y1)*(x2 - x1)（确保三点共线）
• 坐标区间约束：min(x1,x2) ≤ x ≤ max(x1,x2) 且 min(y1,y2) ≤ y ≤ max(y1,y2)（确保点在线段范围内，而非直线延长线上）

Python工具包实现示例 #

用scipy计算凸包顶点，结合numpy做批量点判断：

import numpy as np
from scipy.spatial import ConvexHull

def is_point_on_segment(p, p1, p2):
    # 叉乘判断共线（加入微小误差容忍）
    cross = (p[0] - p1[0]) * (p2[1] - p1[1]) - (p[1] - p1[1]) * (p2[0] - p1[0])
    if not np.isclose(cross, 0, atol=1e-8):
        return False
    # 坐标区间判断（加入微小误差容忍）
    x_in = min(p1[0], p2[0]) - 1e-8 <= p[0] <= max(p1[0], p2[0]) + 1e-8
    y_in = min(p1[1], p2[1]) - 1e-8 <= p[1] <= max(p1[1], p2[1]) + 1e-8
    return x_in and y_in

# 替换成你的[1000,2]点云数据
points = np.random.rand(1000, 2)

# 步骤1：计算凸包顶点
hull = ConvexHull(points)
hull_vertices = points[hull.vertices]

# 步骤2：筛选所有凸包边界点
boundary_points = []
n_hull_vertices = len(hull_vertices)
for i in range(n_hull_vertices):
    p1 = hull_vertices[i]
    p2 = hull_vertices[(i+1)%n_hull_vertices]
    # 批量判断所有点是否在当前线段上
    mask = np.apply_along_axis(is_point_on_segment, 1, points, p1, p2)
    boundary_points.extend(points[mask])

# 去重（避免同一点被多条边重复选中）
boundary_points = np.unique(boundary_points, axis=0)
print(f"找到 {len(boundary_points)} 个凸包边界点")

其他可选工具包 #

• OpenCV：用cv2.convexHull获取凸包顶点后，套用相同的线段点筛选逻辑
• Shapely：将凸包转为LineString对象，通过point.within(line)判断点是否在凸包边上（适合侧重几何对象操作的场景）

内容的提问来源于stack exchange，提问作者Amirul Islam Saimon