一组点的多边形包围

Question

36

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

是否有已知算法来计算这个问题？（我在此领域缺乏文化知识...）

谢谢您的帮助

- Laurent K

你好，我需要在我的应用程序中实现相同的功能。你能分享算法给我吗？ - Ajay Gabani

我使用了QuickHull算法。参考资料在这里：https://en.wikipedia.org/wiki/Quickhull - Laurent K

4个回答

6

这里有一个简单的解决方案...

首先任意选择三个点来组成三角形。然后使用以下操作将每个额外的点添加到多边形中：

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

（注意：只要您的形状保持凸性，这两条路径就会是连续的并形成整个形状）

如果分离路径没有边缘，则该点位于多边形内部，应忽略它；否则，请从多边形中删除分离路径，并用两条线段替换它，将分离路径的每个端点连接到新点。

完成！ :)

- Evan Rogers

4

您可能是想要最小的区域，也就是凸包。

如果您真的只需要最少的点，您可以使用超大的三角形顶点位置将所有点围起来。

- SPWorley

8

你巨大三角形中的点P不会是S的子集，这是其中一个要求。 - Daniel Daranas

@DanielDaranas 如何获取这个超大三角形的顶点？ - Dinesh

凸包不是包含每个点的最小多边形。存在非凸多边形（比如星形），可以包含每个点但仍比凸包更小。它们的周长比凸包长，但面积更小。 - Eric Duminil

4

- Igor Brejc

URL不起作用 :-( 算法的名称应该足以找到解决方案。 - Skeeve

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- malach · Accepted Answer

这个问题有很多算法解决。它被称为"最小外接矩形算法"。你可以搜索"凸包"来找到其他解决方案，特别是在这里。

一种方法是找到最左边的点，然后重复查找一个点，使得所有其他点都在线段p(n-1)p(n)的右侧。