包含一组点的多边形

对于这个问题有很多算法。它被称为“ minimum bounding box convex hull “尤其是 here .

一种方法是找到最左边的点,然后重复搜索所有其他点都位于线p(n-1)p(n)右侧的点。

从任意三个点开始形成三角形。使用以下操作将每个附加点添加到多边形:

将边划分为两条连续路径,其中在一条路径中,每条边的直线将要添加的点与多边形的其余部分分离(我们称之为“分离路径”),在另一条路径中,每条边的直线的点位于多边形的同一侧。

如果分离路径没有边,则该点位于多边形内部,应忽略该点,否则,请从多边形中删除分离路径。将其替换为两段,将分离路径的每个端点连接到新点。

塔达!:)

要点 ,您可以创建一个具有超大顶点位置的三角形,以便将所有点都封闭起来。

The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)