commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.java - commons-geometry - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.commons.geometry.euclidean.oned;

 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.List;
 import java.util.Objects;
 import java.util.function.BiConsumer;

 import org.apache.commons.geometry.core.RegionLocation;
 import org.apache.commons.geometry.core.Transform;
 import org.apache.commons.geometry.core.partitioning.Hyperplane;
 import org.apache.commons.geometry.core.partitioning.Split;
 import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
 import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;

 /** Binary space partitioning (BSP) tree representing a region in one dimensional
  * Euclidean space.
  */
 public final class RegionBSPTree1D extends AbstractRegionBSPTree<Vector1D, RegionBSPTree1D.RegionNode1D> {
     /** Comparator used to sort BoundaryPairs by ascending location.  */
     private static final Comparator<BoundaryPair> BOUNDARY_PAIR_COMPARATOR = (BoundaryPair a, BoundaryPair b) -> {
         return Double.compare(a.getMinValue(), b.getMinValue());
     };

     /** Create a new, empty region.
      */
     public RegionBSPTree1D() {
         this(false);
     }

     /** Create a new region. If {@code full} is true, then the region will
      * represent the entire number line. Otherwise, it will be empty.
      * @param full whether or not the region should contain the entire
      *      number line or be empty
      */
     public RegionBSPTree1D(boolean full) {
         super(full);
     }

     /** Return a deep copy of this instance.
      * @return a deep copy of this instance.
      * @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
      */
     public RegionBSPTree1D copy() {
         RegionBSPTree1D result = RegionBSPTree1D.empty();
         result.copy(this);

         return result;
     }

     /** Add an interval to this region. The resulting region will be the
      * union of the interval and the region represented by this instance.
      * @param interval the interval to add
      */
     public void add(final Interval interval) {
         union(intervalToTree(interval));
     }

     /** Classify a point location with respect to the region.
      * @param x the point to classify
      * @return the location of the point with respect to the region
      * @see #classify(Point)
      */
     public RegionLocation classify(final double x) {
         return classify(Vector1D.of(x));
     }

     /** Return true if the given point location is on the inside or boundary
      * of the region.
      * @param x the location to test
      * @return true if the location is on the inside or boundary of the region
      * @see #contains(Point)
      */
     public boolean contains(final double x) {
         return contains(Vector1D.of(x));
     }

     /** {@inheritDoc}
     *
     *  <p>This method simply returns 0 because boundaries in one dimension do not
     *  have any size.</p>
     */
     @Override
     public double getBoundarySize() {
         return 0;
     }

     /** {@inheritDoc} */
     @Override
     public Vector1D project(final Vector1D pt) {
         // use our custom projector so that we can disambiguate points that are
         // actually equidistant from the target point
         final BoundaryProjector1D projector = new BoundaryProjector1D(pt);
         accept(projector);

         return projector.getProjected();
     }

     /** {@inheritDoc}
      *
      * <p>When splitting trees representing single points with a splitter lying directly
      * on the point, the result point is placed on one side of the splitter based on its
      * orientation: if the splitter is positive-facing, the point is placed on the plus
      * side of the split; if the splitter is negative-facing, the point is placed on the
      * minus side of the split.</p>
      */
     @Override
     public Split<RegionBSPTree1D> split(final Hyperplane<Vector1D> splitter) {
         return split(splitter, RegionBSPTree1D.empty(), RegionBSPTree1D.empty());
     }

     /** Get the minimum value on the inside of the region; returns {@link Double#NEGATIVE_INFINITY}
      * if the region does not have a minimum value and {@link Double#POSITIVE_INFINITY} if
      * the region is empty.
      * @return the minimum value on the inside of the region
      */
     public double getMin() {
         double min = Double.POSITIVE_INFINITY;

         RegionNode1D node = getRoot();
         OrientedPoint pt;

         while (!node.isLeaf()) {
             pt = (OrientedPoint) node.getCutHyperplane();

             min = pt.getLocation();
             node = pt.isPositiveFacing() ? node.getMinus() : node.getPlus();
         }

         return node.isInside() ? Double.NEGATIVE_INFINITY : min;
     }

     /** Get the maximum value on the inside of the region; returns {@link Double#POSITIVE_INFINITY}
      * if the region does not have a maximum value and {@link Double#NEGATIVE_INFINITY} if
      * the region is empty.
      * @return the maximum value on the inside of the region
      */
     public double getMax() {
         double max = Double.NEGATIVE_INFINITY;

         RegionNode1D node = getRoot();
         OrientedPoint pt;

         while (!node.isLeaf()) {
             pt = (OrientedPoint) node.getCutHyperplane();

             max = pt.getLocation();
             node = pt.isPositiveFacing() ? node.getPlus() : node.getMinus();
         }

         return node.isInside() ? Double.POSITIVE_INFINITY : max;
     }

     /** Convert the region represented by this tree into a list of separate
      * {@link Interval}s, arranged in order of ascending min value.
      * @return list of {@link Interval}s representing this region in order of
      *      ascending min value
      */
     public List<Interval> toIntervals() {

         final List<BoundaryPair> boundaryPairs = new ArrayList<>();

         visitInsideIntervals((min, max) -> {
             boundaryPairs.add(new BoundaryPair(min, max));
         });

         boundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR);

         final List<Interval> intervals = new ArrayList<>();

         BoundaryPair start = null;
         BoundaryPair end = null;

         for (BoundaryPair current : boundaryPairs) {
             if (start == null) {
                 start = current;
                 end = current;
             } else if (Objects.equals(end.getMax(), current.getMin())) {
                 // these intervals should be merged
                 end = current;
             } else {
                 // these intervals should not be merged
                 intervals.add(createInterval(start, end));

                 // queue up the next pair
                 start = current;
                 end = current;
             }
         }

         if (start != null && end != null) {
             intervals.add(createInterval(start, end));
         }

         return intervals;
     }

     /** Create an interval instance from the min boundary from the start boundary pair and
      * the max boundary from the end boundary pair. The hyperplane directions are adjusted
      * as needed.
      * @param start starting boundary pair
      * @param end ending boundary pair
      * @return an interval created from the min boundary of the given start pair and the
      *      max boundary from the given end pair
      */
     private Interval createInterval(final BoundaryPair start, final BoundaryPair end) {
         OrientedPoint min = start.getMin();
         OrientedPoint max = end.getMax();

         // flip the hyperplanes if needed since there's no
         // guarantee that the inside will be on the minus side
         // of the hyperplane (for example, if the region is complemented)

         if (min != null && min.isPositiveFacing()) {
             min = min.reverse();
         }
         if (max != null && !max.isPositiveFacing()) {
             max = max.reverse();
         }

         return Interval.of(min, max);
     }

     /** Compute the min/max intervals for all interior convex regions in the tree and
      * pass the values to the given visitor function.
      * @param visitor the object that will receive the calculated min and max boundary for each
      *      insides node's convex region
      */
     private void visitInsideIntervals(final BiConsumer<OrientedPoint, OrientedPoint> visitor) {
         for (RegionNode1D node : this) {
             if (node.isInside()) {
                 visitNodeInterval(node, visitor);
             }
         }
     }

     /** Determine the min/max boundaries for the convex region represented by the given node and pass
      * the values to the visitor function.
      * @param node the node to compute the interval for
      * @param visitor the object that will receive the min and max boundaries for the node's
      *      convex region
      */
     private void visitNodeInterval(final RegionNode1D node, final BiConsumer<OrientedPoint, OrientedPoint> visitor) {
         OrientedPoint min = null;
         OrientedPoint max = null;

         OrientedPoint pt;
         RegionNode1D child = node;
         RegionNode1D parent;

         while ((min == null || max == null) && (parent = child.getParent()) != null) {
             pt = (OrientedPoint) parent.getCutHyperplane();

             if ((pt.isPositiveFacing() && child.isMinus()) ||
                     (!pt.isPositiveFacing() && child.isPlus())) {

                 if (max == null) {
                     max = pt;
                 }
             } else if (min == null) {
                 min = pt;
             }

             child = parent;
         }

         visitor.accept(min, max);
     }

     /** Compute the region represented by the given node.
      * @param node the node to compute the region for
      * @return the region represented by the given node
      */
     private Interval computeNodeRegion(final RegionNode1D node) {
         final NodeRegionVisitor visitor = new NodeRegionVisitor();
         visitNodeInterval(node, visitor);

         return visitor.getInterval();
     }

     /** {@inheritDoc} */
     @Override
     protected RegionNode1D createNode() {
         return new RegionNode1D(this);
     }

     /** {@inheritDoc} */
     @Override
     protected RegionSizeProperties<Vector1D> computeRegionSizeProperties() {
         RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor();

         visitInsideIntervals(visitor);

         return visitor.getRegionSizeProperties();
     }

     /** Returns true if the given transform would result in a swapping of the interior
      * and exterior of the region if applied.
      *
      * <p>This method always returns false since no swapping of this kind occurs in
      * 1D.</p>
      */
     @Override
     protected boolean swapsInsideOutside(final Transform<Vector1D> transform) {
         return false;
     }

     /** Return a new {@link RegionBSPTree1D} instance containing the entire space.
      * @return a new {@link RegionBSPTree1D} instance containing the entire space
      */
     public static RegionBSPTree1D full() {
         return new RegionBSPTree1D(true);
     }

     /** Return a new, empty {@link RegionBSPTree1D} instance.
      * @return a new, empty {@link RegionBSPTree1D} instance
      */
     public static RegionBSPTree1D empty() {
         return new RegionBSPTree1D(false);
     }

     /** Construct a new instance from one or more intervals. The returned tree
      * represents the same region as the union of all of the input intervals.
      * @param interval the input interval
      * @param more additional intervals to add to the region
      * @return a new instance representing the same region as the union
      *      of all of the given intervals
      */
     public static RegionBSPTree1D from(final Interval interval, final Interval... more) {
         final RegionBSPTree1D tree = intervalToTree(interval);

         for (final Interval additional : more) {
             tree.add(additional);
         }

         return tree;
     }

     /** Construct a new instance from the given collection of intervals.
      * @param intervals the intervals to populate the region with
      * @return a new instance constructed from the given collection of intervals
      */
     public static RegionBSPTree1D from(final Iterable<Interval> intervals) {
         RegionBSPTree1D tree = new RegionBSPTree1D(false);

         for (final Interval interval : intervals) {
             tree.add(interval);
         }

         return tree;
     }

     /** Return a tree representing the same region as the given interval.
      * @param interval interval to create a tree from
      * @return a tree representing the same region as the given interval
      */
     private static RegionBSPTree1D intervalToTree(final Interval interval) {
         final OrientedPoint minBoundary = interval.getMinBoundary();
         final OrientedPoint maxBoundary = interval.getMaxBoundary();

         final RegionBSPTree1D tree = full();

         RegionNode1D node = tree.getRoot();

         if (minBoundary != null) {
             tree.cutNode(node, minBoundary.span());

             node = node.getMinus();
         }

         if (maxBoundary != null) {
             tree.cutNode(node, maxBoundary.span());
         }

         return tree;
     }

     /** BSP tree node for one dimensional Euclidean space.
      */
     public static final class RegionNode1D extends AbstractRegionBSPTree.AbstractRegionNode<Vector1D, RegionNode1D> {
         /** Simple constructor.
          * @param tree the owning tree instance
          */
         private RegionNode1D(AbstractBSPTree<Vector1D, RegionNode1D> tree) {
             super(tree);
         }

         /** Get the region represented by this node. The returned region contains
          * the entire area contained in this node, regardless of the attributes of
          * any child nodes.
          * @return the region represented by this node
          */
         public Interval getNodeRegion() {
             return ((RegionBSPTree1D) getTree()).computeNodeRegion(this);
         }

         /** {@inheritDoc} */
         @Override
         protected RegionNode1D getSelf() {
             return this;
         }
     }

     /** Internal class containing pairs of interval boundaries.
      */
     private static final class BoundaryPair {

         /** The min boundary. */
         private final OrientedPoint min;

         /** The max boundary. */
         private final OrientedPoint max;

         /** Simple constructor.
          * @param min min boundary hyperplane
          * @param max max boundary hyperplane
          */
         BoundaryPair(final OrientedPoint min, final OrientedPoint max) {
             this.min = min;
             this.max = max;
         }

         /** Get the minimum boundary hyperplane.
          * @return the minimum boundary hyperplane.
          */
         public OrientedPoint getMin() {
             return min;
         }

         /** Get the maximum boundary hyperplane.
          * @return the maximum boundary hyperplane.
          */
         public OrientedPoint getMax() {
             return max;
         }

         /** Get the minumum value of the interval or {@link Double#NEGATIVE_INFINITY}
          * if no minimum value exists.
          * @return the minumum value of the interval or {@link Double#NEGATIVE_INFINITY}
          *      if no minimum value exists.
          */
         public double getMinValue() {
             return (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
         }
     }

     /** Class used to project points onto the region boundary.
      */
     private static final class BoundaryProjector1D extends BoundaryProjector<Vector1D, RegionNode1D> {
         /** Simple constructor.
          * @param point the point to project onto the region's boundary
          */
         BoundaryProjector1D(Vector1D point) {
             super(point);
         }

         /** {@inheritDoc} */
         @Override
         protected Vector1D disambiguateClosestPoint(final Vector1D target, final Vector1D a, final Vector1D b) {
             final int cmp = Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b);

             if (target.isInfinite() && target.getX() > 0) {
                 // return the largest value (closest to +Infinity)
                 return cmp < 0 ? b : a;
             }

             // return the smallest value
             return cmp < 0 ? a : b;
         }
     }

     /** Internal class for calculating the region of a single tree node.
      */
     private static final class NodeRegionVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {

         /** The min boundary for the region. */
         private OrientedPoint min;

         /** The max boundary for the region. */
         private OrientedPoint max;

         /** {@inheritDoc} */
         @Override
         public void accept(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
             // reverse the oriented point directions if needed
             this.min = (minBoundary != null && minBoundary.isPositiveFacing()) ? minBoundary.reverse() : minBoundary;
             this.max = (maxBoundary != null && !maxBoundary.isPositiveFacing()) ? maxBoundary.reverse() : maxBoundary;
         }

         /** Return the computed interval.
          * @return the computed interval.
          */
         public Interval getInterval() {
             return Interval.of(min, max);
         }
     }

     /** Internal class for calculating size-related properties for a {@link RegionBSPTree1D}.
      */
     private static final class RegionSizePropertiesVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {
         /** Number of inside intervals visited. */
         private int count = 0;

         /** Total computed size of all inside regions. */
         private double size = 0;

         /** Raw sum of the barycenters of each inside interval. */
         private double rawBarycenterSum = 0;

         /** The sum of the barycenter of each inside interval, scaled by the size of the interval. */
         private double scaledBarycenterSum = 0;

         /** {@inheritDoc} */
         @Override
         public void accept(OrientedPoint min, OrientedPoint max) {
             ++count;

             final double minLoc = (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
             final double maxLoc = (max != null) ? max.getLocation() : Double.POSITIVE_INFINITY;

             final double intervalSize = maxLoc - minLoc;
             final double intervalBarycenter = 0.5 * (maxLoc + minLoc);

             size += intervalSize;
             rawBarycenterSum += intervalBarycenter;
             scaledBarycenterSum += intervalSize * intervalBarycenter;
         }

         /** Get the computed properties for the region. This must only be called after
          * every inside interval has been visited.
          * @return properties for the region
          */
         public RegionSizeProperties<Vector1D> getRegionSizeProperties() {
             Vector1D barycenter = null;

             if (count > 0 && Double.isFinite(size)) {
                 if (size > 0.0) {
                     // use the scaled sum if we have a non-zero size
                     barycenter = Vector1D.of(scaledBarycenterSum / size);
                 } else {
                     // use the raw sum if we don't have a size; this will be
                     // the case if the region only contains points with zero size
                     barycenter = Vector1D.of(rawBarycenterSum / count);
                 }
             }

             return new RegionSizeProperties<>(size, barycenter);
         }
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.commons.geometry.euclidean.oned;

	import java.util.ArrayList;
	import java.util.Comparator;
	import java.util.List;
	import java.util.Objects;
	import java.util.function.BiConsumer;

	import org.apache.commons.geometry.core.RegionLocation;
	import org.apache.commons.geometry.core.Transform;
	import org.apache.commons.geometry.core.partitioning.Hyperplane;
	import org.apache.commons.geometry.core.partitioning.Split;
	import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
	import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;

	/** Binary space partitioning (BSP) tree representing a region in one dimensional
	* Euclidean space.
	*/
	public final class RegionBSPTree1D extends AbstractRegionBSPTree<Vector1D, RegionBSPTree1D.RegionNode1D> {
	/** Comparator used to sort BoundaryPairs by ascending location. */
	private static final Comparator<BoundaryPair> BOUNDARY_PAIR_COMPARATOR = (BoundaryPair a, BoundaryPair b) -> {
	return Double.compare(a.getMinValue(), b.getMinValue());
	};

	/** Create a new, empty region.
	*/
	public RegionBSPTree1D() {
	this(false);
	}

	/** Create a new region. If {@code full} is true, then the region will
	* represent the entire number line. Otherwise, it will be empty.
	* @param full whether or not the region should contain the entire
	* number line or be empty
	*/
	public RegionBSPTree1D(boolean full) {
	super(full);
	}

	/** Return a deep copy of this instance.
	* @return a deep copy of this instance.
	* @see #copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
	*/
	public RegionBSPTree1D copy() {
	RegionBSPTree1D result = RegionBSPTree1D.empty();
	result.copy(this);

	return result;
	}

	/** Add an interval to this region. The resulting region will be the
	* union of the interval and the region represented by this instance.
	* @param interval the interval to add
	*/
	public void add(final Interval interval) {
	union(intervalToTree(interval));
	}

	/** Classify a point location with respect to the region.
	* @param x the point to classify
	* @return the location of the point with respect to the region
	* @see #classify(Point)
	*/
	public RegionLocation classify(final double x) {
	return classify(Vector1D.of(x));
	}

	/** Return true if the given point location is on the inside or boundary
	* of the region.
	* @param x the location to test
	* @return true if the location is on the inside or boundary of the region
	* @see #contains(Point)
	*/
	public boolean contains(final double x) {
	return contains(Vector1D.of(x));
	}

	/** {@inheritDoc}
	*
	* <p>This method simply returns 0 because boundaries in one dimension do not
	* have any size.</p>
	*/
	@Override
	public double getBoundarySize() {
	return 0;
	}

	/** {@inheritDoc} */
	@Override
	public Vector1D project(final Vector1D pt) {
	// use our custom projector so that we can disambiguate points that are
	// actually equidistant from the target point
	final BoundaryProjector1D projector = new BoundaryProjector1D(pt);
	accept(projector);

	return projector.getProjected();
	}

	/** {@inheritDoc}
	*
	* <p>When splitting trees representing single points with a splitter lying directly
	* on the point, the result point is placed on one side of the splitter based on its
	* orientation: if the splitter is positive-facing, the point is placed on the plus
	* side of the split; if the splitter is negative-facing, the point is placed on the
	* minus side of the split.</p>
	*/
	@Override
	public Split<RegionBSPTree1D> split(final Hyperplane<Vector1D> splitter) {
	return split(splitter, RegionBSPTree1D.empty(), RegionBSPTree1D.empty());
	}

	/** Get the minimum value on the inside of the region; returns {@link Double#NEGATIVE_INFINITY}
	* if the region does not have a minimum value and {@link Double#POSITIVE_INFINITY} if
	* the region is empty.
	* @return the minimum value on the inside of the region
	*/
	public double getMin() {
	double min = Double.POSITIVE_INFINITY;

	RegionNode1D node = getRoot();
	OrientedPoint pt;

	while (!node.isLeaf()) {
	pt = (OrientedPoint) node.getCutHyperplane();

	min = pt.getLocation();
	node = pt.isPositiveFacing() ? node.getMinus() : node.getPlus();
	}

	return node.isInside() ? Double.NEGATIVE_INFINITY : min;
	}

	/** Get the maximum value on the inside of the region; returns {@link Double#POSITIVE_INFINITY}
	* if the region does not have a maximum value and {@link Double#NEGATIVE_INFINITY} if
	* the region is empty.
	* @return the maximum value on the inside of the region
	*/
	public double getMax() {
	double max = Double.NEGATIVE_INFINITY;

	RegionNode1D node = getRoot();
	OrientedPoint pt;

	while (!node.isLeaf()) {
	pt = (OrientedPoint) node.getCutHyperplane();

	max = pt.getLocation();
	node = pt.isPositiveFacing() ? node.getPlus() : node.getMinus();
	}

	return node.isInside() ? Double.POSITIVE_INFINITY : max;
	}

	/** Convert the region represented by this tree into a list of separate
	* {@link Interval}s, arranged in order of ascending min value.
	* @return list of {@link Interval}s representing this region in order of
	* ascending min value
	*/
	public List<Interval> toIntervals() {

	final List<BoundaryPair> boundaryPairs = new ArrayList<>();

	visitInsideIntervals((min, max) -> {
	boundaryPairs.add(new BoundaryPair(min, max));
	});

	boundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR);

	final List<Interval> intervals = new ArrayList<>();

	BoundaryPair start = null;
	BoundaryPair end = null;

	for (BoundaryPair current : boundaryPairs) {
	if (start == null) {
	start = current;
	end = current;
	} else if (Objects.equals(end.getMax(), current.getMin())) {
	// these intervals should be merged
	end = current;
	} else {
	// these intervals should not be merged
	intervals.add(createInterval(start, end));

	// queue up the next pair
	start = current;
	end = current;
	}
	}

	if (start != null && end != null) {
	intervals.add(createInterval(start, end));
	}

	return intervals;
	}

	/** Create an interval instance from the min boundary from the start boundary pair and
	* the max boundary from the end boundary pair. The hyperplane directions are adjusted
	* as needed.
	* @param start starting boundary pair
	* @param end ending boundary pair
	* @return an interval created from the min boundary of the given start pair and the
	* max boundary from the given end pair
	*/
	private Interval createInterval(final BoundaryPair start, final BoundaryPair end) {
	OrientedPoint min = start.getMin();
	OrientedPoint max = end.getMax();

	// flip the hyperplanes if needed since there's no
	// guarantee that the inside will be on the minus side
	// of the hyperplane (for example, if the region is complemented)

	if (min != null && min.isPositiveFacing()) {
	min = min.reverse();
	}
	if (max != null && !max.isPositiveFacing()) {
	max = max.reverse();
	}

	return Interval.of(min, max);
	}

	/** Compute the min/max intervals for all interior convex regions in the tree and
	* pass the values to the given visitor function.
	* @param visitor the object that will receive the calculated min and max boundary for each
	* insides node's convex region
	*/
	private void visitInsideIntervals(final BiConsumer<OrientedPoint, OrientedPoint> visitor) {
	for (RegionNode1D node : this) {
	if (node.isInside()) {
	visitNodeInterval(node, visitor);
	}
	}
	}

	/** Determine the min/max boundaries for the convex region represented by the given node and pass
	* the values to the visitor function.
	* @param node the node to compute the interval for
	* @param visitor the object that will receive the min and max boundaries for the node's
	* convex region
	*/
	private void visitNodeInterval(final RegionNode1D node, final BiConsumer<OrientedPoint, OrientedPoint> visitor) {
	OrientedPoint min = null;
	OrientedPoint max = null;

	OrientedPoint pt;
	RegionNode1D child = node;
	RegionNode1D parent;

	while ((min == null \|\| max == null) && (parent = child.getParent()) != null) {
	pt = (OrientedPoint) parent.getCutHyperplane();

	if ((pt.isPositiveFacing() && child.isMinus()) \|\|
	(!pt.isPositiveFacing() && child.isPlus())) {

	if (max == null) {
	max = pt;
	}
	} else if (min == null) {
	min = pt;
	}

	child = parent;
	}

	visitor.accept(min, max);
	}

	/** Compute the region represented by the given node.
	* @param node the node to compute the region for
	* @return the region represented by the given node
	*/
	private Interval computeNodeRegion(final RegionNode1D node) {
	final NodeRegionVisitor visitor = new NodeRegionVisitor();
	visitNodeInterval(node, visitor);

	return visitor.getInterval();
	}

	/** {@inheritDoc} */
	@Override
	protected RegionNode1D createNode() {
	return new RegionNode1D(this);
	}

	/** {@inheritDoc} */
	@Override
	protected RegionSizeProperties<Vector1D> computeRegionSizeProperties() {
	RegionSizePropertiesVisitor visitor = new RegionSizePropertiesVisitor();

	visitInsideIntervals(visitor);

	return visitor.getRegionSizeProperties();
	}

	/** Returns true if the given transform would result in a swapping of the interior
	* and exterior of the region if applied.
	*
	* <p>This method always returns false since no swapping of this kind occurs in
	* 1D.</p>
	*/
	@Override
	protected boolean swapsInsideOutside(final Transform<Vector1D> transform) {
	return false;
	}

	/** Return a new {@link RegionBSPTree1D} instance containing the entire space.
	* @return a new {@link RegionBSPTree1D} instance containing the entire space
	*/
	public static RegionBSPTree1D full() {
	return new RegionBSPTree1D(true);
	}

	/** Return a new, empty {@link RegionBSPTree1D} instance.
	* @return a new, empty {@link RegionBSPTree1D} instance
	*/
	public static RegionBSPTree1D empty() {
	return new RegionBSPTree1D(false);
	}

	/** Construct a new instance from one or more intervals. The returned tree
	* represents the same region as the union of all of the input intervals.
	* @param interval the input interval
	* @param more additional intervals to add to the region
	* @return a new instance representing the same region as the union
	* of all of the given intervals
	*/
	public static RegionBSPTree1D from(final Interval interval, final Interval... more) {
	final RegionBSPTree1D tree = intervalToTree(interval);

	for (final Interval additional : more) {
	tree.add(additional);
	}

	return tree;
	}

	/** Construct a new instance from the given collection of intervals.
	* @param intervals the intervals to populate the region with
	* @return a new instance constructed from the given collection of intervals
	*/
	public static RegionBSPTree1D from(final Iterable<Interval> intervals) {
	RegionBSPTree1D tree = new RegionBSPTree1D(false);

	for (final Interval interval : intervals) {
	tree.add(interval);
	}

	return tree;
	}

	/** Return a tree representing the same region as the given interval.
	* @param interval interval to create a tree from
	* @return a tree representing the same region as the given interval
	*/
	private static RegionBSPTree1D intervalToTree(final Interval interval) {
	final OrientedPoint minBoundary = interval.getMinBoundary();
	final OrientedPoint maxBoundary = interval.getMaxBoundary();

	final RegionBSPTree1D tree = full();

	RegionNode1D node = tree.getRoot();

	if (minBoundary != null) {
	tree.cutNode(node, minBoundary.span());

	node = node.getMinus();
	}

	if (maxBoundary != null) {
	tree.cutNode(node, maxBoundary.span());
	}

	return tree;
	}

	/** BSP tree node for one dimensional Euclidean space.
	*/
	public static final class RegionNode1D extends AbstractRegionBSPTree.AbstractRegionNode<Vector1D, RegionNode1D> {
	/** Simple constructor.
	* @param tree the owning tree instance
	*/
	private RegionNode1D(AbstractBSPTree<Vector1D, RegionNode1D> tree) {
	super(tree);
	}

	/** Get the region represented by this node. The returned region contains
	* the entire area contained in this node, regardless of the attributes of
	* any child nodes.
	* @return the region represented by this node
	*/
	public Interval getNodeRegion() {
	return ((RegionBSPTree1D) getTree()).computeNodeRegion(this);
	}

	/** {@inheritDoc} */
	@Override
	protected RegionNode1D getSelf() {
	return this;
	}
	}

	/** Internal class containing pairs of interval boundaries.
	*/
	private static final class BoundaryPair {

	/** The min boundary. */
	private final OrientedPoint min;

	/** The max boundary. */
	private final OrientedPoint max;

	/** Simple constructor.
	* @param min min boundary hyperplane
	* @param max max boundary hyperplane
	*/
	BoundaryPair(final OrientedPoint min, final OrientedPoint max) {
	this.min = min;
	this.max = max;
	}

	/** Get the minimum boundary hyperplane.
	* @return the minimum boundary hyperplane.
	*/
	public OrientedPoint getMin() {
	return min;
	}

	/** Get the maximum boundary hyperplane.
	* @return the maximum boundary hyperplane.
	*/
	public OrientedPoint getMax() {
	return max;
	}

	/** Get the minumum value of the interval or {@link Double#NEGATIVE_INFINITY}
	* if no minimum value exists.
	* @return the minumum value of the interval or {@link Double#NEGATIVE_INFINITY}
	* if no minimum value exists.
	*/
	public double getMinValue() {
	return (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
	}
	}

	/** Class used to project points onto the region boundary.
	*/
	private static final class BoundaryProjector1D extends BoundaryProjector<Vector1D, RegionNode1D> {
	/** Simple constructor.
	* @param point the point to project onto the region's boundary
	*/
	BoundaryProjector1D(Vector1D point) {
	super(point);
	}

	/** {@inheritDoc} */
	@Override
	protected Vector1D disambiguateClosestPoint(final Vector1D target, final Vector1D a, final Vector1D b) {
	final int cmp = Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b);

	if (target.isInfinite() && target.getX() > 0) {
	// return the largest value (closest to +Infinity)
	return cmp < 0 ? b : a;
	}

	// return the smallest value
	return cmp < 0 ? a : b;
	}
	}

	/** Internal class for calculating the region of a single tree node.
	*/
	private static final class NodeRegionVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {

	/** The min boundary for the region. */
	private OrientedPoint min;

	/** The max boundary for the region. */
	private OrientedPoint max;

	/** {@inheritDoc} */
	@Override
	public void accept(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
	// reverse the oriented point directions if needed
	this.min = (minBoundary != null && minBoundary.isPositiveFacing()) ? minBoundary.reverse() : minBoundary;
	this.max = (maxBoundary != null && !maxBoundary.isPositiveFacing()) ? maxBoundary.reverse() : maxBoundary;
	}

	/** Return the computed interval.
	* @return the computed interval.
	*/
	public Interval getInterval() {
	return Interval.of(min, max);
	}
	}

	/** Internal class for calculating size-related properties for a {@link RegionBSPTree1D}.
	*/
	private static final class RegionSizePropertiesVisitor implements BiConsumer<OrientedPoint, OrientedPoint> {
	/** Number of inside intervals visited. */
	private int count = 0;

	/** Total computed size of all inside regions. */
	private double size = 0;

	/** Raw sum of the barycenters of each inside interval. */
	private double rawBarycenterSum = 0;

	/** The sum of the barycenter of each inside interval, scaled by the size of the interval. */
	private double scaledBarycenterSum = 0;

	/** {@inheritDoc} */
	@Override
	public void accept(OrientedPoint min, OrientedPoint max) {
	++count;

	final double minLoc = (min != null) ? min.getLocation() : Double.NEGATIVE_INFINITY;
	final double maxLoc = (max != null) ? max.getLocation() : Double.POSITIVE_INFINITY;

	final double intervalSize = maxLoc - minLoc;
	final double intervalBarycenter = 0.5 * (maxLoc + minLoc);

	size += intervalSize;
	rawBarycenterSum += intervalBarycenter;
	scaledBarycenterSum += intervalSize * intervalBarycenter;
	}

	/** Get the computed properties for the region. This must only be called after
	* every inside interval has been visited.
	* @return properties for the region
	*/
	public RegionSizeProperties<Vector1D> getRegionSizeProperties() {
	Vector1D barycenter = null;

	if (count > 0 && Double.isFinite(size)) {
	if (size > 0.0) {
	// use the scaled sum if we have a non-zero size
	barycenter = Vector1D.of(scaledBarycenterSum / size);
	} else {
	// use the raw sum if we don't have a size; this will be
	// the case if the region only contains points with zero size
	barycenter = Vector1D.of(rawBarycenterSum / count);
	}
	}

	return new RegionSizeProperties<>(size, barycenter);
	}
	}
	}