程序包 org.hipparchus.geometry.partitioning

类 BSPTree<S extends Space>

java.lang.Object
org.hipparchus.geometry.partitioning.BSPTree<S>
类型参数:
S - 空间的类型。
public class BSPTree<S extends Space> extends Object
该类表示二叉空间分区树。

BSP树是表示空间分区并将属性与每个单元格关联的有效方法。BSP树中的每个节点表示一个凸区域，该区域在切割超平面的两侧分为两个凸子区域。根树包含完整空间。

这种分区的主要用途是使用布尔属性来定义内部/外部属性，从而表示任意多边形（1D中的线段，2D中的多边形和3D中的多面体）并对其进行操作。

另一个例子是表示Voronoi镶嵌，其中每个单元格的属性保存单元格的定义点。

应用程序定义的属性在复制实例之间共享，并传播到分割部分。这些属性本身不会被BSP树算法使用，因此应用程序可以将它们用于任何目的。由于树访问方法以不同方式处理内部和叶节点，因此可以为内部节点属性和叶节点属性使用不同的类。但是，应谨慎使用，因为如果在设置属性后以任何方式修改树，则某些内部节点可能会变为叶节点，某些叶节点可能会变为内部节点。

开发此软件包的主要来源之一是Bruce Naylor，John Amanatides和William Thibault的论文合并BSP树产生多面体集合操作，发表于Siggraph '90，计算机图形学24（4），1990年8月，第115-124页，由计算机协会（ACM）出版。

  • 构造器详细资料

    • BSPTree

      public BSPTree()
      构建仅具有代表整个空间的一个根单元格的树。

    • BSPTree

      public BSPTree(Object attribute)
      构建仅具有代表整个空间的一个根单元格的树。
      参数:
      attribute - 树的属性（可以为null）

    • BSPTree

      public BSPTree(SubHyperplane<S> cut, BSPTree<S> plus, BSPTree<S> minus, Object attribute)
      从其基础元素构建BSPTree。

      此方法不对其参数的一致性执行任何验证，因此只有在调用者知道自己在做什么时才应使用它。

      此方法主要用于自底向上构建树。自顶向下构建树是通过方法insertCut实现的。

      参数:
      cut - 树的切割子超平面
      plus - 正侧子树
      minus - 负侧子树
      attribute - 与节点关联的属性（可以为null）
      另请参阅:

  • 方法详细资料

    • insertCut

      public boolean insertCut(Hyperplane<S> hyperplane)
      在节点中插入切割子超平面。

      从此节点开始的子树将被完全覆盖。新的切割子超平面将从提供的超平面与单元格的交点构建。如果超平面与单元格相交，则单元格将具有两个具有null属性的子单元格，分别位于插入的切割子超平面的两侧。如果超平面不与单元格相交，则不会插入任何切割超平面，并且单元格将更改为叶单元格。节点的属性永远不会更改。

      此方法主要在叶节点上调用时特别有用（即对于getCut返回null的节点），在这种情况下，它提供了一种自顶向下构建树的方法（而4个参数的构造函数专用于自底向上构建树）。

      参数:
      hyperplane - 要插入的超平面，它将被切割以适应由实例的父节点定义的单元格
      返回:
      如果已插入切割子超平面（即如果单元格现在具有两个叶子子节点）
      另请参阅:

    • copySelf

      public BSPTree<S> copySelf()
      复制实例。

      创建的实例与原始实例完全独立。使用深度复制，没有共享任何基础对象（除了节点属性和不可变对象）。

      返回:
      一个新的树，是实例的副本

    • getCut

      public SubHyperplane<S> getCut()
      获取切割子超平面。
      返回:
      切割子超平面，如果这是一个叶树则为null

    • getPlus

      public BSPTree<S> getPlus()
      获取切割超平面正侧的树。
      返回:
      切割超平面正侧的树，如果这是一个叶树则为null

    • getMinus

      public BSPTree<S> getMinus()
      获取切割超平面负侧的树。
      返回:
      切割超平面负侧的树，如果这是一个叶树则为null

    • getParent

      public BSPTree<S> getParent()
      获取父节点。
      返回:
      父节点，如果节点没有父节点则为null

    • setAttribute

      public void setAttribute(Object attribute)
      将属性与实例关联。
      参数:
      attribute - 要与节点关联的属性
      另请参阅:

    • getAttribute

      public Object getAttribute()
      获取与实例关联的属性。
      返回:
      与节点关联的属性，如果未使用setAttribute方法显式设置属性，则为null
      另请参阅:

    • visit

      public void visit(BSPTreeVisitor<S> visitor)
      访问BSP树节点。
      参数:
      visitor - 访问树节点的对象

    • getCell

      public BSPTree<S> getCell(Point<S> point, double tolerance)
      获取点所属的单元格。

      如果返回的单元格是叶节点，则点属于节点的内部，如果单元格是内部节点，则点属于节点切割子超平面。

      参数:
      point - 要检查的点
      tolerance - 在此值以下，被认为接近切割超平面的点被视为属于超平面本身
      返回:
      点所属的树单元格

    • getCloseCuts

      public List<BSPTree<S>> getCloseCuts(Point<S> point, double maxOffset)
      获取切割子超平面附近的单元格。
      参数:
      point - 要检查的点
      maxOffset - 在绝对值上，被认为切割子超平面接近点的偏移量下限
      返回:
      接近的单元格（如果所有切割子超平面距离点的距离大于maxOffset，则可能为空）

    • merge

      public BSPTree<S> merge(BSPTree<S> tree, BSPTree.LeafMerger<S> leafMerger)
      合并BSP树与实例。

      所有树都会被修改（其中的部分在新树中被重用），调用者有责任在此之前确保已经进行了复制，以便保留任何以前的树，这里不会进行任何复制！

      此处使用的算法直接源自Naylor、Amanatides和Thibault的论文中描述的算法（第III节，BSP树的二进制分割）。

      参数:
      tree - 与实例合并的其他树（操作后将无法使用，以及实例本身）
      leafMerger - 实现最终合并阶段的对象（这是操作语义发生的地方，通常取决于叶节点的属性）
      返回:
      一个新树，结果为instance <op> tree，如果parentTree不为null，则可以忽略此值，因为所有连接已经建立

    • split

      public BSPTree<S> split(SubHyperplane<S> sub)
      通过外部子超平面拆分BSP树。

      将树分为两半，位于子超平面的每一侧。实例不会被修改。

      返回的树不是向上一致的：尽管其所有子树都被切割为子超平面（包括其自身的切割子超平面）都被限制在当前单元中，但它尚未附加到任何父树。此树旨在稍后插入到更高级别的树中。

      此处使用的算法是Naylor、Amanatides和Thibault的论文中给出的算法（第III节，BSP树的二进制分割）。

      参数:
      sub - 分区子超平面，必须已经被剪切到实例表示的凸区域，将用作返回树的切割子超平面
      返回:
      一个树，其指定的子超平面为其切割子超平面，拆分实例的两部分为其两个子树，父节点为空

    • insertInTree

      public void insertInTree(BSPTree<S> parentTree, boolean isPlusChild, BSPTree.VanishingCutHandler<S> vanishingHandler)
      将实例插入另一个树中。

      实例本身被修改，因此其以前的父节点不应再使用。

      参数:
      parentTree - 要连接的父树（可以为null）
      isPlusChild - 如果为true且parentTree不为null，则结果树应为其父节点的正子树，如果parentTree为null则忽略
      vanishingHandler - 用于处理内部节点在合并过程中出现极少见消失切割子超平面的处理程序
      另请参阅:

    • pruneAroundConvexCell

      public BSPTree<S> pruneAroundConvexCell(Object cellAttribute, Object otherLeafsAttributes, Object internalAttributes)
      在单元周围修剪树。

      此方法可用于从树中提取凸单元。原始单元可以是叶节点或内部节点。如果是内部节点，则其子树将被忽略（即提取的单元在所有情况下都将是叶节点）。原始单元所属的原始树完全不受影响，将构建一个新的独立树。

      参数:
      cellAttribute - 为对应于初始实例单元的叶节点设置的属性
      otherLeafsAttributes - 为其他叶节点设置的属性
      internalAttributes - 为内部节点设置的属性
      返回:
      一个新树（原始树保持不变），包含一个单个分支，其中单元作为叶节点，其他叶节点作为修剪分支的残余部分