论文标题
隐式定义域的连接组件标记算法
A Connected Component Labeling Algorithm for Implicitly-Defined Domains
论文作者
论文摘要
为由多元多项式指定的隐式定义的域开发了连接的组件标记算法。该算法是通过将约束域递归细分为超偏角子细胞的，直到其拓扑非常简单为止。特别是，我们使用伯恩斯坦多项式的特性设计了拓扑测试。在许多情况下，该算法会产生保证其正确性的证书，即，仅当它们与路径连接时，两个点会产生相同的标签。为了稳健地处理各种边缘情况，该算法可能会将相同的标签分配给不同的组件，但只有在它们完全或接近触摸的情况下，相对于用户控制的长度比例。各种数值实验评估了整体方法的有效性，包括对2D和3D中随机生成的多组分几何形状的统计分析，以及涉及尖牙，自身切断，交界处和其他类型的奇异性的特定示例。
A connected component labeling algorithm is developed for implicitly-defined domains specified by multivariate polynomials. The algorithm operates by recursively subdividing the constraint domain into hyperrectangular subcells until the topology thereon is sufficiently simple; in particular, we devise a topology test using properties of Bernstein polynomials. In many cases the algorithm produces a certificate guaranteeing its correctness, i.e., two points yield the same label if and only if they are path-connected. To robustly handle various kinds of edge cases, the algorithm may assign identical labels to distinct components, but only when they are exactly or nearly touching, relative to a user-controlled length scale. A variety of numerical experiments assess the effectiveness of the overall approach, including statistical analyses on randomly generated multi-component geometry in 2D and 3D, as well as specific examples involving cusps, self-intersections, junctions, and other kinds of singularities.
