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;

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

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

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

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

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

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

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

  56.     /** Construct a new region will the given boolean determining whether or not the
  57.      * region will be full (including the entire space) or empty (excluding the entire
  58.      * space).
  59.      * @param full if true, the region will cover the entire space, otherwise it will
  60.      *      be empty
  61.      */
  62.     protected AbstractRegionBSPTree(final boolean full) {
  63.         getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
  64.     }

  65.     /** {@inheritDoc} */
  66.     @Override
  67.     public boolean isEmpty() {
  68.         return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.INSIDE);
  69.     }

  70.     /** {@inheritDoc} */
  71.     @Override
  72.     public boolean isFull() {
  73.         return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.OUTSIDE);
  74.     }

  75.     /** Return true if any node in the subtree rooted at the given node has a location with the
  76.      * given value.
  77.      * @param node the node at the root of the subtree to search
  78.      * @param location the location to find
  79.      * @return true if any node in the subtree has the given location
  80.      */
  81.     private boolean hasNodeWithLocationRecursive(final AbstractRegionNode<P, N> node, final RegionLocation location) {
  82.         if (node == null) {
  83.             return false;
  84.         }

  85.         return node.getLocation() == location ||
  86.                 hasNodeWithLocationRecursive(node.getMinus(), location) ||
  87.                 hasNodeWithLocationRecursive(node.getPlus(), location);
  88.     }

  89.     /** Modify this instance so that it contains the entire space.
  90.      * @see #isFull()
  91.      */
  92.     public void setFull() {
  93.         final N root = getRoot();

  94.         root.clearCut();
  95.         root.setLocationValue(RegionLocation.INSIDE);
  96.     }

  97.     /** Modify this instance so that is is completely empty.
  98.      * @see #isEmpty()
  99.      */
  100.     public void setEmpty() {
  101.         final N root = getRoot();

  102.         root.clearCut();
  103.         root.setLocationValue(RegionLocation.OUTSIDE);
  104.     }

  105.     /** {@inheritDoc} */
  106.     @Override
  107.     public double getSize() {
  108.         return getRegionSizeProperties().getSize();
  109.     }

  110.     /** {@inheritDoc} */
  111.     @Override
  112.     public double getBoundarySize() {
  113.         if (boundarySize < 0) {
  114.             double sum = 0.0;

  115.             RegionCutBoundary<P> boundary;
  116.             for (final AbstractRegionNode<P, N> node : nodes()) {
  117.                 boundary = node.getCutBoundary();
  118.                 if (boundary != null) {
  119.                     sum += boundary.getSize();
  120.                 }
  121.             }

  122.             boundarySize = sum;
  123.         }

  124.         return boundarySize;
  125.     }

  126.     /** Insert a hyperplane subset into the tree, using the default {@link RegionCutRule} of
  127.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  128.      * @param sub the hyperplane subset to insert into the tree
  129.      */
  130.     public void insert(final HyperplaneSubset<P> sub) {
  131.         insert(sub, DEFAULT_REGION_CUT_RULE);
  132.     }

  133.     /** Insert a hyperplane subset into the tree.
  134.      * @param sub the hyperplane subset to insert into the tree
  135.      * @param cutRule rule used to determine the region locations of new child nodes
  136.      */
  137.     public void insert(final HyperplaneSubset<P> sub, final RegionCutRule cutRule) {
  138.         insert(sub.toConvex(), cutRule);
  139.     }

  140.     /** Insert a hyperplane convex subset into the tree, using the default {@link RegionCutRule} of
  141.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  142.      * @param convexSub the hyperplane convex subset to insert into the tree
  143.      */
  144.     public void insert(final HyperplaneConvexSubset<P> convexSub) {
  145.         insert(convexSub, DEFAULT_REGION_CUT_RULE);
  146.     }

  147.     /** Insert a hyperplane convex subset into the tree.
  148.      * @param convexSub the hyperplane convex subset to insert into the tree
  149.      * @param cutRule rule used to determine the region locations of new child nodes
  150.      */
  151.     public void insert(final HyperplaneConvexSubset<P> convexSub, final RegionCutRule cutRule) {
  152.         insert(convexSub, getSubtreeInitializer(cutRule));
  153.     }

  154.     /** Insert a set of hyperplane convex subsets into the tree, using the default {@link RegionCutRule} of
  155.      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  156.      * @param convexSubs iterable containing a collection of hyperplane convex subsets
  157.      *      to insert into the tree
  158.      */
  159.     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs) {
  160.         insert(convexSubs, DEFAULT_REGION_CUT_RULE);
  161.     }

  162.     /** Insert a set of hyperplane convex subsets into the tree.
  163.      * @param convexSubs iterable containing a collection of hyperplane convex subsets
  164.      *      to insert into the tree
  165.      * @param cutRule rule used to determine the region locations of new child nodes
  166.      */
  167.     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, final RegionCutRule cutRule) {
  168.         for (final HyperplaneConvexSubset<P> convexSub : convexSubs) {
  169.             insert(convexSub, cutRule);
  170.         }
  171.     }

  172.     /** Insert all hyperplane convex subsets from the given source into the tree, using the default
  173.      * {@link RegionCutRule} of {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
  174.      * @param boundarySrc source of boundary hyperplane subsets to insert
  175.      *      into the tree
  176.      */
  177.     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc) {
  178.         insert(boundarySrc, DEFAULT_REGION_CUT_RULE);
  179.     }

  180.     /** Insert all hyperplane convex subsets from the given source into the tree.
  181.      * @param boundarySrc source of boundary hyperplane subsets to insert
  182.      *      into the tree
  183.      * @param cutRule rule used to determine the region locations of new child nodes
  184.      */
  185.     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc,
  186.             final RegionCutRule cutRule) {
  187.         try (Stream<? extends HyperplaneConvexSubset<P>> stream = boundarySrc.boundaryStream()) {
  188.             stream.forEach(c -> insert(c, cutRule));
  189.         }
  190.     }

  191.     /** Get the subtree initializer to use for the given region cut rule.
  192.      * @param cutRule the cut rule to get an initializer for
  193.      * @return the subtree initializer for the given region cut rule
  194.      */
  195.     protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) {
  196.         switch (cutRule) {
  197.         case INHERIT:
  198.             return root -> {
  199.                 final RegionLocation rootLoc = root.getLocation();

  200.                 root.getMinus().setLocationValue(rootLoc);
  201.                 root.getPlus().setLocationValue(rootLoc);
  202.             };
  203.         case PLUS_INSIDE:
  204.             return root -> {
  205.                 root.getMinus().setLocationValue(RegionLocation.OUTSIDE);
  206.                 root.getPlus().setLocationValue(RegionLocation.INSIDE);
  207.             };
  208.         default:
  209.             return root -> {
  210.                 root.getMinus().setLocationValue(RegionLocation.INSIDE);
  211.                 root.getPlus().setLocationValue(RegionLocation.OUTSIDE);
  212.             };
  213.         }
  214.     }

  215.     /** Return an {@link Iterable} for iterating over the boundaries of the region.
  216.      * Each boundary is oriented such that its plus side points to the outside of the
  217.      * region. The exact ordering of the boundaries is determined by the internal structure
  218.      * of the tree.
  219.      * @return an {@link Iterable} for iterating over the boundaries of the region
  220.      * @see #getBoundaries()
  221.      */
  222.     public Iterable<? extends HyperplaneConvexSubset<P>> boundaries() {
  223.         return createBoundaryIterable(Function.identity());
  224.     }

  225.     /** Internal method for creating the iterable instances used to iterate the region boundaries.
  226.      * @param typeConverter function to convert the generic hyperplane subset type into
  227.      *      the type specific for this tree
  228.      * @param <C> HyperplaneConvexSubset implementation type
  229.      * @return an iterable to iterating the region boundaries
  230.      */
  231.     protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(
  232.             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {

  233.         return () -> new RegionBoundaryIterator<>(
  234.                 getRoot().nodes().iterator(),
  235.                 typeConverter);
  236.     }

  237.     /** Return a list containing the boundaries of the region. Each boundary is oriented such
  238.      * that its plus side points to the outside of the region. The exact ordering of
  239.      * the boundaries is determined by the internal structure of the tree.
  240.      * @return a list of the boundaries of the region
  241.      */
  242.     public List<? extends HyperplaneConvexSubset<P>> getBoundaries() {
  243.         return createBoundaryList(Function.identity());
  244.     }

  245.     /** Internal method for creating a list of the region boundaries.
  246.      * @param typeConverter function to convert the generic convex subset type into
  247.      *      the type specific for this tree
  248.      * @param <C> HyperplaneConvexSubset implementation type
  249.      * @return a list of the region boundaries
  250.      */
  251.     protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(
  252.             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {

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

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

  256.         return result;
  257.     }

  258.     /** {@inheritDoc} */
  259.     @Override
  260.     public P project(final P pt) {
  261.         final BoundaryProjector<P, N> projector = new BoundaryProjector<>(pt);
  262.         accept(projector);

  263.         return projector.getProjected();
  264.     }

  265.     /** {@inheritDoc} */
  266.     @Override
  267.     public P getCentroid() {
  268.         return getRegionSizeProperties().getCentroid();
  269.     }

  270.     /** Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses
  271.      * should call this method with two instantiated trees of the correct type.
  272.      * @param splitter splitting hyperplane
  273.      * @param minus tree that will contain the minus side of the split result
  274.      * @param plus tree that will contain the plus side of the split result
  275.      * @param <T> Tree implementation type
  276.      * @return result of splitting this tree with the given hyperplane
  277.      */
  278.     protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(final Hyperplane<P> splitter,
  279.             final T minus, final T plus) {

  280.         splitIntoTrees(splitter, minus, plus);

  281.         T splitMinus = null;
  282.         T splitPlus = null;

  283.         if (minus != null) {
  284.             minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE);
  285.             minus.condense();

  286.             splitMinus = minus.isEmpty() ? null : minus;
  287.         }
  288.         if (plus != null) {
  289.             plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE);
  290.             plus.condense();

  291.             splitPlus = plus.isEmpty() ? null : plus;
  292.         }

  293.         return new Split<>(splitMinus, splitPlus);
  294.     }

  295.     /** Get the size-related properties for the region. The value is computed
  296.      * lazily and cached.
  297.      * @return the size-related properties for the region
  298.      */
  299.     protected RegionSizeProperties<P> getRegionSizeProperties() {
  300.         if (regionSizeProperties == null) {
  301.             regionSizeProperties = computeRegionSizeProperties();
  302.         }

  303.         return regionSizeProperties;
  304.     }

  305.     /** Compute the size-related properties of the region.
  306.      * @return object containing size properties for the region
  307.      */
  308.     protected abstract RegionSizeProperties<P> computeRegionSizeProperties();

  309.     /** {@inheritDoc}
  310.      *
  311.      * <p>If the point is {@link org.apache.commons.geometry.core.Spatial#isNaN() NaN}, then
  312.      * {@link RegionLocation#OUTSIDE} is returned.</p>
  313.      */
  314.     @Override
  315.     public RegionLocation classify(final P point) {
  316.         if (point.isNaN()) {
  317.             return RegionLocation.OUTSIDE;
  318.         }

  319.         return classifyRecursive(getRoot(), point);
  320.     }

  321.     /** Recursively classify a point with respect to the region.
  322.      * @param node the node to classify against
  323.      * @param point the point to classify
  324.      * @return the classification of the point with respect to the region rooted
  325.      *      at the given node
  326.      */
  327.     private RegionLocation classifyRecursive(final AbstractRegionNode<P, N> node, final P point) {
  328.         if (node.isLeaf()) {
  329.             // the point is in a leaf, so the classification is just the leaf location
  330.             return node.getLocation();
  331.         } else {
  332.             final HyperplaneLocation cutLoc = node.getCutHyperplane().classify(point);

  333.             if (cutLoc == HyperplaneLocation.MINUS) {
  334.                 return classifyRecursive(node.getMinus(), point);
  335.             } else if (cutLoc == HyperplaneLocation.PLUS) {
  336.                 return classifyRecursive(node.getPlus(), point);
  337.             } else {
  338.                 // the point is on the cut boundary; classify against both child
  339.                 // subtrees and see if we end up with the same result or not
  340.                 final RegionLocation minusLoc = classifyRecursive(node.getMinus(), point);
  341.                 final RegionLocation plusLoc = classifyRecursive(node.getPlus(), point);

  342.                 if (minusLoc == plusLoc) {
  343.                     return minusLoc;
  344.                 }
  345.                 return RegionLocation.BOUNDARY;
  346.             }
  347.         }
  348.     }

  349.     /** Change this region into its complement. All inside nodes become outside
  350.      * nodes and vice versa. The orientations of the node cuts are not modified.
  351.      */
  352.     public void complement() {
  353.         complementRecursive(getRoot());
  354.     }

  355.     /** Set this instance to be the complement of the given tree. The argument
  356.      * is not modified.
  357.      * @param tree the tree to become the complement of
  358.      */
  359.     public void complement(final AbstractRegionBSPTree<P, N> tree) {
  360.         copySubtree(tree.getRoot(), getRoot());
  361.         complementRecursive(getRoot());
  362.     }

  363.     /** Recursively switch all inside nodes to outside nodes and vice versa.
  364.      * @param node the node at the root of the subtree to switch
  365.      */
  366.     private void complementRecursive(final AbstractRegionNode<P, N> node) {
  367.         if (node != null) {
  368.             final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ?
  369.                     RegionLocation.OUTSIDE :
  370.                     RegionLocation.INSIDE;

  371.             node.setLocationValue(newLoc);

  372.             complementRecursive(node.getMinus());
  373.             complementRecursive(node.getPlus());
  374.         }
  375.     }

  376.     /** Compute the union of this instance and the given region, storing the result back in
  377.      * this instance. The argument is not modified.
  378.      * @param other the tree to compute the union with
  379.      */
  380.     public void union(final AbstractRegionBSPTree<P, N> other) {
  381.         new UnionOperator<P, N>().apply(this, other, this);
  382.     }

  383.     /** Compute the union of the two regions passed as arguments and store the result in
  384.      * this instance. Any nodes currently existing in this instance are removed.
  385.      * @param a first argument to the union operation
  386.      * @param b second argument to the union operation
  387.      */
  388.     public void union(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  389.         new UnionOperator<P, N>().apply(a, b, this);
  390.     }

  391.     /** Compute the intersection of this instance and the given region, storing the result back in
  392.      * this instance. The argument is not modified.
  393.      * @param other the tree to compute the intersection with
  394.      */
  395.     public void intersection(final AbstractRegionBSPTree<P, N> other) {
  396.         new IntersectionOperator<P, N>().apply(this, other, this);
  397.     }

  398.     /** Compute the intersection of the two regions passed as arguments and store the result in
  399.      * this instance. Any nodes currently existing in this instance are removed.
  400.      * @param a first argument to the intersection operation
  401.      * @param b second argument to the intersection operation
  402.      */
  403.     public void intersection(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  404.         new IntersectionOperator<P, N>().apply(a, b, this);
  405.     }

  406.     /** Compute the difference of this instance and the given region, storing the result back in
  407.      * this instance. The argument is not modified.
  408.      * @param other the tree to compute the difference with
  409.      */
  410.     public void difference(final AbstractRegionBSPTree<P, N> other) {
  411.         new DifferenceOperator<P, N>().apply(this, other, this);
  412.     }

  413.     /** Compute the difference of the two regions passed as arguments and store the result in
  414.      * this instance. Any nodes currently existing in this instance are removed.
  415.      * @param a first argument to the difference operation
  416.      * @param b second argument to the difference operation
  417.      */
  418.     public void difference(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  419.         new DifferenceOperator<P, N>().apply(a, b, this);
  420.     }

  421.     /** Compute the symmetric difference (xor) of this instance and the given region, storing the result back in
  422.      * this instance. The argument is not modified.
  423.      * @param other the tree to compute the symmetric difference with
  424.      */
  425.     public void xor(final AbstractRegionBSPTree<P, N> other) {
  426.         new XorOperator<P, N>().apply(this, other, this);
  427.     }

  428.     /** Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in
  429.      * this instance. Any nodes currently existing in this instance are removed.
  430.      * @param a first argument to the symmetric difference operation
  431.      * @param b second argument to the symmetric difference operation
  432.      */
  433.     public void xor(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
  434.         new XorOperator<P, N>().apply(a, b, this);
  435.     }

  436.     /** Condense this tree by removing redundant subtrees, returning true if the
  437.      * tree structure was modified.
  438.      *
  439.      * <p>This operation can be used to reduce the total number of nodes in the
  440.      * tree after performing node manipulations. For example, if two sibling leaf
  441.      * nodes both represent the same {@link RegionLocation}, then there is no reason
  442.      * from the perspective of the geometric region to retain both nodes. They are
  443.      * therefore both merged into their parent node. This method performs this
  444.      * simplification process.
  445.      * </p>
  446.      * @return true if the tree structure was modified, otherwise false
  447.      */
  448.     public boolean condense() {
  449.         return new Condenser<P, N>().condense(getRoot());
  450.     }

  451.     /** {@inheritDoc} */
  452.     @Override
  453.     protected void copyNodeProperties(final N src, final N dst) {
  454.         dst.setLocationValue(src.getLocation());
  455.     }

  456.     /** {@inheritDoc} */
  457.     @Override
  458.     protected void invalidate() {
  459.         super.invalidate();

  460.         // clear cached region properties
  461.         boundarySize = UNKNOWN_SIZE;
  462.         regionSizeProperties = null;
  463.     }

  464.     /** {@link BSPTree.Node} implementation for use with {@link AbstractRegionBSPTree}s.
  465.      * @param <P> Point implementation type
  466.      * @param <N> BSP tree node implementation type
  467.      */
  468.     public abstract static class AbstractRegionNode<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  469.         extends AbstractBSPTree.AbstractNode<P, N> {
  470.         /** The location for the node. This will only be set on leaf nodes. */
  471.         private RegionLocation location;

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

  476.         /** Simple constructor.
  477.          * @param tree owning tree instance
  478.          */
  479.         protected AbstractRegionNode(final AbstractBSPTree<P, N> tree) {
  480.             super(tree);
  481.         }

  482.         /** {@inheritDoc} */
  483.         @Override
  484.         public AbstractRegionBSPTree<P, N> getTree() {
  485.             // cast to our parent tree type
  486.             return (AbstractRegionBSPTree<P, N>) super.getTree();
  487.         }

  488.         /** Get the location property of the node. Only the locations of leaf nodes are meaningful
  489.          * as they relate to the region represented by the BSP tree. For example, changing
  490.          * the location of an internal node will only affect the geometric properties
  491.          * of the region if the node later becomes a leaf node.
  492.          * @return the location of the node
  493.          */
  494.         public RegionLocation getLocation() {
  495.             return location;
  496.         }

  497.         /** Set the location property for the node. If the location is changed, the tree is
  498.          * invalidated.
  499.          *
  500.          * <p>Only the locations of leaf nodes are meaningful
  501.          * as they relate to the region represented by the BSP tree. For example, changing
  502.          * the location of an internal node will only affect the geometric properties
  503.          * of the region if the node later becomes a leaf node.</p>
  504.          * @param location the location for the node
  505.          * @throws IllegalArgumentException if {@code location} is not one of
  506.          *      {@link RegionLocation#INSIDE INSIDE} or {@link RegionLocation#OUTSIDE OUTSIDE}
  507.          */
  508.         public void setLocation(final RegionLocation location) {
  509.             if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) {
  510.                 throw new IllegalArgumentException("Invalid node location: " + location);
  511.             }
  512.             if (this.location != location) {
  513.                 this.location = location;

  514.                 getTree().invalidate();
  515.             }
  516.         }

  517.         /** True if the node is a leaf node and has a location of {@link RegionLocation#INSIDE}.
  518.          * @return true if the node is a leaf node and has a location of
  519.          *      {@link RegionLocation#INSIDE}
  520.          */
  521.         public boolean isInside() {
  522.             return isLeaf() && getLocation() == RegionLocation.INSIDE;
  523.         }

  524.         /** True if the node is a leaf node and has a location of {@link RegionLocation#OUTSIDE}.
  525.          * @return true if the node is a leaf node and has a location of
  526.          *      {@link RegionLocation#OUTSIDE}
  527.          */
  528.         public boolean isOutside() {
  529.             return isLeaf() && getLocation() == RegionLocation.OUTSIDE;
  530.         }

  531.         /** Insert a cut into this node, using the default region cut rule of
  532.          * {@link RegionCutRule#MINUS_INSIDE}.
  533.          * @param cutter the hyperplane to cut the node's region with
  534.          * @return true if the cutting hyperplane intersected the node's region, resulting
  535.          *      in the creation of new child nodes
  536.          * @see #insertCut(Hyperplane, RegionCutRule)
  537.          */
  538.         public boolean insertCut(final Hyperplane<P> cutter) {
  539.             return insertCut(cutter, DEFAULT_REGION_CUT_RULE);
  540.         }

  541.         /** Insert a cut into this node. If the given hyperplane intersects
  542.          * this node's region, then the node's cut is set to the {@link HyperplaneConvexSubset}
  543.          * representing the intersection, new plus and minus child leaf nodes
  544.          * are assigned, and true is returned. If the hyperplane does not intersect
  545.          * the node's region, then the node's cut and plus and minus child references
  546.          * are all set to null (ie, it becomes a leaf node) and false is returned. In
  547.          * either case, any existing cut and/or child nodes are removed by this method.
  548.          * @param cutter the hyperplane to cut the node's region with
  549.          * @param cutRule rule used to determine the region locations of newly created
  550.          *      child nodes
  551.          * @return true if the cutting hyperplane intersected the node's region, resulting
  552.          *      in the creation of new child nodes
  553.          */
  554.         public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
  555.             final AbstractRegionBSPTree<P, N> tree = getTree();
  556.             return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule));
  557.         }

  558.         /** Remove the cut from this node. Returns true if the node previously had a cut.
  559.          * @return true if the node had a cut before the call to this method
  560.          */
  561.         public boolean clearCut() {
  562.             return getTree().removeNodeCut(getSelf());
  563.         }

  564.         /** Cut this node with the given hyperplane. The same node is returned, regardless of
  565.          * the outcome of the cut operation. If the operation succeeded, then the node will
  566.          * have plus and minus child nodes.
  567.          * @param cutter the hyperplane to cut the node's region with
  568.          * @return this node
  569.          * @see #insertCut(Hyperplane)
  570.          */
  571.         public N cut(final Hyperplane<P> cutter) {
  572.             return cut(cutter, DEFAULT_REGION_CUT_RULE);
  573.         }

  574.         /** Cut this node with the given hyperplane, using {@code cutRule} to determine the region
  575.          * locations of any new child nodes. The same node is returned, regardless of
  576.          * the outcome of the cut operation. If the operation succeeded, then the node will
  577.          * have plus and minus child nodes.
  578.          * @param cutter the hyperplane to cut the node's region with
  579.          * @param cutRule rule used to determine the region locations of newly created
  580.          *      child nodes
  581.          * @return this node
  582.          * @see #insertCut(Hyperplane, RegionCutRule)
  583.          */
  584.         public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
  585.             this.insertCut(cutter, cutRule);

  586.             return getSelf();
  587.         }

  588.         /** Get the portion of the node's cut that lies on the boundary of the region.
  589.          * @return the portion of the node's cut that lies on the boundary of
  590.          *      the region
  591.          */
  592.         public RegionCutBoundary<P> getCutBoundary() {
  593.             if (!isLeaf()) {
  594.                 checkValid();

  595.                 if (cutBoundary == null) {
  596.                     cutBoundary = computeBoundary();
  597.                 }
  598.             }

  599.             return cutBoundary;
  600.         }

  601.         /** Compute the portion of the node's cut that lies on the boundary of the region.
  602.          * This method must only be called on internal nodes.
  603.          * @return object representing the portions of the node's cut that lie on the region's boundary
  604.          */
  605.         private RegionCutBoundary<P> computeBoundary() {
  606.             final HyperplaneConvexSubset<P> sub = getCut();

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

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

  612.             final ArrayList<HyperplaneConvexSubset<P>> insideFacing = new ArrayList<>();
  613.             final ArrayList<HyperplaneConvexSubset<P>> outsideFacing = new ArrayList<>();

  614.             if (!minusIn.isEmpty()) {
  615.                 // Add to the boundary anything that touches an inside cell in the minus sub-tree
  616.                 // and an outside cell in the plus sub-tree. These portions are oriented with their
  617.                 // plus side pointing to the outside of the region.
  618.                 for (final HyperplaneConvexSubset<P> minusInFragment : minusIn) {
  619.                     characterizeHyperplaneSubset(minusInFragment, getPlus(), null, outsideFacing);
  620.                 }
  621.             }

  622.             if (!minusOut.isEmpty()) {
  623.                 // Add to the boundary anything that touches an outside cell in the minus sub-tree
  624.                 // and an inside cell in the plus sub-tree. These portions are oriented with their
  625.                 // plus side pointing to the inside of the region.
  626.                 for (final HyperplaneConvexSubset<P> minusOutFragment : minusOut) {
  627.                     characterizeHyperplaneSubset(minusOutFragment, getPlus(), insideFacing, null);
  628.                 }
  629.             }

  630.             insideFacing.trimToSize();
  631.             outsideFacing.trimToSize();

  632.             return new RegionCutBoundary<>(
  633.                     insideFacing.isEmpty() ? null : insideFacing,
  634.                     outsideFacing.isEmpty() ? null : outsideFacing);
  635.         }

  636.         /** Recursive method to characterize a hyperplane convex subset with respect to the region's
  637.          * boundaries.
  638.          * @param sub the hyperplane convex subset to characterize
  639.          * @param node the node to characterize the hyperplane convex subset against
  640.          * @param in list that will receive the portions of the subset that lie in the inside
  641.          *      of the region; may be null
  642.          * @param out list that will receive the portions of the subset that lie on the outside
  643.          *      of the region; may be null
  644.          */
  645.         private void characterizeHyperplaneSubset(final HyperplaneConvexSubset<P> sub,
  646.                 final AbstractRegionNode<P, N> node, final List<? super HyperplaneConvexSubset<P>> in,
  647.                 final List<? super HyperplaneConvexSubset<P>> out) {

  648.             if (sub != null) {
  649.                 if (node.isLeaf()) {
  650.                     if (node.isInside() && in != null) {
  651.                         in.add(sub);
  652.                     } else if (node.isOutside() && out != null) {
  653.                         out.add(sub);
  654.                     }
  655.                 } else {
  656.                     final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());

  657.                     // Continue further on down the subtree with the same subset if the
  658.                     // subset lies directly on the current node's cut
  659.                     if (split.getLocation() == SplitLocation.NEITHER) {
  660.                         characterizeHyperplaneSubset(sub, node.getPlus(), in, out);
  661.                         characterizeHyperplaneSubset(sub, node.getMinus(), in, out);
  662.                     } else {
  663.                         characterizeHyperplaneSubset(split.getPlus(), node.getPlus(), in, out);
  664.                         characterizeHyperplaneSubset(split.getMinus(), node.getMinus(), in, out);
  665.                     }
  666.                 }
  667.             }
  668.         }

  669.         /** {@inheritDoc} */
  670.         @Override
  671.         public String toString() {
  672.             final StringBuilder sb = new StringBuilder();
  673.             sb.append(this.getClass().getSimpleName())
  674.                 .append("[cut= ")
  675.                 .append(getCut())
  676.                 .append(", location= ")
  677.                 .append(getLocation())
  678.                 .append("]");

  679.             return sb.toString();
  680.         }

  681.         /** {@inheritDoc} */
  682.         @Override
  683.         protected void nodeInvalidated() {
  684.             super.nodeInvalidated();

  685.             // null any computed boundary value since it is no longer valid
  686.             cutBoundary = null;
  687.         }

  688.         /** Directly set the value of the location property for the node. No input validation
  689.          * is performed and the tree is not invalidated.
  690.          * @param locationValue the new location value for the node
  691.          * @see #setLocation(RegionLocation)
  692.          */
  693.         protected void setLocationValue(final RegionLocation locationValue) {
  694.             this.location = locationValue;
  695.         }
  696.     }

  697.     /** Class used to compute the point on the region's boundary that is closest to a target point.
  698.      * @param <P> Point implementation type
  699.      * @param <N> BSP tree node implementation type
  700.      */
  701.     protected static class BoundaryProjector<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  702.         extends ClosestFirstVisitor<P, N> {
  703.         /** The projected point. */
  704.         private P projected;

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

  707.         /** Simple constructor.
  708.          * @param point the point to project onto the region's boundary
  709.          */
  710.         public BoundaryProjector(final P point) {
  711.             super(point);
  712.         }

  713.         /** {@inheritDoc} */
  714.         @Override
  715.         public Result visit(final N node) {
  716.             final P point = getTarget();

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

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

  722.                 if (minDist < 0.0 || cmp < 0) {
  723.                     projected = boundaryPt;
  724.                     minDist = dist;
  725.                 } else if (cmp == 0) {
  726.                     // the two points are the _exact_ same distance from the reference point, so use
  727.                     // a separate method to disambiguate them
  728.                     projected = disambiguateClosestPoint(point, projected, boundaryPt);
  729.                 }
  730.             }

  731.             return Result.CONTINUE;
  732.         }

  733.         /** Return true if the given node cut is a possible candidate for containing the closest region
  734.          * boundary point to the target.
  735.          * @param cut the node cut to test
  736.          * @param target the target point being projected
  737.          * @param currentMinDist the smallest distance found so far to a region boundary; this value is guaranteed
  738.          *      to be non-negative
  739.          * @return true if the cut is a possible candidate for containing the closest region
  740.          *      boundary point to the target
  741.          */
  742.         protected boolean isPossibleClosestCut(final HyperplaneSubset<P> cut, final P target,
  743.                 final double currentMinDist) {
  744.             return Math.abs(cut.getHyperplane().offset(target)) <= currentMinDist;
  745.         }

  746.         /** Method used to determine which of points {@code a} and {@code b} should be considered
  747.          * as the "closest" point to {@code target} when the points are exactly equidistant.
  748.          * @param target the target point
  749.          * @param a first point to consider
  750.          * @param b second point to consider
  751.          * @return which of {@code a} or {@code b} should be considered as the one closest to
  752.          *      {@code target}
  753.          */
  754.         protected P disambiguateClosestPoint(final P target, final P a, final P b) {
  755.             return a;
  756.         }

  757.         /** Get the projected point on the region's boundary, or null if no point could be found.
  758.          * @return the projected point on the region's boundary
  759.          */
  760.         public P getProjected() {
  761.             return projected;
  762.         }
  763.     }

  764.     /** Class containing the primary size-related properties of a region. These properties
  765.      * are typically computed at the same time, so this class serves to encapsulate the result
  766.      * of the combined computation.
  767.      * @param <P> Point implementation type
  768.      */
  769.     protected static class RegionSizeProperties<P extends Point<P>> {
  770.         /** The size of the region. */
  771.         private final double size;

  772.         /** The centroid of the region. */
  773.         private final P centroid;

  774.         /** Simple constructor.
  775.          * @param size the region size
  776.          * @param centroid the region centroid
  777.          */
  778.         public RegionSizeProperties(final double size, final P centroid) {
  779.             this.size = size;
  780.             this.centroid = centroid;
  781.         }

  782.         /** Get the size of the region.
  783.          * @return the size of the region
  784.          */
  785.         public double getSize() {
  786.             return size;
  787.         }

  788.         /** Get the centroid of the region.
  789.          * @return the centroid of the region
  790.          */
  791.         public P getCentroid() {
  792.             return centroid;
  793.         }
  794.     }

  795.     /** Class containing the basic algorithm for merging region BSP trees.
  796.      * @param <P> Point implementation type
  797.      * @param <N> BSP tree node implementation type
  798.      */
  799.     private abstract static class RegionMergeOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  800.         extends AbstractBSPTreeMergeOperator<P, N> {

  801.         /** Merge two input trees, storing the output in the third. The output tree can be one of the
  802.          * input trees. The output tree is condensed before the method returns.
  803.          * @param inputTree1 first input tree
  804.          * @param inputTree2 second input tree
  805.          * @param outputTree the tree that will contain the result of the merge; may be one
  806.          *      of the input trees
  807.          */
  808.         public void apply(final AbstractRegionBSPTree<P, N> inputTree1, final AbstractRegionBSPTree<P, N> inputTree2,
  809.                 final AbstractRegionBSPTree<P, N> outputTree) {

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

  811.             outputTree.condense();
  812.         }
  813.     }

  814.     /** Class for performing boolean union operations on region trees.
  815.      * @param <P> Point implementation type
  816.      * @param <N> BSP tree node implementation type
  817.      */
  818.     private static final class UnionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  819.         extends RegionMergeOperator<P, N> {

  820.         /** {@inheritDoc} */
  821.         @Override
  822.         protected N mergeLeaf(final N node1, final N node2) {
  823.             if (node1.isLeaf()) {
  824.                 return node1.isInside() ? node1 : node2;
  825.             }

  826.             // call again with flipped arguments
  827.             return mergeLeaf(node2, node1);
  828.         }
  829.     }

  830.     /** Class for performing boolean intersection operations on region trees.
  831.      * @param <P> Point implementation type
  832.      * @param <N> BSP tree node implementation type
  833.      */
  834.     private static final class IntersectionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  835.         extends RegionMergeOperator<P, N> {

  836.         /** {@inheritDoc} */
  837.         @Override
  838.         protected N mergeLeaf(final N node1, final N node2) {
  839.             if (node1.isLeaf()) {
  840.                 return node1.isInside() ? node2 : node1;
  841.             }

  842.             // call again with flipped arguments
  843.             return mergeLeaf(node2, node1);
  844.         }
  845.     }

  846.     /** Class for performing boolean difference operations on region trees.
  847.      * @param <P> Point implementation type
  848.      * @param <N> BSP tree node implementation type
  849.      */
  850.     private static final class DifferenceOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  851.         extends RegionMergeOperator<P, N> {

  852.         /** {@inheritDoc} */
  853.         @Override
  854.         protected N mergeLeaf(final N node1, final N node2) {
  855.             // a region is included if it belongs in tree1 and is not in tree2

  856.             if (node1.isInside()) {
  857.                 // this region is inside of tree1, so only include subregions that are
  858.                 // not in tree2, ie include everything in node2's complement
  859.                 final N output = outputSubtree(node2);
  860.                 output.getTree().complementRecursive(output);

  861.                 return output;
  862.             } else if (node2.isInside()) {
  863.                 // this region is inside of tree2 and so cannot be in the result region
  864.                 final N output = outputNode();
  865.                 output.setLocationValue(RegionLocation.OUTSIDE);

  866.                 return output;
  867.             }

  868.             // this region is not in tree2, so we can include everything in tree1
  869.             return node1;
  870.         }
  871.     }

  872.     /** Class for performing boolean symmetric difference (xor) operations on region trees.
  873.      * @param <P> Point implementation type
  874.      * @param <N> BSP tree node implementation type
  875.      */
  876.     private static final class XorOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
  877.         extends RegionMergeOperator<P, N> {

  878.         /** {@inheritDoc} */
  879.         @Override
  880.         protected N mergeLeaf(final N node1, final N node2) {
  881.             // a region is included if it belongs in tree1 and is not in tree2 OR
  882.             // it belongs in tree2 and is not in tree1

  883.             if (node1.isLeaf()) {
  884.                 if (node1.isInside()) {
  885.                     // this region is inside node1, so only include subregions that are
  886.                     // not in node2, ie include everything in node2's complement
  887.                     final N output = outputSubtree(node2);
  888.                     output.getTree().complementRecursive(output);

  889.                     return output;
  890.                 } else {
  891.                     // this region is not in node1, so only include subregions that
  892.                     // in node2
  893.                     return node2;
  894.                 }
  895.             }

  896.             // the operation is symmetric, so perform the same operation but with the
  897.             // nodes flipped
  898.             return mergeLeaf(node2, node1);
  899.         }
  900.     }

  901.     /** Internal class used to perform tree condense operations.
  902.      * @param <P> Point implementation type
  903.      * @param <N> BSP tree node implementation type
  904.      */
  905.     private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> {
  906.         /** Flag set to true if the tree was modified during the operation. */
  907.         private boolean modifiedTree;

  908.         /** Condense the nodes in the subtree rooted at the given node. Redundant child nodes are
  909.          * removed. The tree is invalidated if the tree structure was modified.
  910.          * @param node the root node of the subtree to condense
  911.          * @return true if the tree was modified.
  912.          */
  913.         boolean condense(final N node) {
  914.             modifiedTree = false;

  915.             condenseRecursive(node);

  916.             return modifiedTree;
  917.         }

  918.         /** Recursively condense nodes that have children with homogenous location attributes
  919.          * (eg, both inside, both outside) into single nodes.
  920.          * @param node the root of the subtree to condense
  921.          * @return the location of the successfully condensed subtree or null if no condensing was
  922.          *      able to be performed
  923.          */
  924.         private RegionLocation condenseRecursive(final N node) {
  925.             if (node.isLeaf()) {
  926.                 return node.getLocation();
  927.             }

  928.             final RegionLocation minusLocation = condenseRecursive(node.getMinus());
  929.             final RegionLocation plusLocation = condenseRecursive(node.getPlus());

  930.             if (minusLocation == plusLocation && minusLocation != null) {
  931.                 node.setLocationValue(minusLocation);
  932.                 node.clearCut();

  933.                 modifiedTree = true;

  934.                 return minusLocation;
  935.             }

  936.             return null;
  937.         }
  938.     }

  939.     /** Class that iterates over the boundary hyperplane convex subsets from a set of region nodes.
  940.      * @param <P> Point implementation type
  941.      * @param <C> Boundary hyperplane convex subset implementation type
  942.      * @param <N> BSP tree node implementation type
  943.      */
  944.     private static final class RegionBoundaryIterator<
  945.             P extends Point<P>,
  946.             C extends HyperplaneConvexSubset<P>,
  947.             N extends AbstractRegionNode<P, N>>
  948.         extends IteratorTransform<N, C> {

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

  951.         /** Simple constructor.
  952.          * @param inputIterator iterator that will provide all nodes in the tree
  953.          * @param typeConverter function that converts from the convex subset type to the output type
  954.          */
  955.         RegionBoundaryIterator(final Iterator<N> inputIterator,
  956.                 final Function<? super HyperplaneConvexSubset<P>, C> typeConverter) {
  957.             super(inputIterator);

  958.             this.typeConverter = typeConverter;
  959.         }

  960.         /** {@inheritDoc} */
  961.         @Override
  962.         protected void acceptInput(final N input) {
  963.             if (input.isInternal()) {
  964.                 final RegionCutBoundary<P> cutBoundary = input.getCutBoundary();

  965.                 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getOutsideFacing()) {
  966.                     addOutput(typeConverter.apply(boundary));
  967.                 }

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

  970.                     addOutput(typeConverter.apply(reversed));
  971.                 }
  972.             }
  973.         }
  974.     }
  975. }