2

有一个具有 n 个顶点的简单多边形 P1,n 很小,比如说 8。这个多边形应该代表一些 2D 点集的周长。

接下来,我们有另一个多边形,我们称之为 P2,也有最大顶点数 n。P2 靠近 P1,因此绘制一个新的多边形 P3 是有意义的,它将一起描述 P1 和 P2 的区域。

我正在寻找算法来选择新多边形 P3 的点。我想尽可能好地描述(仍然有 n 个点!)P1 + P2 的形状:用于创建多边形且仍在新多边形 P3 内的点的数量应最大化,但面积P3 尽可能小。

扩展多边形的过程将在我的应用程序中反复调用。

4

2 回答 2

2

如果我正确阅读了这个问题,那是不可能的。考虑一个“半圆”,由沿曲线的 N 个点定义,而在直边上没有一个点。让 P1 和 P2 是两个这样的半圆,它们的直边像这样相互面对:(||)。显然,包含它们的唯一多边形由所有 2N 个点组成。

更简单的问题(引入一个新顶点并选择一个旧顶点驱逐)也是不可能的:考虑一个三角形和一个靠近边缘中间的新点。

如果我们放弃内部不能丢失的要求,那么问题可以解决,但并不完美。我建议您尝试其中的一些,看看您最适合哪种套房。

  • 只需将 P1 和 P2 组合成一个 2N 多边形,然后消除所有其他顶点(dh 保留顶点 2、4、6...)。粗制滥造,但也许足够好。
  • 将两个最近的邻居合二为一。重复直到你只剩下N。
  • 消除“最直”的顶点,直到只剩下 N 个。
  • 从 2N 多边形开始,然后通过取其两条边的叉积来测量每个顶点对区域的贡献。如果是正数,这个顶点是凸的并且“保护”了大部分内部。如果为负,这是一个“排除”大部分外部的凹顶点。现在消除最不有价值的顶点。请注意,这不是一个完美的方法,因为消除两个邻居会造成比分数显示的更大的伤害。
于 2009-09-10T00:06:16.053 回答
1

听起来您正试图找到一组具有可接受的点密度的多边形。您是否考虑过构建一系列凸包?向外扩展您的集合,每次添加一个点时构建新的凸包。求新船体的密度。如果不可接受,请删除该点并选择其他点。当您到达目标区域或总点数时停止。

这也可以反过来应用。您可以使用初始多边形 P1 和 P2 播种凸包,然后考虑丢弃单个点并计算新密度。最有用的去除点是使密度增加最大化的点。重复直到满意。

Simple O(n logn) convex hull algorithms exist for two dimensions. Qhull is a nice C implementation.

于 2009-09-10T13:20:15.007 回答