algorithm - 包含一组点的多边形

Question

我有一组点 S（2D：由 x 和 y 定义），我想找到 P，最小的（意思是：点数最少的）多边形包围该集合的所有点，P 是的有序子集S。

有没有已知的算法来计算这个？（我在这个领域缺乏文化令人惊讶......）

谢谢你的帮助

score 35 · Accepted Answer

这个问题有很多算法。它被称为“最小边界框”。您也会在搜索“凸包”时找到解决方案，尤其是在这里。

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

score 6 · Accepted Answer

这是一个简单的解决方案...

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

将边分成两条连续的路径，在一条路径中，每条边的线将要添加的点与多边形的其余部分分开（我们称之为“分离路径”），在另一条路径中，每条边的线点与多边形在同一侧。

（注意：只要你的形状保持凸出，它必须，这两条路径将是连续的并形成整个形状）

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

达达！:)

score 4 · Accepted Answer

您可能的意思是您想要最小的区域，即凸包。

如果你真的想要最少的点，你可以用超大的顶点位置制作一个三角形，这样你的所有点都被包围了。

score 4 · Accepted Answer

4 回答 4