BSPTree.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      https://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */

  18. /*
  19.  * This is not the original file distributed by the Apache Software Foundation
  20.  * It has been modified by the Hipparchus project
  21.  */
  22. package org.hipparchus.geometry.partitioning;

  24. import java.util.ArrayList;
  25. import java.util.List;

  27. import org.hipparchus.exception.MathRuntimeException;
  28. import org.hipparchus.geometry.Geometry;
  29. import org.hipparchus.geometry.Point;
  30. import org.hipparchus.geometry.Space;
  31. import org.hipparchus.util.FastMath;

  33. /** This class represent a Binary Space Partition tree.

  35.  * <p>BSP trees are an efficient way to represent space partitions and
  36.  * to associate attributes with each cell. Each node in a BSP tree
  37.  * represents a convex region which is partitioned in two convex
  38.  * sub-regions at each side of a cut hyperplane. The root tree
  39.  * contains the complete space.</p>

  41.  * <p>The main use of such partitions is to use a boolean attribute to
  42.  * define an inside/outside property, hence representing arbitrary
  43.  * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
  44.  * 3D) and to operate on them.</p>

  46.  * <p>Another example would be to represent Voronoi tesselations, the
  47.  * attribute of each cell holding the defining point of the cell.</p>

  49.  * <p>The application-defined attributes are shared among copied
  50.  * instances and propagated to split parts. These attributes are not
  51.  * used by the BSP-tree algorithms themselves, so the application can
  52.  * use them for any purpose. Since the tree visiting method holds
  53.  * internal and leaf nodes differently, it is possible to use
  54.  * different classes for internal nodes attributes and leaf nodes
  55.  * attributes. This should be used with care, though, because if the
  56.  * tree is modified in any way after attributes have been set, some
  57.  * internal nodes may become leaf nodes and some leaf nodes may become
  58.  * internal nodes.</p>

  60.  * <p>One of the main sources for the development of this package was
  61.  * Bruce Naylor, John Amanatides and William Thibault paper <a
  62.  * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
  63.  * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
  64.  * Computer Graphics 24(4), August 1990, pp 115-124, published by the
  65.  * Association for Computing Machinery (ACM).</p>

  67.  * @param <S> Type of the space.
  68.  * @param <P> Type of the points in space.
  69.  * @param <H> Type of the hyperplane.
  70.  * @param <I> Type of the sub-hyperplane.

  72.  */
  73. public class BSPTree<S extends Space,
  74.                      P extends Point<S, P>,
  75.                      H extends Hyperplane<S, P, H, I>,
  76.                      I extends SubHyperplane<S, P, H, I>> {

  78.     /** Cut sub-hyperplane. */
  79.     private I cut;

  81.     /** Tree at the plus side of the cut hyperplane. */
  82.     private BSPTree<S, P, H, I> plus;

  84.     /** Tree at the minus side of the cut hyperplane. */
  85.     private BSPTree<S, P, H, I> minus;

  87.     /** Parent tree. */
  88.     private BSPTree<S, P, H, I> parent;

  90.     /** Application-defined attribute. */
  91.     private Object attribute;

  93.     /** Build a tree having only one root cell representing the whole space.
  94.      */
  95.     public BSPTree() {
  96.         cut       = null;
  97.         plus      = null;
  98.         minus     = null;
  99.         parent    = null;
  100.         attribute = null;
  101.     }

  103.     /** Build a tree having only one root cell representing the whole space.
  104.      * @param attribute attribute of the tree (may be null)
  105.      */
  106.     public BSPTree(final Object attribute) {
  107.         cut    = null;
  108.         plus   = null;
  109.         minus  = null;
  110.         parent = null;
  111.         this.attribute = attribute;
  112.     }

  114.     /** Build a BSPTree from its underlying elements.
  115.      * <p>This method does <em>not</em> perform any verification on
  116.      * consistency of its arguments, it should therefore be used only
  117.      * when then caller knows what it is doing.</p>
  118.      * <p>This method is mainly useful to build trees
  119.      * bottom-up. Building trees top-down is realized with the help of
  120.      * method {@link #insertCut insertCut}.</p>
  121.      * @param cut cut sub-hyperplane for the tree
  122.      * @param plus plus side sub-tree
  123.      * @param minus minus side sub-tree
  124.      * @param attribute attribute associated with the node (may be null)
  125.      * @see #insertCut
  126.      */
  127.     public BSPTree(final I cut, final BSPTree<S, P, H, I> plus, final BSPTree<S, P, H, I> minus,
  128.                    final Object attribute) {
  129.         this.cut       = cut;
  130.         this.plus      = plus;
  131.         this.minus     = minus;
  132.         this.parent    = null;
  133.         this.attribute = attribute;
  134.         plus.parent    = this;
  135.         minus.parent   = this;
  136.     }

  138.     /** Insert a cut sub-hyperplane in a node.
  139.      * <p>The sub-tree starting at this node will be completely
  140.      * overwritten. The new cut sub-hyperplane will be built from the
  141.      * intersection of the provided hyperplane with the cell. If the
  142.      * hyperplane does intersect the cell, the cell will have two
  143.      * children cells with {@code null} attributes on each side of
  144.      * the inserted cut sub-hyperplane. If the hyperplane does not
  145.      * intersect the cell then <em>no</em> cut hyperplane will be
  146.      * inserted and the cell will be changed to a leaf cell. The
  147.      * attribute of the node is never changed.</p>
  148.      * <p>This method is mainly useful when called on leaf nodes
  149.      * (i.e. nodes for which {@link #getCut getCut} returns
  150.      * {@code null}), in this case it provides a way to build a
  151.      * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
  152.      * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
  153.      * build trees bottom-up).</p>
  154.      * @param hyperplane hyperplane to insert, it will be chopped in
  155.      * order to fit in the cell defined by the parent nodes of the
  156.      * instance
  157.      * @return true if a cut sub-hyperplane has been inserted (i.e. if
  158.      * the cell now has two leaf child nodes)
  159.      * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
  160.      */
  161.     public boolean insertCut(final H hyperplane) {

  163.         if (cut != null) {
  164.             plus.parent  = null;
  165.             minus.parent = null;
  166.         }

  168.         final I chopped = fitToCell(hyperplane.wholeHyperplane(), null);
  169.         if (chopped == null || chopped.isEmpty()) {
  170.             cut          = null;
  171.             plus         = null;
  172.             minus        = null;
  173.             return false;
  174.         }

  176.         cut          = chopped;
  177.         plus         = new BSPTree<>();
  178.         plus.parent  = this;
  179.         minus        = new BSPTree<>();
  180.         minus.parent = this;
  181.         return true;

  183.     }

  185.     /** Copy the instance.
  186.      * <p>The instance created is completely independent of the original
  187.      * one. A deep copy is used, none of the underlying objects are
  188.      * shared (except for the nodes attributes and immutable
  189.      * objects).</p>
  190.      * @return a new tree, copy of the instance
  191.      */
  192.     public BSPTree<S, P, H, I> copySelf() {

  194.         if (cut == null) {
  195.             return new BSPTree<>(attribute);
  196.         }

  198.         return new BSPTree<>(cut.copySelf(), plus.copySelf(), minus.copySelf(), attribute);

  200.     }

  202.     /** Get the cut sub-hyperplane.
  203.      * @return cut sub-hyperplane, null if this is a leaf tree
  204.      */
  205.     public I getCut() {
  206.         return cut;
  207.     }

  209.     /** Get the tree on the plus side of the cut hyperplane.
  210.      * @return tree on the plus side of the cut hyperplane, null if this
  211.      * is a leaf tree
  212.      */
  213.     public BSPTree<S, P, H, I> getPlus() {
  214.         return plus;
  215.     }

  217.     /** Get the tree on the minus side of the cut hyperplane.
  218.      * @return tree on the minus side of the cut hyperplane, null if this
  219.      * is a leaf tree
  220.      */
  221.     public BSPTree<S, P, H, I> getMinus() {
  222.         return minus;
  223.     }

  225.     /** Get the parent node.
  226.      * @return parent node, null if the node has no parents
  227.      */
  228.     public BSPTree<S, P, H, I> getParent() {
  229.         return parent;
  230.     }

  232.     /** Associate an attribute with the instance.
  233.      * @param attribute attribute to associate with the node
  234.      * @see #getAttribute
  235.      */
  236.     public void setAttribute(final Object attribute) {
  237.         this.attribute = attribute;
  238.     }

  240.     /** Get the attribute associated with the instance.
  241.      * @return attribute associated with the node or null if no
  242.      * attribute has been explicitly set using the {@link #setAttribute
  243.      * setAttribute} method
  244.      * @see #setAttribute
  245.      */
  246.     public Object getAttribute() {
  247.         return attribute;
  248.     }

  250.     /** Visit the BSP tree nodes.
  251.      * @param visitor object visiting the tree nodes
  252.      */
  253.     public void visit(final BSPTreeVisitor<S, P, H, I> visitor) {
  254.         if (cut == null) {
  255.             visitor.visitLeafNode(this);
  256.         } else {
  257.             switch (visitor.visitOrder(this)) {
  258.             case PLUS_MINUS_SUB:
  259.                 plus.visit(visitor);
  260.                 minus.visit(visitor);
  261.                 visitor.visitInternalNode(this);
  262.                 break;
  263.             case PLUS_SUB_MINUS:
  264.                 plus.visit(visitor);
  265.                 visitor.visitInternalNode(this);
  266.                 minus.visit(visitor);
  267.                 break;
  268.             case MINUS_PLUS_SUB:
  269.                 minus.visit(visitor);
  270.                 plus.visit(visitor);
  271.                 visitor.visitInternalNode(this);
  272.                 break;
  273.             case MINUS_SUB_PLUS:
  274.                 minus.visit(visitor);
  275.                 visitor.visitInternalNode(this);
  276.                 plus.visit(visitor);
  277.                 break;
  278.             case SUB_PLUS_MINUS:
  279.                 visitor.visitInternalNode(this);
  280.                 plus.visit(visitor);
  281.                 minus.visit(visitor);
  282.                 break;
  283.             case SUB_MINUS_PLUS:
  284.                 visitor.visitInternalNode(this);
  285.                 minus.visit(visitor);
  286.                 plus.visit(visitor);
  287.                 break;
  288.             default:
  289.                 throw MathRuntimeException.createInternalError();
  290.             }

  292.         }
  293.     }

  295.     /** Fit a sub-hyperplane inside the cell defined by the instance.
  296.      * <p>Fitting is done by chopping off the parts of the
  297.      * sub-hyperplane that lie outside the cell using the
  298.      * cut-hyperplanes of the parent nodes of the instance.</p>
  299.      * @param sub sub-hyperplane to fit
  300.      * @param ignored tree node to ignore (null if all nodes should be considered)
  301.      * @return a new sub-hyperplane, guaranteed to have no part outside
  302.      * of the instance cell
  303.      */
  304.     private I fitToCell(final I sub, final BSPTree<S, P, H, I> ignored) {
  305.         I s = sub;
  306.         for (BSPTree<S, P, H, I> tree = this; tree.parent != null && s != null; tree = tree.parent) {
  307.             if (tree.parent != ignored) {
  308.                 if (tree == tree.parent.plus) {
  309.                     s = s.split(tree.parent.cut.getHyperplane()).getPlus();
  310.                 }
  311.                 else {
  312.                     s = s.split(tree.parent.cut.getHyperplane()).getMinus();
  313.                 }
  314.             }
  315.         }
  316.         return s;
  317.     }

  319.     /** Get a point that is interior to the cell.
  320.      * @param defaultPoint default point to return if tree is empty
  321.      * @return point that is interior to the cell
  322.      * @since 4.0
  323.      */
  324.     public InteriorPoint<S, P> getInteriorPoint(final P defaultPoint) {

  326.         // find edges/facets interior points
  327.         final List<P> edgePoints = new ArrayList<>();
  328.         for (BSPTree<S, P, H, I> n = parent; n != null; n = n.getParent()) {
  329.             final I fit = fitToCell(n.getCut().getHyperplane().wholeHyperplane(), n);
  330.             if (fit != null) {
  331.                 final P p = fit.getInteriorPoint();
  332.                 if (p != null) {
  333.                     edgePoints.add(p);
  334.                 }
  335.             }
  336.         }

  338.         if (edgePoints.isEmpty()) {
  339.             // there are no edges/facets interior points at all!
  340.             // we are in a cell representing the whole space
  341.             return new InteriorPoint<>(defaultPoint, Double.POSITIVE_INFINITY);
  342.         } else {
  343.             // compute barycenter of edges/facets interior point
  344.             final P barycenter = Geometry.barycenter(edgePoints);

  346.             // compute distance to the closest edge/facet
  347.             double min = Double.POSITIVE_INFINITY;
  348.             for (BSPTree<S, P, H, I> n = parent; n != null; n = n.getParent()) {
  349.                 min = FastMath.min(min, FastMath.abs(n.getCut().getHyperplane().getOffset(barycenter)));
  350.             }

  352.             return new InteriorPoint<>(barycenter, min);
  353.         }

  355.     }

  357.     /** Get the cell to which a point belongs.
  358.      * <p>If the returned cell is a leaf node the points belongs to the
  359.      * interior of the node, if the cell is an internal node the points
  360.      * belongs to the node cut sub-hyperplane.</p>
  361.      * @param point point to check
  362.      * @param tolerance tolerance below which points close to a cut hyperplane
  363.      * are considered to belong to the hyperplane itself
  364.      * @return the tree cell to which the point belongs
  365.      */
  366.     public BSPTree<S, P, H, I> getCell(final P point, final double tolerance) {

  368.         if (cut == null) {
  369.             return this;
  370.         }

  372.         // position of the point with respect to the cut hyperplane
  373.         final double offset = cut.getHyperplane().getOffset(point);

  375.         if (FastMath.abs(offset) < tolerance) {
  376.             return this;
  377.         } else if (offset <= 0) {
  378.             // point is on the minus side of the cut hyperplane
  379.             return minus.getCell(point, tolerance);
  380.         } else {
  381.             // point is on the plus side of the cut hyperplane
  382.             return plus.getCell(point, tolerance);
  383.         }

  385.     }

  387.     /** Perform condensation on a tree.
  388.      * <p>The condensation operation is not recursive, it must be called
  389.      * explicitly from leaves to root.</p>
  390.      */
  391.     private void condense() {
  392.         if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
  393.             (((plus.attribute == null) && (minus.attribute == null)) ||
  394.              ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
  395.             attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
  396.             cut       = null;
  397.             plus      = null;
  398.             minus     = null;
  399.         }
  400.     }

  402.     /** Merge a BSP tree with the instance.
  403.      * <p>All trees are modified (parts of them are reused in the new
  404.      * tree), it is the responsibility of the caller to ensure a copy
  405.      * has been done before if any of the former tree should be
  406.      * preserved, <em>no</em> such copy is done here!</p>
  407.      * <p>The algorithm used here is directly derived from the one
  408.      * described in the Naylor, Amanatides and Thibault paper (section
  409.      * III, Binary Partitioning of a BSP Tree).</p>
  410.      * @param tree other tree to merge with the instance (will be
  411.      * <em>unusable</em> after the operation, as well as the
  412.      * instance itself)
  413.      * @param leafMerger object implementing the final merging phase
  414.      * (this is where the semantic of the operation occurs, generally
  415.      * depending on the attribute of the leaf node)
  416.      * @return a new tree, result of <code>instance &lt;op&gt;
  417.      * tree</code>, this value can be ignored if parentTree is not null
  418.      * since all connections have already been established
  419.      */
  420.     public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> tree, final LeafMerger<S, P, H, I> leafMerger) {
  421.         final BSPTree<S, P, H, I> merged = merge(tree, leafMerger, null, false);
  422.         merged.fixCuts();
  423.         return merged;
  424.     }

  426.     /** Merge a BSP tree with the instance.
  427.      * @param tree other tree to merge with the instance (will be
  428.      * <em>unusable</em> after the operation, as well as the
  429.      * instance itself)
  430.      * @param leafMerger object implementing the final merging phase
  431.      * (this is where the semantic of the operation occurs, generally
  432.      * depending on the attribute of the leaf node)
  433.      * @param parentTree parent tree to connect to (may be null)
  434.      * @param isPlusChild if true and if parentTree is not null, the
  435.      * resulting tree should be the plus child of its parent, ignored if
  436.      * parentTree is null
  437.      * @return a new tree, result of <code>instance &lt;op&gt;
  438.      * tree</code>, this value can be ignored if parentTree is not null
  439.      * since all connections have already been established
  440.      */
  441.     private BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> tree, final LeafMerger<S, P, H, I> leafMerger,
  442.                                       final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild) {
  443.         if (cut == null) {
  444.             // cell/tree operation
  445.             return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
  446.         } else if (tree.cut == null) {
  447.             // tree/cell operation
  448.             return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
  449.         } else {
  450.             // tree/tree operation
  451.             final BSPTree<S, P, H, I> merged = tree.split(cut);
  452.             if (parentTree != null) {
  453.                 merged.parent = parentTree;
  454.                 if (isPlusChild) {
  455.                     parentTree.plus = merged;
  456.                 } else {
  457.                     parentTree.minus = merged;
  458.                 }
  459.             }

  461.             // merging phase
  462.             plus.merge(merged.plus, leafMerger, merged, true);
  463.             minus.merge(merged.minus, leafMerger, merged, false);
  464.             merged.condense();
  465.             if (merged.cut != null) {
  466.                 merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane(), null);
  467.             }

  469.             return merged;

  471.         }
  472.     }

  474.     /** Fix cut sub-hyperplanes.
  475.      * <p>
  476.      * In some cases, cut sub-hyperplanes boundaries in a tree may be inconsistent.
  477.      * One cause can be merge operations, where some cuts are inherited from one of
  478.      * the merged tree, because the trees returned by {@link #split(SubHyperplane)}
  479.      * are not upward-consistent. Another cause can be trees built bottom-up.
  480.      * </p>
  481.      * <p>
  482.      * This method recomputes the sub-hyperplanes once the full tree has been built
  483.      * </p>
  484.      */
  485.     private void fixCuts() {
  486.         if (cut != null) {
  487.             final I fit = fitToCell(cut.getHyperplane().wholeHyperplane(), null);
  488.             if (fit == null) {
  489.                 // cut sub-hyperplane vanished
  490.                 cut = cut.getHyperplane().emptyHyperplane();
  491.             } else {
  492.                 cut = fit;
  493.             }
  494.             plus.fixCuts();
  495.             minus.fixCuts();
  496.         }
  497.     }

  499.     /** This interface gather the merging operations between a BSP tree
  500.      * leaf and another BSP tree.
  501.      * <p>As explained in Bruce Naylor, John Amanatides and William
  502.      * Thibault paper <a
  503.      * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
  504.      * BSP Trees Yields Polyhedral Set Operations</a>,
  505.      * the operations on {@link BSPTree BSP trees} can be expressed as a
  506.      * generic recursive merging operation where only the final part,
  507.      * when one of the operand is a leaf, is specific to the real
  508.      * operation semantics. For example, a tree representing a region
  509.      * using a boolean attribute to identify inside cells and outside
  510.      * cells would use four different objects to implement the final
  511.      * merging phase of the four set operations union, intersection,
  512.      * difference and symmetric difference (exclusive or).</p>
  513.      * @param <S> Type of the space.
  514.      * @param <P> Type of the points in space.
  515.      * @param <H> Type of the hyperplane.
  516.      * @param <I> Type of the sub-hyperplane.
  517.      */
  518.     public interface LeafMerger<S extends Space,
  519.                                 P extends Point<S, P>,
  520.                                 H extends Hyperplane<S, P, H, I>,
  521.                                 I extends SubHyperplane<S, P, H, I>> {

  523.         /** Merge a leaf node and a tree node.
  524.          * <p>This method is called at the end of a recursive merging
  525.          * resulting from a {@code tree1.merge(tree2, leafMerger)}
  526.          * call, when one of the sub-trees involved is a leaf (i.e. when
  527.          * its cut-hyperplane is null). This is the only place where the
  528.          * precise semantics of the operation are required. For all upper
  529.          * level nodes in the tree, the merging operation is only a
  530.          * generic partitioning algorithm.</p>
  531.          * <p>Since the final operation may be non-commutative, it is
  532.          * important to know if the leaf node comes from the instance tree
  533.          * ({@code tree1}) or the argument tree
  534.          * ({@code tree2}). The third argument of the method is
  535.          * devoted to this. It can be ignored for commutative
  536.          * operations.</p>
  537.          * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
  538.          * may be useful to implement this method.</p>
  539.          * @param leaf leaf node (its cut hyperplane is guaranteed to be
  540.          * null)
  541.          * @param tree tree node (its cut hyperplane may be null or not)
  542.          * @param parentTree parent tree to connect to (may be null)
  543.          * @param isPlusChild if true and if parentTree is not null, the
  544.          * resulting tree should be the plus child of its parent, ignored if
  545.          * parentTree is null
  546.          * @param leafFromInstance if true, the leaf node comes from the
  547.          * instance tree ({@code tree1}) and the tree node comes from
  548.          * the argument tree ({@code tree2})
  549.          * @return the BSP tree resulting from the merging (may be one of
  550.          * the arguments)
  551.          */
  552.         BSPTree<S, P, H, I> merge(BSPTree<S, P, H, I> leaf, BSPTree<S, P, H, I> tree,
  553.                                   BSPTree<S, P, H, I> parentTree, boolean isPlusChild, boolean leafFromInstance);

  555.     }

  557.     /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.
  558.      * <p>
  559.      * Such cases happens for example when a cut sub-hyperplane is inserted into
  560.      * another tree (during a merge operation), and is split in several parts,
  561.      * some of which becomes smaller than the tolerance. The corresponding node
  562.      * as then no cut sub-hyperplane anymore, but does have children. This interface
  563.      * specifies how to handle this situation.
  564.      * setting
  565.      * </p>
  566.      * @param <S> Type of the space.
  567.      * @param <P> Type of the points in space.
  568.      * @param <H> Type of the hyperplane.
  569.      * @param <I> Type of the sub-hyperplane.
  570.      */
  571.     public interface VanishingCutHandler<S extends Space,
  572.                                          P extends Point<S, P>,
  573.                                          H extends Hyperplane<S, P, H, I>,
  574.                                          I extends SubHyperplane<S, P, H, I>> {

  576.         /** Fix a node with both vanished cut and children.
  577.          * @param node node to fix
  578.          * @return fixed node
  579.          */
  580.         BSPTree<S, P, H, I> fixNode(BSPTree<S, P, H, I> node);

  582.     }

  584.     /** Split a BSP tree by an external sub-hyperplane.
  585.      * <p>Split a tree in two halves, on each side of the
  586.      * sub-hyperplane. The instance is not modified.</p>
  587.      * <p>The tree returned is not upward-consistent: despite all of its
  588.      * sub-trees cut sub-hyperplanes (including its own cut
  589.      * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
  590.      * attached to any parent tree yet. This tree is intended to be
  591.      * later inserted into a higher level tree.</p>
  592.      * <p>The algorithm used here is the one given in Naylor, Amanatides
  593.      * and Thibault paper (section III, Binary Partitioning of a BSP
  594.      * Tree).</p>
  595.      * @param sub partitioning sub-hyperplane, must be already clipped
  596.      * to the convex region represented by the instance, will be used as
  597.      * the cut sub-hyperplane of the returned tree
  598.      * @return a tree having the specified sub-hyperplane as its cut
  599.      * sub-hyperplane, the two parts of the split instance as its two
  600.      * sub-trees and a null parent
  601.      */
  602.     public BSPTree<S, P, H, I> split(final I sub) {

  604.         if (cut == null) {
  605.             return new BSPTree<>(sub, copySelf(), new BSPTree<>(attribute), null);
  606.         }

  608.         final H cHyperplane = cut.getHyperplane();
  609.         final H sHyperplane = sub.getHyperplane();
  610.         final SubHyperplane.SplitSubHyperplane<S, P, H, I> subParts = sub.split(cHyperplane);
  611.         switch (subParts.getSide()) {
  612.         case PLUS :
  613.         { // the partitioning sub-hyperplane is entirely in the plus sub-tree
  614.             final BSPTree<S, P, H, I> split = plus.split(sub);
  615.             if (cut.split(sHyperplane).getSide() == Side.PLUS) {
  616.                 split.plus = new BSPTree<>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
  617.                 split.plus.condense();
  618.                 split.plus.parent = split;
  619.             } else {
  620.                 split.minus = new BSPTree<>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
  621.                 split.minus.condense();
  622.                 split.minus.parent = split;
  623.             }
  624.             return split;
  625.         }
  626.         case MINUS :
  627.         { // the partitioning sub-hyperplane is entirely in the minus sub-tree
  628.             final BSPTree<S, P, H, I> split = minus.split(sub);
  629.             if (cut.split(sHyperplane).getSide() == Side.PLUS) {
  630.                 split.plus = new BSPTree<>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
  631.                 split.plus.condense();
  632.                 split.plus.parent = split;
  633.             } else {
  634.                 split.minus = new BSPTree<>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
  635.                 split.minus.condense();
  636.                 split.minus.parent = split;
  637.             }
  638.             return split;
  639.         }
  640.         case BOTH :
  641.         {
  642.             final SubHyperplane.SplitSubHyperplane<S, P, H, I> cutParts = cut.split(sHyperplane);
  643.             final BSPTree<S, P, H, I> split = new BSPTree<>(sub,
  644.                                                             plus.split(subParts.getPlus()),
  645.                                                             minus.split(subParts.getMinus()),
  646.                                                             null);
  647.             final BSPTree<S, P, H, I> tmp    = split.plus.minus;
  648.             split.plus.minus        = split.minus.plus;
  649.             split.plus.minus.parent = split.plus;
  650.             split.minus.plus        = tmp;
  651.             split.minus.plus.parent = split.minus;
  652.             if (cutParts.getPlus() == null) {
  653.                 split.plus.cut = cut.getHyperplane().emptyHyperplane();
  654.             } else {
  655.                 split.plus.cut = cutParts.getPlus();
  656.             }
  657.             if (cutParts.getMinus() == null) {
  658.                 split.minus.cut = cut.getHyperplane().emptyHyperplane();
  659.             } else {
  660.                 split.minus.cut = cutParts.getMinus();
  661.             }
  662.             split.plus.condense();
  663.             split.minus.condense();
  664.             return split;

  666.         }
  667.         default :
  668.             return cHyperplane.sameOrientationAs(sHyperplane) ?
  669.                    new BSPTree<>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
  670.                    new BSPTree<>(sub, minus.copySelf(), plus.copySelf(),  attribute);
  671.         }

  673.     }

  675.     /** Insert the instance into another tree.
  676.      * <p>The instance itself is modified so its former parent should
  677.      * not be used anymore.</p>
  678.      * @param parentTree parent tree to connect to (may be null)
  679.      * @param isPlusChild if true and if parentTree is not null, the
  680.      * resulting tree should be the plus child of its parent, ignored if
  681.      * parentTree is null
  682.      * @param vanishingHandler handler to use for handling very rare corner
  683.      * cases of vanishing cut sub-hyperplanes in internal nodes during merging
  684.      * @see LeafMerger
  685.      */
  686.     public void insertInTree(final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild,
  687.                              final VanishingCutHandler<S, P, H, I> vanishingHandler) {

  689.         // set up parent/child links
  690.         parent = parentTree;
  691.         if (parentTree != null) {
  692.             if (isPlusChild) {
  693.                 parentTree.plus = this;
  694.             } else {
  695.                 parentTree.minus = this;
  696.             }
  697.         }

  699.         // make sure the inserted tree lies in the cell defined by its parent nodes
  700.         if (cut != null) {

  702.             // explore the parent nodes from here towards tree root
  703.             for (BSPTree<S, P, H, I> tree = this; tree.parent != null; tree = tree.parent) {

  705.                 // this is an hyperplane of some parent node
  706.                 final H hyperplane = tree.parent.cut.getHyperplane();

  708.                 // chop off the parts of the inserted tree that extend
  709.                 // on the wrong side of this parent hyperplane
  710.                 if (tree == tree.parent.plus) {
  711.                     cut = cut.split(hyperplane).getPlus();
  712.                     fixVanishingCut(vanishingHandler);
  713.                     if (cut == null) {
  714.                         break;
  715.                     }
  716.                     plus.chopOffMinus(hyperplane, vanishingHandler);
  717.                     minus.chopOffMinus(hyperplane, vanishingHandler);
  718.                 } else {
  719.                     cut = cut.split(hyperplane).getMinus();
  720.                     fixVanishingCut(vanishingHandler);
  721.                     if (cut == null) {
  722.                         break;
  723.                     }
  724.                     plus.chopOffPlus(hyperplane, vanishingHandler);
  725.                     minus.chopOffPlus(hyperplane, vanishingHandler);
  726.                 }
  727.             }

  729.             // since we may have drop some parts of the inserted tree,
  730.             // perform a condensation pass to keep the tree structure simple
  731.             condense();

  733.         }

  735.     }

  737.     /** Prune a tree around a cell.
  738.      * <p>
  739.      * This method can be used to extract a convex cell from a tree.
  740.      * The original cell may either be a leaf node or an internal node.
  741.      * If it is an internal node, it's subtree will be ignored (i.e. the
  742.      * extracted cell will be a leaf node in all cases). The original
  743.      * tree to which the original cell belongs is not touched at all,
  744.      * a new independent tree will be built.
  745.      * </p>
  746.      * @param cellAttribute attribute to set for the leaf node
  747.      * corresponding to the initial instance cell
  748.      * @param otherLeafsAttributes attribute to set for the other leaf
  749.      * nodes
  750.      * @param internalAttributes attribute to set for the internal nodes
  751.      * @return a new tree (the original tree is left untouched) containing
  752.      * a single branch with the cell as a leaf node, and other leaf nodes
  753.      * as the remnants of the pruned branches
  754.      */
  755.     public BSPTree<S, P, H, I> pruneAroundConvexCell(final Object cellAttribute,
  756.                                                      final Object otherLeafsAttributes,
  757.                                                      final Object internalAttributes) {

  759.         // build the current cell leaf
  760.         BSPTree<S, P, H, I> tree = new BSPTree<>(cellAttribute);

  762.         // build the pruned tree bottom-up
  763.         for (BSPTree<S, P, H, I> current = this; current.parent != null; current = current.parent) {
  764.             final I parentCut = current.parent.cut.copySelf();
  765.             final BSPTree<S, P, H, I> sibling   = new BSPTree<>(otherLeafsAttributes);
  766.             if (current == current.parent.plus) {
  767.                 tree = new BSPTree<>(parentCut, tree, sibling, internalAttributes);
  768.             } else {
  769.                 tree = new BSPTree<>(parentCut, sibling, tree, internalAttributes);
  770.             }
  771.         }

  773.         // fix the cuts so the pruned tree is consistent
  774.         tree.fixCuts();

  776.         return tree;

  778.     }

  780.     /** Chop off parts of the tree.
  781.      * <p>The instance is modified in place, all the parts that are on
  782.      * the minus side of the chopping hyperplane are discarded, only the
  783.      * parts on the plus side remain.</p>
  784.      * @param hyperplane chopping hyperplane
  785.      * @param vanishingHandler handler to use for handling very rare corner
  786.      * cases of vanishing cut sub-hyperplanes in internal nodes during merging
  787.      */
  788.     private void chopOffMinus(final H hyperplane, final VanishingCutHandler<S, P, H, I> vanishingHandler) {
  789.         if (cut != null) {

  791.             cut = cut.split(hyperplane).getPlus();
  792.             plus.chopOffMinus(hyperplane, vanishingHandler);
  793.             minus.chopOffMinus(hyperplane, vanishingHandler);

  795.             fixVanishingCut(vanishingHandler);

  797.         }
  798.     }

  800.     /** Chop off parts of the tree.
  801.      * <p>The instance is modified in place, all the parts that are on
  802.      * the plus side of the chopping hyperplane are discarded, only the
  803.      * parts on the minus side remain.</p>
  804.      * @param hyperplane chopping hyperplane
  805.      * @param vanishingHandler handler to use for handling very rare corner
  806.      * cases of vanishing cut sub-hyperplanes in internal nodes during merging
  807.      */
  808.     private void chopOffPlus(final H hyperplane, final VanishingCutHandler<S, P, H, I> vanishingHandler) {
  809.         if (cut != null) {

  811.             cut = cut.split(hyperplane).getMinus();
  812.             plus.chopOffPlus(hyperplane, vanishingHandler);
  813.             minus.chopOffPlus(hyperplane, vanishingHandler);

  815.             fixVanishingCut(vanishingHandler);

  817.         }
  818.     }

  820.     /** Fix vanishing cut.
  821.      * @param vanishingHandler handler to use for handling very rare corner
  822.      */
  823.     private void fixVanishingCut(final VanishingCutHandler<S, P, H, I> vanishingHandler) {
  824.         if (cut == null) {
  825.             // the cut sub-hyperplane has vanished
  826.             final BSPTree<S, P, H, I> fixed = vanishingHandler.fixNode(this);
  827.             cut       = fixed.cut;
  828.             plus      = fixed.plus;
  829.             minus     = fixed.minus;
  830.             attribute = fixed.attribute;
  831.         }
  832.     }

  834.     /** Container for cell interior points.
  835.      * @param <S> Type of the space.
  836.      * @param <P> Type of the points in space.
  837.      * @since 4.0
  838.      */
  839.     public static final class InteriorPoint <S extends Space, P extends Point<S, P>> {

  841.         /** Point. */
  842.         private final P point;

  844.         /** Distance to the closest edge/facet. */
  845.         private final double distance;

  847.         /** Simple constructor.
  848.          * @param point point
  849.          * @param distance d
  850.          */
  851.         InteriorPoint(final P point, final double distance) {
  852.             this.point    = point;
  853.             this.distance = distance;
  854.         }

  856.         /** Get the interior point.
  857.          * @return interior point
  858.          */
  859.         public P getPoint() {
  860.             return point;
  861.         }

  863.         /** Get the distance to the closest edge/facet.
  864.          * @return distance to the closest edge/facet.
  865.          */
  866.         public double getDistance() {
  867.             return distance;
  868.         }

  870.     }

  872. }
Created with JaCoCo 0.8.12.202403310830