从顶点组合中找到最小的不规则多边形（性能关键）。

Question

我需要在二维平面上的多个顶点中找到一个面积最小的不规则多边形。

这不是家庭作业。虽然我现在希望回到学校。

对于构建多边形有一些要求。假设我在8x8的网格上绘制了3种不同类型的顶点（红色，绿色，蓝色）。我需要扫描此网格中满足红、绿、蓝组合要求的所有顶点，并选择面积最小的顶点。

计算不规则多边形的表面积很简单，我主要关心的是高效地扫描所有可能的组合的性能。

请参见下面的图像示例。使用了三种类型来制作多边形，但是圈出来的那个具有最小的表面积，是我的目标。

与我尝试制作原型的情况相比，这种情况被简化了。这些多边形将由数十甚至数百个顶点构成，网格将更大。此外，这将是一个24/7运行的过程。

我想也许我应该按类型组织顶点并将它们分成单独的数组。然后以分层方式迭代这些数组，以计算所有组合的表面积。然而，此方法似乎是浪费的。

- Brian

Answer 1

这是一个基于分支定界的版本，带有一些华丽的修饰。

1) 将网格分解为四叉树，并根据需要在节点中进行注释。

2) 找到四叉树中具有每种类型节点的最低节点。这给您一个起始解决方案，应该足够好以加快其余搜索的速度。

3) 进行递归搜索，其中考虑所有可能的分支，选择可用时最有前途的候选项：

3a) 猜测最不常见类型的顶点。

3b) 使用四叉树中点的相对位置来排序猜测，猜测下一个最不常见类型的顶点，以便按距离从原点递增地猜测它们...

3z) 您拥有一个完整的顶点集。

在每个步骤3？处，您都有部分顶点集，我假设这给出了任何包括那些顶点的完整解的面积下限（它是顶点凸包内部的面积吗？）。您可以丢弃任何已经至少与迄今为止最大解一样大的部分解决方案。如果您可以接受X％不准确的答案，则可以丢弃任何部分解决方案，其与迄今为止最大解相差不到X％。希望这可以剪枝您正在导航的可能性树（3），使其易于处理。

- mcdowella

---

根据我对这个解决方案的理解，可能会漏掉一些组合的评估。在我的情况下这是不能接受的。 - Brian

如果您将X=0并且下限准确无误，那么您不应该错过最佳答案 - 这取决于您所指的区域是什么。仅当它们已经使用与迄今为止最佳解决方案一样多的面积时，才会丢弃部分解决方案。如果面积是凸包的面积，则从被丢弃的部分解中生成的任何完整解决方案都必须使用至少这么多的面积，因此不能比迄今为止找到的最佳解决方案更好。 - mcdowella

我实际上非常喜欢你的想法。 - Brian

Answer 2

如何选择具有最少顶点的颜色，并检查每个顶点的直接邻域，如果在该邻域内没有其他颜色，则增加模板尺寸（选择顶点周围的下一个环），然后再次检查。一直进行，直到至少一个顶点在当前模板中具有所有其他颜色。如果存在多个，则只需比较它们（简单的最小值约减）即可找到最小值。

- haraldkl

---

通过这种方式找到的组合可能不具有最小的平方。想象一下目标多边形是狭长的情况。 - Dmitry Ornatsky

@Dmitry，我的担忧也是这样。 - Brian

如果你在谈论封闭区域，是的。我以为你在寻找多边形的最小表面积（边缘之和）。 - haraldkl

Answer 3

以下是如何在O(n² log n)时间内找到最小的三角形。或许对你有用。

高层次的想法是使用旋转扫描线。我们始终保持沿着垂直于扫描线轴的蓝点的顺序，使用二叉搜索树。当扫描线与通过红绿对的线平行时，我们使用BST来查找最靠近红绿线的蓝点。

像往常一样，我们使用事件驱动的扫描线模拟。对于每个红绿对，为其角度制作一种事件。对于每对蓝点，为它们的相对顺序更改时制作另一种事件，数量为O(1)。对所有事件进行排序并启动程序。

- QWERTY

Answer 4

如果我们已经找到了一个区域A，我们可以缩小搜索范围。

三角形的面积是B*h（底乘高）。

如果你找到了两个点，那么B就是它们之间的距离。

然后我们可以搜索一个点，它距离该线最多为A/B（B*h < A => h < A/B）。这与在已有两个点的两条平行线之间搜索相同，这些平行线分别偏移A/B和-A/B。

这应该给出一个复杂度为O(n^2*k)，其中k是网格的宽度或高度。

如果您不提取坐标，则必须进行O(k^5)搜索，这至少比您之前必须执行的O(k^6)好。

更多分析：如果p是一个单元格包含顶点的概率，那么复杂度为：O(k^2p(k^2p(kp))) = O(k^5p^3)。 如果p=n/k^2，其中n是节点数，则得到O(n^3/k)。

- nulvinge