如何将几何体分成块？
lve*_*lla 8 algorithm partitioning computational-geometry
我确信已经有一些算法可以满足我的需求,但我不确定谷歌会使用什么词组,或者算法类别是什么.
这是我的问题:我有一个由多个接触块(hyperslabs)组成的多面体,即边缘是轴对齐的,边缘之间的角度是90°.多面体内可能有孔.
我想把这个凹面多面体分解成一个小的凸矩形轴对齐的整块是可能的(如果原始的多面体是凸的并且没有孔,那么它已经是这样的块,因此,解决方案).为了说明,我制作了一些二维图像(但我需要3-D的解决方案,最好是ND):
我有这个几何:
一个可能分解成块的是:
但我想要的是这个(尽可能少的块):
我的印象是一个精确的算法可能太昂贵了(这个问题是NP难吗？),所以近似算法是合适的.
一个细节可能会使问题更容易,因此可能有一个更合适/专业的算法是所有边都有一些固定值的大小倍数(你可能认为所有边大小都是整数,或几何是由均匀的小方块或体素组成).
背景:这是PDE域的结构化网格离散化.
什么算法可以解决这个问题？我应该搜索哪种算法？