AbstractRegionBSPTree.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.  *      http://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.  */
  17. package org.apache.commons.geometry.core.partitioning.bsp;

  19. import java.util.ArrayList;
  20. import java.util.Iterator;
  21. import java.util.List;
  22. import java.util.function.Function;
  23. import java.util.stream.Stream;

  25. import org.apache.commons.geometry.core.Point;
  26. import org.apache.commons.geometry.core.RegionLocation;
  27. import org.apache.commons.geometry.core.internal.IteratorTransform;
  28. import org.apache.commons.geometry.core.partitioning.BoundarySource;
  29. import org.apache.commons.geometry.core.partitioning.Hyperplane;
  30. import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
  31. import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
  32. import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
  33. import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
  34. import org.apache.commons.geometry.core.partitioning.Split;
  35. import org.apache.commons.geometry.core.partitioning.SplitLocation;
  36. import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;

  38. /** Abstract {@link BSPTree} specialized for representing regions of space. For example,
  39.  * this class can be used to represent polygons in Euclidean 2D space and polyhedrons
  40.  * in Euclidean 3D space.
  41.  *
  42.  * <p>This class is not thread safe.</p>
  43.  * @param <P> Point implementation type
  44.  * @param <N> BSP tree node implementation type
  45.  * @see HyperplaneBoundedRegion
  46.  */
  47. public abstract class AbstractRegionBSPTree<
  48.         P extends Point<P>,
  49.         N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>
  50.     extends AbstractBSPTree<P, N> implements HyperplaneBoundedRegion<P> {

  52.     /** The default {@link RegionCutRule}. */
  53.     private static final RegionCutRule DEFAULT_REGION_CUT_RULE = RegionCutRule.MINUS_INSIDE;

  55.     /** Value used to indicate an unknown size. */
  56.     private static final double UNKNOWN_SIZE = -1.0;

  58.     /** The region boundary size; this is computed when requested and then cached. */
  59.     private double boundarySize = UNKNOWN_SIZE;

  61.     /** The current size properties for the region. */
  62.     private RegionSizeProperties<P> regionSizeProperties;

  64.     /** Construct a new region will the given boolean determining whether or not the
  65.      * region will be full (including the entire space) or empty (excluding the entire
  66.      * space).
  67.      * @param full if true, the region will cover the entire space, otherwise it will
  68.      *      be empty
  69.      */
  70.     protected AbstractRegionBSPTree(final boolean full) {
  71.         getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
  72.     }

  74.     /** {@inheritDoc} */
  75.     @Override
  76.     public boolean isEmpty() {
  77.         return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.INSIDE);
  78.     }

  80.     /** {@inheritDoc} */
  81.     @Override
  82.     public boolean isFull() {
  83.         return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.OUTSIDE);
  84.     }

  86.     /** Return true if any node in the subtree rooted at the given node has a location with the
  87.      * given value.
  88.      * @param node the node at the root of the subtree to search
  89.      * @param location the location to find
  90.      * @return true if any node in the subtree has the given location
  91.      */
  92.     private boolean hasNodeWithLocationRecursive(final AbstractRegionNode<P, N> node, final RegionLocation location) {
  93.         if (node == null) {
  94.             return false;
  95.         }

  97.         return node.getLocation() == location ||
  98.                 hasNodeWithLocationRecursive(node.getMinus(), location) ||
  99.                 hasNodeWithLocationRecursive(node.getPlus(), location);
  100.     }

  102.     /** Modify this instance so that it contains the entire space.
  103.      * @see #isFull()
  104.      */
  105.     public void setFull() {
  106.         final N root = getRoot();

  108.         root.clearCut();
  109.         root.setLocationValue(RegionLocation.INSIDE);
  110.     }

  112.     /** Modify this instance so that is is completely empty.
  113.      * @see #isEmpty()
  114.      */
  115.     public void setEmpty() {
  116.         final N root = getRoot();

  118.         root.clearCut();
  119.         root.setLocationValue(RegionLocation.OUTSIDE);
  120.     }

  122.     /** {@inheritDoc} */
  123.     @Override
  124.     public double getSize() {
  125.         return getRegionSizeProperties().getSize();
  126.     }

  128.     /** {@inheritDoc} */
  129.     @Override
  130.     public double getBoundarySize() {
  131.         if (boundarySize < 0) {
  132.             double sum = 0.0;

  134.             RegionCutBoundary<P> boundary;
  135.             for (final AbstractRegionNode<P, N> node : nodes()) {
  136.                 boundary = node.getCutBoundary();
  137.                 if (boundary != null) {
  138.                     sum += boundary.getSize();
  139.                 }
  140.             }

  142.             boundarySize = sum;
  143.         }

  145.         return boundarySize;
  146.     }

  148.     /** Insert a hyperplane subset into the tree, using the default {@link RegionCutRule} of
  149.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  150.      * @param sub the hyperplane subset to insert into the tree
  151.      */
  152.     public void insert(final HyperplaneSubset<P> sub) {
  153.         insert(sub, DEFAULT_REGION_CUT_RULE);
  154.     }

  156.     /** Insert a hyperplane subset into the tree.
  157.      * @param sub the hyperplane subset to insert into the tree
  158.      * @param cutRule rule used to determine the region locations of new child nodes
  159.      */
  160.     public void insert(final HyperplaneSubset<P> sub, final RegionCutRule cutRule) {
  161.         insert(sub.toConvex(), cutRule);
  162.     }

  164.     /** Insert a hyperplane convex subset into the tree, using the default {@link RegionCutRule} of
  165.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  166.      * @param convexSub the hyperplane convex subset to insert into the tree
  167.      */
  168.     public void insert(final HyperplaneConvexSubset<P> convexSub) {
  169.         insert(convexSub, DEFAULT_REGION_CUT_RULE);
  170.     }

  172.     /** Insert a hyperplane convex subset into the tree.
  173.      * @param convexSub the hyperplane convex subset to insert into the tree
  174.      * @param cutRule rule used to determine the region locations of new child nodes
  175.      */
  176.     public void insert(final HyperplaneConvexSubset<P> convexSub, final RegionCutRule cutRule) {
  177.         insert(convexSub, getSubtreeInitializer(cutRule));
  178.     }

  180.     /** Insert a set of hyperplane convex subsets into the tree, using the default {@link RegionCutRule} of
  181.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  182.      * @param convexSubs iterable containing a collection of hyperplane convex subsets
  183.      *      to insert into the tree
  184.      */
  185.     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs) {
  186.         insert(convexSubs, DEFAULT_REGION_CUT_RULE);
  187.     }

  189.     /** Insert a set of hyperplane convex subsets into the tree.
  190.      * @param convexSubs iterable containing a collection of hyperplane convex subsets
  191.      *      to insert into the tree
  192.      * @param cutRule rule used to determine the region locations of new child nodes
  193.      */
  194.     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, final RegionCutRule cutRule) {
  195.         for (final HyperplaneConvexSubset<P> convexSub : convexSubs) {
  196.             insert(convexSub, cutRule);
  197.         }
  198.     }

  200.     /** Insert all hyperplane convex subsets from the given source into the tree, using the default
  201.      * {@link RegionCutRule} of {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  202.      * @param boundarySrc source of boundary hyperplane subsets to insert
  203.      *      into the tree
  204.      */
  205.     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc) {
  206.         insert(boundarySrc, DEFAULT_REGION_CUT_RULE);
  207.     }

  209.     /** Insert all hyperplane convex subsets from the given source into the tree.
  210.      * @param boundarySrc source of boundary hyperplane subsets to insert
  211.      *      into the tree
  212.      * @param cutRule rule used to determine the region locations of new child nodes
  213.      */
  214.     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc,
  215.             final RegionCutRule cutRule) {
  216.         try (Stream<? extends HyperplaneConvexSubset<P>> stream = boundarySrc.boundaryStream()) {
  217.             stream.forEach(c -> insert(c, cutRule));
  218.         }
  219.     }

  221.     /** Get the subtree initializer to use for the given region cut rule.
  222.      * @param cutRule the cut rule to get an initializer for
  223.      * @return the subtree initializer for the given region cut rule
  224.      */
  225.     protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) {
  226.         switch (cutRule) {
  227.         case INHERIT:
  228.             return root -> {
  229.                 final RegionLocation rootLoc = root.getLocation();

  231.                 root.getMinus().setLocationValue(rootLoc);
  232.                 root.getPlus().setLocationValue(rootLoc);
  233.             };
  234.         case PLUS_INSIDE:
  235.             return root -> {
  236.                 root.getMinus().setLocationValue(RegionLocation.OUTSIDE);
  237.                 root.getPlus().setLocationValue(RegionLocation.INSIDE);
  238.             };
  239.         default:
  240.             return root -> {
  241.                 root.getMinus().setLocationValue(RegionLocation.INSIDE);
  242.                 root.getPlus().setLocationValue(RegionLocation.OUTSIDE);
  243.             };
  244.         }
  245.     }

  247.     /** Return an {@link Iterable} for iterating over the boundaries of the region.
  248.      * Each boundary is oriented such that its plus side points to the outside of the
  249.      * region. The exact ordering of the boundaries is determined by the internal structure
  250.      * of the tree.
  251.      * @return an {@link Iterable} for iterating over the boundaries of the region
  252.      * @see #getBoundaries()
  253.      */
  254.     public Iterable<? extends HyperplaneConvexSubset<P>> boundaries() {
  255.         return createBoundaryIterable(Function.identity());
  256.     }

  258.     /** Internal method for creating the iterable instances used to iterate the region boundaries.
  259.      * @param typeConverter function to convert the generic hyperplane subset type into
  260.      *      the type specific for this tree
  261.      * @param <C> HyperplaneConvexSubset implementation type
  262.      * @return an iterable to iterating the region boundaries
  263.      */
  264.     protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(
  265.             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {

  267.         return () -> new RegionBoundaryIterator<>(
  268.                 getRoot().nodes().iterator(),
  269.                 typeConverter);
  270.     }

  272.     /** Return a list containing the boundaries of the region. Each boundary is oriented such
  273.      * that its plus side points to the outside of the region. The exact ordering of
  274.      * the boundaries is determined by the internal structure of the tree.
  275.      * @return a list of the boundaries of the region
  276.      */
  277.     public List<? extends HyperplaneConvexSubset<P>> getBoundaries() {
  278.         return createBoundaryList(Function.identity());
  279.     }

  281.     /** Internal method for creating a list of the region boundaries.
  282.      * @param typeConverter function to convert the generic convex subset type into
  283.      *      the type specific for this tree
  284.      * @param <C> HyperplaneConvexSubset implementation type
  285.      * @return a list of the region boundaries
  286.      */
  287.     protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(
  288.             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {

  290.         final List<C> result = new ArrayList<>();

  292.         final RegionBoundaryIterator<P, C, N> it = new RegionBoundaryIterator<>(nodes().iterator(), typeConverter);
  293.         it.forEachRemaining(result::add);

  295.         return result;
  296.     }

  298.     /** {@inheritDoc} */
  299.     @Override
  300.     public P project(final P pt) {
  301.         final BoundaryProjector<P, N> projector = new BoundaryProjector<>(pt);
  302.         accept(projector);

  304.         return projector.getProjected();
  305.     }

  307.     /** {@inheritDoc} */
  308.     @Override
  309.     public P getCentroid() {
  310.         return getRegionSizeProperties().getCentroid();
  311.     }

  313.     /** Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses
  314.      * should call this method with two instantiated trees of the correct type.
  315.      * @param splitter splitting hyperplane
  316.      * @param minus tree that will contain the minus side of the split result
  317.      * @param plus tree that will contain the plus side of the split result
  318.      * @param <T> Tree implementation type
  319.      * @return result of splitting this tree with the given hyperplane
  320.      */
  321.     protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(final Hyperplane<P> splitter,
  322.             final T minus, final T plus) {

  324.         splitIntoTrees(splitter, minus, plus);

  326.         T splitMinus = null;
  327.         T splitPlus = null;

  329.         if (minus != null) {
  330.             minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE);
  331.             minus.condense();

  333.             splitMinus = minus.isEmpty() ? null : minus;
  334.         }
  335.         if (plus != null) {
  336.             plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE);
  337.             plus.condense();

  339.             splitPlus = plus.isEmpty() ? null : plus;
  340.         }

  342.         return new Split<>(splitMinus, splitPlus);
  343.     }

  345.     /** Get the size-related properties for the region. The value is computed
  346.      * lazily and cached.
  347.      * @return the size-related properties for the region
  348.      */
  349.     protected RegionSizeProperties<P> getRegionSizeProperties() {
  350.         if (regionSizeProperties == null) {
  351.             regionSizeProperties = computeRegionSizeProperties();
  352.         }

  354.         return regionSizeProperties;
  355.     }

  357.     /** Compute the size-related properties of the region.
  358.      * @return object containing size properties for the region
  359.      */
  360.     protected abstract RegionSizeProperties<P> computeRegionSizeProperties();

  362.     /** {@inheritDoc}
  363.      *
  364.      * <p>If the point is {@link org.apache.commons.geometry.core.Spatial#isNaN() NaN}, then
  365.      * {@link RegionLocation#OUTSIDE} is returned.</p>
  366.      */
  367.     @Override
  368.     public RegionLocation classify(final P point) {
  369.         if (point.isNaN()) {
  370.             return RegionLocation.OUTSIDE;
  371.         }

  373.         return classifyRecursive(getRoot(), point);
  374.     }

  376.     /** Recursively classify a point with respect to the region.
  377.      * @param node the node to classify against
  378.      * @param point the point to classify
  379.      * @return the classification of the point with respect to the region rooted
  380.      *      at the given node
  381.      */
  382.     private RegionLocation classifyRecursive(final AbstractRegionNode<P, N> node, final P point) {
  383.         if (node.isLeaf()) {
  384.             // the point is in a leaf, so the classification is just the leaf location
  385.             return node.getLocation();
  386.         } else {
  387.             final HyperplaneLocation cutLoc = node.getCutHyperplane().classify(point);

  389.             if (cutLoc == HyperplaneLocation.MINUS) {
  390.                 return classifyRecursive(node.getMinus(), point);
  391.             } else if (cutLoc == HyperplaneLocation.PLUS) {
  392.                 return classifyRecursive(node.getPlus(), point);
  393.             } else {
  394.                 // the point is on the cut boundary; classify against both child
  395.                 // subtrees and see if we end up with the same result or not
  396.                 final RegionLocation minusLoc = classifyRecursive(node.getMinus(), point);
  397.                 final RegionLocation plusLoc = classifyRecursive(node.getPlus(), point);

  399.                 if (minusLoc == plusLoc) {
  400.                     return minusLoc;
  401.                 }
  402.                 return RegionLocation.BOUNDARY;
  403.             }
  404.         }
  405.     }

  407.     /** Change this region into its complement. All inside nodes become outside
  408.      * nodes and vice versa. The orientations of the node cuts are not modified.
  409.      */
  410.     public void complement() {
  411.         complementRecursive(getRoot());
  412.     }

  414.     /** Set this instance to be the complement of the given tree. The argument
  415.      * is not modified.
  416.      * @param tree the tree to become the complement of
  417.      */
  418.     public void complement(final AbstractRegionBSPTree<P, N> tree) {
  419.         copySubtree(tree.getRoot(), getRoot());
  420.         complementRecursive(getRoot());
  421.     }

  423.     /** Recursively switch all inside nodes to outside nodes and vice versa.
  424.      * @param node the node at the root of the subtree to switch
  425.      */
  426.     private void complementRecursive(final AbstractRegionNode<P, N> node) {
  427.         if (node != null) {
  428.             final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ?
  429.                     RegionLocation.OUTSIDE :
  430.                     RegionLocation.INSIDE;

  432.             node.setLocationValue(newLoc);

  434.             complementRecursive(node.getMinus());
  435.             complementRecursive(node.getPlus());
  436.         }
  437.     }

  439.     /** Compute the union of this instance and the given region, storing the result back in
  440.      * this instance. The argument is not modified.
  441.      * @param other the tree to compute the union with
  442.      */
  443.     public void union(final AbstractRegionBSPTree<P, N> other) {
  444.         new UnionOperator<P, N>().apply(this, other, this);
  445.     }

  447.     /** Compute the union of the two regions passed as arguments and store the result in
  448.      * this instance. Any nodes currently existing in this instance are removed.
  449.      * @param a first argument to the union operation
  450.      * @param b second argument to the union operation
  451.      */
  452.     public void union(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  453.         new UnionOperator<P, N>().apply(a, b, this);
  454.     }

  456.     /** Compute the intersection of this instance and the given region, storing the result back in
  457.      * this instance. The argument is not modified.
  458.      * @param other the tree to compute the intersection with
  459.      */
  460.     public void intersection(final AbstractRegionBSPTree<P, N> other) {
  461.         new IntersectionOperator<P, N>().apply(this, other, this);
  462.     }

  464.     /** Compute the intersection of the two regions passed as arguments and store the result in
  465.      * this instance. Any nodes currently existing in this instance are removed.
  466.      * @param a first argument to the intersection operation
  467.      * @param b second argument to the intersection operation
  468.      */
  469.     public void intersection(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  470.         new IntersectionOperator<P, N>().apply(a, b, this);
  471.     }

  473.     /** Compute the difference of this instance and the given region, storing the result back in
  474.      * this instance. The argument is not modified.
  475.      * @param other the tree to compute the difference with
  476.      */
  477.     public void difference(final AbstractRegionBSPTree<P, N> other) {
  478.         new DifferenceOperator<P, N>().apply(this, other, this);
  479.     }

  481.     /** Compute the difference of the two regions passed as arguments and store the result in
  482.      * this instance. Any nodes currently existing in this instance are removed.
  483.      * @param a first argument to the difference operation
  484.      * @param b second argument to the difference operation
  485.      */
  486.     public void difference(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  487.         new DifferenceOperator<P, N>().apply(a, b, this);
  488.     }

  490.     /** Compute the symmetric difference (xor) of this instance and the given region, storing the result back in
  491.      * this instance. The argument is not modified.
  492.      * @param other the tree to compute the symmetric difference with
  493.      */
  494.     public void xor(final AbstractRegionBSPTree<P, N> other) {
  495.         new XorOperator<P, N>().apply(this, other, this);
  496.     }

  498.     /** Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in
  499.      * this instance. Any nodes currently existing in this instance are removed.
  500.      * @param a first argument to the symmetric difference operation
  501.      * @param b second argument to the symmetric difference operation
  502.      */
  503.     public void xor(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  504.         new XorOperator<P, N>().apply(a, b, this);
  505.     }

  507.     /** Condense this tree by removing redundant subtrees, returning true if the
  508.      * tree structure was modified.
  509.      *
  510.      * <p>This operation can be used to reduce the total number of nodes in the
  511.      * tree after performing node manipulations. For example, if two sibling leaf
  512.      * nodes both represent the same {@link RegionLocation}, then there is no reason
  513.      * from the perspective of the geometric region to retain both nodes. They are
  514.      * therefore both merged into their parent node. This method performs this
  515.      * simplification process.
  516.      * </p>
  517.      * @return true if the tree structure was modified, otherwise false
  518.      */
  519.     public boolean condense() {
  520.         return new Condenser<P, N>().condense(getRoot());
  521.     }

  523.     /** {@inheritDoc} */
  524.     @Override
  525.     protected void copyNodeProperties(final N src, final N dst) {
  526.         dst.setLocationValue(src.getLocation());
  527.     }

  529.     /** {@inheritDoc} */
  530.     @Override
  531.     protected void invalidate() {
  532.         super.invalidate();

  534.         // clear cached region properties
  535.         boundarySize = UNKNOWN_SIZE;
  536.         regionSizeProperties = null;
  537.     }

  539.     /** {@link BSPTree.Node} implementation for use with {@link AbstractRegionBSPTree}s.
  540.      * @param <P> Point implementation type
  541.      * @param <N> BSP tree node implementation type
  542.      */
  543.     public abstract static class AbstractRegionNode<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  544.         extends AbstractBSPTree.AbstractNode<P, N> {
  545.         /** The location for the node. This will only be set on leaf nodes. */
  546.         private RegionLocation location;

  548.         /** Object representing the part of the node cut hyperplane subset that lies on the
  549.          * region boundary. This is calculated lazily and is only present on internal nodes.
  550.          */
  551.         private RegionCutBoundary<P> cutBoundary;

  553.         /** Simple constructor.
  554.          * @param tree owning tree instance
  555.          */
  556.         protected AbstractRegionNode(final AbstractBSPTree<P, N> tree) {
  557.             super(tree);
  558.         }

  560.         /** {@inheritDoc} */
  561.         @Override
  562.         public AbstractRegionBSPTree<P, N> getTree() {
  563.             // cast to our parent tree type
  564.             return (AbstractRegionBSPTree<P, N>) super.getTree();
  565.         }

  567.         /** Get the location property of the node. Only the locations of leaf nodes are meaningful
  568.          * as they relate to the region represented by the BSP tree. For example, changing
  569.          * the location of an internal node will only affect the geometric properties
  570.          * of the region if the node later becomes a leaf node.
  571.          * @return the location of the node
  572.          */
  573.         public RegionLocation getLocation() {
  574.             return location;
  575.         }

  577.         /** Set the location property for the node. If the location is changed, the tree is
  578.          * invalidated.
  579.          *
  580.          * <p>Only the locations of leaf nodes are meaningful
  581.          * as they relate to the region represented by the BSP tree. For example, changing
  582.          * the location of an internal node will only affect the geometric properties
  583.          * of the region if the node later becomes a leaf node.</p>
  584.          * @param location the location for the node
  585.          * @throws IllegalArgumentException if {@code location} is not one of
  586.          *      {@link RegionLocation#INSIDE INSIDE} or {@link RegionLocation#OUTSIDE OUTSIDE}
  587.          */
  588.         public void setLocation(final RegionLocation location) {
  589.             if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) {
  590.                 throw new IllegalArgumentException("Invalid node location: " + location);
  591.             }
  592.             if (this.location != location) {
  593.                 this.location = location;

  595.                 getTree().invalidate();
  596.             }
  597.         }

  599.         /** True if the node is a leaf node and has a location of {@link RegionLocation#INSIDE}.
  600.          * @return true if the node is a leaf node and has a location of
  601.          *      {@link RegionLocation#INSIDE}
  602.          */
  603.         public boolean isInside() {
  604.             return isLeaf() && getLocation() == RegionLocation.INSIDE;
  605.         }

  607.         /** True if the node is a leaf node and has a location of {@link RegionLocation#OUTSIDE}.
  608.          * @return true if the node is a leaf node and has a location of
  609.          *      {@link RegionLocation#OUTSIDE}
  610.          */
  611.         public boolean isOutside() {
  612.             return isLeaf() && getLocation() == RegionLocation.OUTSIDE;
  613.         }

  615.         /** Insert a cut into this node, using the default region cut rule of
  616.          * {@link RegionCutRule#MINUS_INSIDE}.
  617.          * @param cutter the hyperplane to cut the node's region with
  618.          * @return true if the cutting hyperplane intersected the node's region, resulting
  619.          *      in the creation of new child nodes
  620.          * @see #insertCut(Hyperplane, RegionCutRule)
  621.          */
  622.         public boolean insertCut(final Hyperplane<P> cutter) {
  623.             return insertCut(cutter, DEFAULT_REGION_CUT_RULE);
  624.         }

  626.         /** Insert a cut into this node. If the given hyperplane intersects
  627.          * this node's region, then the node's cut is set to the {@link HyperplaneConvexSubset}
  628.          * representing the intersection, new plus and minus child leaf nodes
  629.          * are assigned, and true is returned. If the hyperplane does not intersect
  630.          * the node's region, then the node's cut and plus and minus child references
  631.          * are all set to null (ie, it becomes a leaf node) and false is returned. In
  632.          * either case, any existing cut and/or child nodes are removed by this method.
  633.          * @param cutter the hyperplane to cut the node's region with
  634.          * @param cutRule rule used to determine the region locations of newly created
  635.          *      child nodes
  636.          * @return true if the cutting hyperplane intersected the node's region, resulting
  637.          *      in the creation of new child nodes
  638.          */
  639.         public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
  640.             final AbstractRegionBSPTree<P, N> tree = getTree();
  641.             return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule));
  642.         }

  644.         /** Remove the cut from this node. Returns true if the node previously had a cut.
  645.          * @return true if the node had a cut before the call to this method
  646.          */
  647.         public boolean clearCut() {
  648.             return getTree().removeNodeCut(getSelf());
  649.         }

  651.         /** Cut this node with the given hyperplane. The same node is returned, regardless of
  652.          * the outcome of the cut operation. If the operation succeeded, then the node will
  653.          * have plus and minus child nodes.
  654.          * @param cutter the hyperplane to cut the node's region with
  655.          * @return this node
  656.          * @see #insertCut(Hyperplane)
  657.          */
  658.         public N cut(final Hyperplane<P> cutter) {
  659.             return cut(cutter, DEFAULT_REGION_CUT_RULE);
  660.         }

  662.         /** Cut this node with the given hyperplane, using {@code cutRule} to determine the region
  663.          * locations of any new child nodes. The same node is returned, regardless of
  664.          * the outcome of the cut operation. If the operation succeeded, then the node will
  665.          * have plus and minus child nodes.
  666.          * @param cutter the hyperplane to cut the node's region with
  667.          * @param cutRule rule used to determine the region locations of newly created
  668.          *      child nodes
  669.          * @return this node
  670.          * @see #insertCut(Hyperplane, RegionCutRule)
  671.          */
  672.         public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
  673.             this.insertCut(cutter, cutRule);

  675.             return getSelf();
  676.         }

  678.         /** Get the portion of the node's cut that lies on the boundary of the region.
  679.          * @return the portion of the node's cut that lies on the boundary of
  680.          *      the region
  681.          */
  682.         public RegionCutBoundary<P> getCutBoundary() {
  683.             if (!isLeaf()) {
  684.                 checkValid();

  686.                 if (cutBoundary == null) {
  687.                     cutBoundary = computeBoundary();
  688.                 }
  689.             }

  691.             return cutBoundary;
  692.         }

  694.         /** Compute the portion of the node's cut that lies on the boundary of the region.
  695.          * This method must only be called on internal nodes.
  696.          * @return object representing the portions of the node's cut that lie on the region's boundary
  697.          */
  698.         private RegionCutBoundary<P> computeBoundary() {
  699.             final HyperplaneConvexSubset<P> sub = getCut();

  701.             // find the portions of the node cut hyperplane subset that touch inside and
  702.             // outside cells in the minus sub-tree
  703.             final List<HyperplaneConvexSubset<P>> minusIn = new ArrayList<>();
  704.             final List<HyperplaneConvexSubset<P>> minusOut = new ArrayList<>();

  706.             characterizeHyperplaneSubset(sub, getMinus(), minusIn, minusOut);

  708.             final ArrayList<HyperplaneConvexSubset<P>> insideFacing = new ArrayList<>();
  709.             final ArrayList<HyperplaneConvexSubset<P>> outsideFacing = new ArrayList<>();

  711.             if (!minusIn.isEmpty()) {
  712.                 // Add to the boundary anything that touches an inside cell in the minus sub-tree
  713.                 // and an outside cell in the plus sub-tree. These portions are oriented with their
  714.                 // plus side pointing to the outside of the region.
  715.                 for (final HyperplaneConvexSubset<P> minusInFragment : minusIn) {
  716.                     characterizeHyperplaneSubset(minusInFragment, getPlus(), null, outsideFacing);
  717.                 }
  718.             }

  720.             if (!minusOut.isEmpty()) {
  721.                 // Add to the boundary anything that touches an outside cell in the minus sub-tree
  722.                 // and an inside cell in the plus sub-tree. These portions are oriented with their
  723.                 // plus side pointing to the inside of the region.
  724.                 for (final HyperplaneConvexSubset<P> minusOutFragment : minusOut) {
  725.                     characterizeHyperplaneSubset(minusOutFragment, getPlus(), insideFacing, null);
  726.                 }
  727.             }

  729.             insideFacing.trimToSize();
  730.             outsideFacing.trimToSize();

  732.             return new RegionCutBoundary<>(
  733.                     insideFacing.isEmpty() ? null : insideFacing,
  734.                     outsideFacing.isEmpty() ? null : outsideFacing);
  735.         }

  737.         /** Recursive method to characterize a hyperplane convex subset with respect to the region's
  738.          * boundaries.
  739.          * @param sub the hyperplane convex subset to characterize
  740.          * @param node the node to characterize the hyperplane convex subset against
  741.          * @param in list that will receive the portions of the subset that lie in the inside
  742.          *      of the region; may be null
  743.          * @param out list that will receive the portions of the subset that lie on the outside
  744.          *      of the region; may be null
  745.          */
  746.         private void characterizeHyperplaneSubset(final HyperplaneConvexSubset<P> sub,
  747.                 final AbstractRegionNode<P, N> node, final List<? super HyperplaneConvexSubset<P>> in,
  748.                 final List<? super HyperplaneConvexSubset<P>> out) {

  750.             if (sub != null) {
  751.                 if (node.isLeaf()) {
  752.                     if (node.isInside() && in != null) {
  753.                         in.add(sub);
  754.                     } else if (node.isOutside() && out != null) {
  755.                         out.add(sub);
  756.                     }
  757.                 } else {
  758.                     final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());

  760.                     // Continue further on down the subtree with the same subset if the
  761.                     // subset lies directly on the current node's cut
  762.                     if (split.getLocation() == SplitLocation.NEITHER) {
  763.                         characterizeHyperplaneSubset(sub, node.getPlus(), in, out);
  764.                         characterizeHyperplaneSubset(sub, node.getMinus(), in, out);
  765.                     } else {
  766.                         characterizeHyperplaneSubset(split.getPlus(), node.getPlus(), in, out);
  767.                         characterizeHyperplaneSubset(split.getMinus(), node.getMinus(), in, out);
  768.                     }
  769.                 }
  770.             }
  771.         }

  773.         /** {@inheritDoc} */
  774.         @Override
  775.         public String toString() {
  776.             final StringBuilder sb = new StringBuilder();
  777.             sb.append(this.getClass().getSimpleName())
  778.                 .append("[cut= ")
  779.                 .append(getCut())
  780.                 .append(", location= ")
  781.                 .append(getLocation())
  782.                 .append("]");

  784.             return sb.toString();
  785.         }

  787.         /** {@inheritDoc} */
  788.         @Override
  789.         protected void nodeInvalidated() {
  790.             super.nodeInvalidated();

  792.             // null any computed boundary value since it is no longer valid
  793.             cutBoundary = null;
  794.         }

  796.         /** Directly set the value of the location property for the node. No input validation
  797.          * is performed and the tree is not invalidated.
  798.          * @param locationValue the new location value for the node
  799.          * @see #setLocation(RegionLocation)
  800.          */
  801.         protected void setLocationValue(final RegionLocation locationValue) {
  802.             this.location = locationValue;
  803.         }
  804.     }

  806.     /** Class used to compute the point on the region's boundary that is closest to a target point.
  807.      * @param <P> Point implementation type
  808.      * @param <N> BSP tree node implementation type
  809.      */
  810.     protected static class BoundaryProjector<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  811.         extends ClosestFirstVisitor<P, N> {
  812.         /** The projected point. */
  813.         private P projected;

  815.         /** The current closest distance to the boundary found. */
  816.         private double minDist = -1.0;

  818.         /** Simple constructor.
  819.          * @param point the point to project onto the region's boundary
  820.          */
  821.         public BoundaryProjector(final P point) {
  822.             super(point);
  823.         }

  825.         /** {@inheritDoc} */
  826.         @Override
  827.         public Result visit(final N node) {
  828.             final P point = getTarget();

  830.             if (node.isInternal() && (minDist < 0.0 || isPossibleClosestCut(node.getCut(), point, minDist))) {
  831.                 final RegionCutBoundary<P> boundary = node.getCutBoundary();
  832.                 final P boundaryPt = boundary.closest(point);

  834.                 final double dist = boundaryPt.distance(point);
  835.                 final int cmp = Double.compare(dist, minDist);

  837.                 if (minDist < 0.0 || cmp < 0) {
  838.                     projected = boundaryPt;
  839.                     minDist = dist;
  840.                 } else if (cmp == 0) {
  841.                     // the two points are the _exact_ same distance from the reference point, so use
  842.                     // a separate method to disambiguate them
  843.                     projected = disambiguateClosestPoint(point, projected, boundaryPt);
  844.                 }
  845.             }

  847.             return Result.CONTINUE;
  848.         }

  850.         /** Return true if the given node cut is a possible candidate for containing the closest region
  851.          * boundary point to the target.
  852.          * @param cut the node cut to test
  853.          * @param target the target point being projected
  854.          * @param currentMinDist the smallest distance found so far to a region boundary; this value is guaranteed
  855.          *      to be non-negative
  856.          * @return true if the cut is a possible candidate for containing the closest region
  857.          *      boundary point to the target
  858.          */
  859.         protected boolean isPossibleClosestCut(final HyperplaneSubset<P> cut, final P target,
  860.                 final double currentMinDist) {
  861.             return Math.abs(cut.getHyperplane().offset(target)) <= currentMinDist;
  862.         }

  864.         /** Method used to determine which of points {@code a} and {@code b} should be considered
  865.          * as the "closest" point to {@code target} when the points are exactly equidistant.
  866.          * @param target the target point
  867.          * @param a first point to consider
  868.          * @param b second point to consider
  869.          * @return which of {@code a} or {@code b} should be considered as the one closest to
  870.          *      {@code target}
  871.          */
  872.         protected P disambiguateClosestPoint(final P target, final P a, final P b) {
  873.             return a;
  874.         }

  876.         /** Get the projected point on the region's boundary, or null if no point could be found.
  877.          * @return the projected point on the region's boundary
  878.          */
  879.         public P getProjected() {
  880.             return projected;
  881.         }
  882.     }

  884.     /** Class containing the primary size-related properties of a region. These properties
  885.      * are typically computed at the same time, so this class serves to encapsulate the result
  886.      * of the combined computation.
  887.      * @param <P> Point implementation type
  888.      */
  889.     protected static class RegionSizeProperties<P extends Point<P>> {
  890.         /** The size of the region. */
  891.         private final double size;

  893.         /** The centroid of the region. */
  894.         private final P centroid;

  896.         /** Simple constructor.
  897.          * @param size the region size
  898.          * @param centroid the region centroid
  899.          */
  900.         public RegionSizeProperties(final double size, final P centroid) {
  901.             this.size = size;
  902.             this.centroid = centroid;
  903.         }

  905.         /** Get the size of the region.
  906.          * @return the size of the region
  907.          */
  908.         public double getSize() {
  909.             return size;
  910.         }

  912.         /** Get the centroid of the region.
  913.          * @return the centroid of the region
  914.          */
  915.         public P getCentroid() {
  916.             return centroid;
  917.         }
  918.     }

  920.     /** Class containing the basic algorithm for merging region BSP trees.
  921.      * @param <P> Point implementation type
  922.      * @param <N> BSP tree node implementation type
  923.      */
  924.     private abstract static class RegionMergeOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  925.         extends AbstractBSPTreeMergeOperator<P, N> {

  927.         /** Merge two input trees, storing the output in the third. The output tree can be one of the
  928.          * input trees. The output tree is condensed before the method returns.
  929.          * @param inputTree1 first input tree
  930.          * @param inputTree2 second input tree
  931.          * @param outputTree the tree that will contain the result of the merge; may be one
  932.          *      of the input trees
  933.          */
  934.         public void apply(final AbstractRegionBSPTree<P, N> inputTree1, final AbstractRegionBSPTree<P, N> inputTree2,
  935.                 final AbstractRegionBSPTree<P, N> outputTree) {

  937.             this.performMerge(inputTree1, inputTree2, outputTree);

  939.             outputTree.condense();
  940.         }
  941.     }

  943.     /** Class for performing boolean union operations on region trees.
  944.      * @param <P> Point implementation type
  945.      * @param <N> BSP tree node implementation type
  946.      */
  947.     private static final class UnionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  948.         extends RegionMergeOperator<P, N> {

  950.         /** {@inheritDoc} */
  951.         @Override
  952.         protected N mergeLeaf(final N node1, final N node2) {
  953.             if (node1.isLeaf()) {
  954.                 return node1.isInside() ? node1 : node2;
  955.             }

  957.             // call again with flipped arguments
  958.             return mergeLeaf(node2, node1);
  959.         }
  960.     }

  962.     /** Class for performing boolean intersection operations on region trees.
  963.      * @param <P> Point implementation type
  964.      * @param <N> BSP tree node implementation type
  965.      */
  966.     private static final class IntersectionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  967.         extends RegionMergeOperator<P, N> {

  969.         /** {@inheritDoc} */
  970.         @Override
  971.         protected N mergeLeaf(final N node1, final N node2) {
  972.             if (node1.isLeaf()) {
  973.                 return node1.isInside() ? node2 : node1;
  974.             }

  976.             // call again with flipped arguments
  977.             return mergeLeaf(node2, node1);
  978.         }
  979.     }

  981.     /** Class for performing boolean difference operations on region trees.
  982.      * @param <P> Point implementation type
  983.      * @param <N> BSP tree node implementation type
  984.      */
  985.     private static final class DifferenceOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  986.         extends RegionMergeOperator<P, N> {

  988.         /** {@inheritDoc} */
  989.         @Override
  990.         protected N mergeLeaf(final N node1, final N node2) {
  991.             // a region is included if it belongs in tree1 and is not in tree2

  993.             if (node1.isInside()) {
  994.                 // this region is inside of tree1, so only include subregions that are
  995.                 // not in tree2, ie include everything in node2's complement
  996.                 final N output = outputSubtree(node2);
  997.                 output.getTree().complementRecursive(output);

  999.                 return output;
  1000.             } else if (node2.isInside()) {
  1001.                 // this region is inside of tree2 and so cannot be in the result region
  1002.                 final N output = outputNode();
  1003.                 output.setLocationValue(RegionLocation.OUTSIDE);

  1005.                 return output;
  1006.             }

  1008.             // this region is not in tree2, so we can include everything in tree1
  1009.             return node1;
  1010.         }
  1011.     }

  1013.     /** Class for performing boolean symmetric difference (xor) operations on region trees.
  1014.      * @param <P> Point implementation type
  1015.      * @param <N> BSP tree node implementation type
  1016.      */
  1017.     private static final class XorOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  1018.         extends RegionMergeOperator<P, N> {

  1020.         /** {@inheritDoc} */
  1021.         @Override
  1022.         protected N mergeLeaf(final N node1, final N node2) {
  1023.             // a region is included if it belongs in tree1 and is not in tree2 OR
  1024.             // it belongs in tree2 and is not in tree1

  1026.             if (node1.isLeaf()) {
  1027.                 if (node1.isInside()) {
  1028.                     // this region is inside node1, so only include subregions that are
  1029.                     // not in node2, ie include everything in node2's complement
  1030.                     final N output = outputSubtree(node2);
  1031.                     output.getTree().complementRecursive(output);

  1033.                     return output;
  1034.                 } else {
  1035.                     // this region is not in node1, so only include subregions that
  1036.                     // in node2
  1037.                     return node2;
  1038.                 }
  1039.             }

  1041.             // the operation is symmetric, so perform the same operation but with the
  1042.             // nodes flipped
  1043.             return mergeLeaf(node2, node1);
  1044.         }
  1045.     }

  1047.     /** Internal class used to perform tree condense operations.
  1048.      * @param <P> Point implementation type
  1049.      * @param <N> BSP tree node implementation type
  1050.      */
  1051.     private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> {
  1052.         /** Flag set to true if the tree was modified during the operation. */
  1053.         private boolean modifiedTree;

  1055.         /** Condense the nodes in the subtree rooted at the given node. Redundant child nodes are
  1056.          * removed. The tree is invalidated if the tree structure was modified.
  1057.          * @param node the root node of the subtree to condense
  1058.          * @return true if the tree was modified.
  1059.          */
  1060.         boolean condense(final N node) {
  1061.             modifiedTree = false;

  1063.             condenseRecursive(node);

  1065.             return modifiedTree;
  1066.         }

  1068.         /** Recursively condense nodes that have children with homogenous location attributes
  1069.          * (eg, both inside, both outside) into single nodes.
  1070.          * @param node the root of the subtree to condense
  1071.          * @return the location of the successfully condensed subtree or null if no condensing was
  1072.          *      able to be performed
  1073.          */
  1074.         private RegionLocation condenseRecursive(final N node) {
  1075.             if (node.isLeaf()) {
  1076.                 return node.getLocation();
  1077.             }

  1079.             final RegionLocation minusLocation = condenseRecursive(node.getMinus());
  1080.             final RegionLocation plusLocation = condenseRecursive(node.getPlus());

  1082.             if (minusLocation == plusLocation && minusLocation != null) {
  1083.                 node.setLocationValue(minusLocation);
  1084.                 node.clearCut();

  1086.                 modifiedTree = true;

  1088.                 return minusLocation;
  1089.             }

  1091.             return null;
  1092.         }
  1093.     }

  1095.     /** Class that iterates over the boundary hyperplane convex subsets from a set of region nodes.
  1096.      * @param <P> Point implementation type
  1097.      * @param <C> Boundary hyperplane convex subset implementation type
  1098.      * @param <N> BSP tree node implementation type
  1099.      */
  1100.     private static final class RegionBoundaryIterator<
  1101.             P extends Point<P>,
  1102.             C extends HyperplaneConvexSubset<P>,
  1103.             N extends AbstractRegionNode<P, N>>
  1104.         extends IteratorTransform<N, C> {

  1106.         /** Function that converts from the convex subset type to the output type. */
  1107.         private final Function<? super HyperplaneConvexSubset<P>, C> typeConverter;

  1109.         /** Simple constructor.
  1110.          * @param inputIterator iterator that will provide all nodes in the tree
  1111.          * @param typeConverter function that converts from the convex subset type to the output type
  1112.          */
  1113.         RegionBoundaryIterator(final Iterator<N> inputIterator,
  1114.                 final Function<? super HyperplaneConvexSubset<P>, C> typeConverter) {
  1115.             super(inputIterator);

  1117.             this.typeConverter = typeConverter;
  1118.         }

  1120.         /** {@inheritDoc} */
  1121.         @Override
  1122.         protected void acceptInput(final N input) {
  1123.             if (input.isInternal()) {
  1124.                 final RegionCutBoundary<P> cutBoundary = input.getCutBoundary();

  1126.                 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getOutsideFacing()) {
  1127.                     addOutput(typeConverter.apply(boundary));
  1128.                 }

  1130.                 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getInsideFacing()) {
  1131.                     final HyperplaneConvexSubset<P> reversed = boundary.reverse();

  1133.                     addOutput(typeConverter.apply(reversed));
  1134.                 }
  1135.             }
  1136.         }
  1137.     }
  1138. }
Created with JaCoCo 0.8.5.201910111838