程序包 org.hipparchus.geometry.partitioning

package org.hipparchus.geometry.partitioning
该程序包提供了实现二进制空间分区树的类。

BSP树是表示空间部分的有效方式，特别是多面体（1D中的线段，2D中的多边形和3D中的多面体）以及对它们进行操作。主要原则是使用简单的超平面（1D中的点，2D中的线，3D中的平面）递归地对空间进行细分。

我们从一个由单个节点组成且没有任何切割超平面的树开始：它表示完整空间，这是一个凸部分。如果我们向此节点添加一个切割超平面，这表示具有超平面在节点级别的划分，并且在切割超平面的两侧有两个半空间。这些半空间由两个子节点表示，这两个子节点没有关联的切割超平面，正子节点表示切割超平面正侧的半空间，负子节点表示另一侧。继续细分，我们最终得到一个树，其中内部节点与切割超平面关联，没有任何超平面的叶节点对应于凸部分。

当使用BSP树表示多面体时，已知凸部分完全在多面体内部或外部，只要该部分中没有面（如果切割超平面已选择为面的基础超平面（这称为自动划分），并且如果继续细分过程直到所有面都已处理。重要的是要注意，多面体不是由单个部分定义的，而是由多个凸部分定义。这是允许BSP树表示非凸多面体的属性，尽管所有部分都是凸的。 Region 类致力于此表示，它是在 BSPTree 类的基础上构建的，使用布尔对象作为叶节点属性来表示每个叶部分的内部/外部属性，并且还添加了处理边界的各种方法（即内部和外部部分之间的分隔）。

与其简单地将内部节点与超平面关联起来，我们考虑与父节点定义的凸部分内部相对应的子超平面，这意味着根节点处的子超平面实际上是完整超平面，因为没有父节点来限制它。由于部分是凸的，子超平面也是凸的，在3D中，凸部分是凸多面体，子超平面是凸多边形，这些多边形将这些多面体切割成两个子多面体。使用此定义，BSP树完全对空间进行划分。每个点要么属于内部节点中的一个子超平面，要么属于一个叶凸部分。

为了确定点的位置，只需检查其相对于根切割超平面的位置，选择相应的子树，并递归地重复该过程，直到点出现在树中间的超平面上或出现在一个叶部分中。对于此操作，只需考虑完整超平面，无需检查点与子超平面的边界，因为实际上已通过树中的递归下降来实现此检查。这样做非常简单且非常高效，特别是如果树平衡良好（成本为O(log(n))，其中n是面数）或者如果靠近根部的前几层可以区分总空间的大部分。

开发此程序包的主要来源之一是Bruce Naylor、John Amanatides和William Thibault的论文 Merging BSP Trees Yields Polyhedral Set Operations Proc. Siggraph '90, Computer Graphics 24(4), August 1990, pp 115-124，由计算机协会（ACM）出版。同一篇论文也可以在 这里 找到。

请注意，此程序包中定义的接口不打算由Hipparchus用户实现，它们仅打算在库内部实现。即使是对于次要版本，也可能添加新方法，这会破坏外部实现的兼容性。