假设我有一个由一组组成的网格填充该区域的保形元素. 假设我也有一个 2D 形状 谁的边界是分段线性的，但不一定是凸的，也不一定是简单连接的。在不对网格中元素的特定形状做出任何假设的情况下，如何有效地确定其并集包含所有形状的最小元素集?
虽然我的问题是在 2D 中提出的，但我对一种也可以扩展到 3D 的方法感兴趣。
如何找到覆盖给定形状的最小元素集？
计算科学
计算几何
2021-12-20 10:24:34
2个回答
如果您不想采用简单的凸包（导致高估且不仅仅是由元素组成），这里有一个算法，也许可以解决您的问题的一个专门版本：
- 找到所有简单连通的组件（例如使用联合查找算法）。
- 对于每个组件，找到alpha 形状。
自然延伸到 3D。还没有证明它是否是最小的。
我们首先还假设您有某种方法来验证一个点是否在形状内. 鉴于您已经实现，可以使用某个给定元素的顶点来检查它是否在形状内.
下一步将是找到一个确实位于其中的元素，这可以通过找到一个包含/共享用于创建分段形状的顶点之一的元素来完成. 这可以使用 KD 树、空间哈希表或类似的数据结构来有效地完成。
找到形状内的单个元素后，然后您可以使用基于相邻元素及其顶点的广度/深度优先搜索来查找其中的元素.
其它你可能感兴趣的问题