从顶点组合中查找最小的不规则多边形(性能严重)
use*_*uld 15 c# algorithm math data-structures
我需要在2D平面上的几个顶点找到一个具有最小表面积的不规则多边形.
不,这不是功课.虽然我希望我现在回到学校.
关于如何构造多边形有一些要求.假设我在8x8网格上绘制了3种不同类型的顶点(红色,绿色,蓝色).我需要扫描此网格中满足红色,绿色,蓝色组合要求的所有顶点,并选择具有最小表面积的顶点.
获得不规则多边形的表面区域非常简单.我主要关心的是有效扫描所有可能组合的性能.
有关示例,请参见下图.所有三种类型都用于制作多边形,但是圈出的多边形具有最小的表面积并且是我的目标.
与我正在尝试原型相比,这种情况得到了简化.多边形将由数十个甚至数百个顶点构成,并且网格将更大.此外,这将是一个全天候运行的过程.
我想也许我应该按类型组织顶点并将它们分成单个数组.然后以分层方式迭代数组以计算所有组合的表面积.然而,这种方法似乎很浪费.
这是一个基于分支和界限的版本,有一些繁荣.
1)将网格分解为四叉树,其余部分根据需要在节点中添加注释.
2)找到四叉树中具有每种节点类型之一的最低节点.这为您提供了一个起始解决方案,该解决方案应该至少足以加快搜索的其余部分.
3)做一个递归搜索,它采用我猜的所有可能的分支,在适用的情况下首先选择最有希望的候选者:
3a)猜测最不常见类型的顶点.
3b)使用四叉树中点的相对位置来对您的猜测进行排序,猜测下一个最常见类型的顶点,以便从原点开始以距离递增的顺序猜测它们......
3z)你有一套完整的顶点.
在每一步3？你有一个部分顶点集合,我认为它给你一个完整解决方案区域的下界,包括那些顶点(它是顶点凸包内的区域？).您可以丢弃迄今为止已经至少与最大解决方案一样大的任何部分解决方案.如果您可以使用X%不准确的答案,则可以丢弃目前为止最大解决方案的X%范围内的任何部分解决方案.希望这可以修剪你正在导航的可能性树(3),使其易于处理.