c# - 从顶点组合中找到最小的不规则多边形(性能关键)

Question

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

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

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

获取不规则多边形的表面积非常简单。我主要关心的是高效扫描所有可能组合的性能。

有关示例，请参见下图。所有三种类型都用于制作多边形，但圈出的一种具有最小的表面积，这是我的目标。

与我尝试制作的原型(prototype)相比，这个场景得到了简化。多边形将由数十个(如果不是数百个)顶点构成，并且网格将大得多。此外，这将是一个 24/7 全天候运行的过程。

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

Answer 1

这是一个基于分支定界的版本，有一些改进。

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

2) 在四叉树中找到具有每种类型节点之一的最低节点。这为您提供了一个起始解决方案，该解决方案至少应该足以加快其余搜索的速度。

3) 进行递归搜索，在我说猜测的地方采用所有可能的分支，在适用的情况下首先选择最有希望的候选者:

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

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

3z) 你有一组完整的顶点。

在每个步骤 3？您有一组部分顶点，我认为它为您提供了包括这些顶点在内的任何完整解决方案的区域的下限(它是顶点凸包内的区域吗？)。您可以丢弃任何已经至少与迄今为止最大的解决方案一样大的部分解决方案。如果您可以接受 X% 不准确的答案，则可以丢弃目前最大解决方案的 X% 范围内的任何部分解决方案。希望这会修剪您在 (3) 中导航的可能性树，使其足够易于处理。