commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.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.twod;

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
 import java.util.stream.Collectors;

 import org.apache.commons.geometry.core.exception.GeometryValueException;
 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;
 import org.apache.commons.geometry.core.precision.DoublePrecisionContext;

 /** Binary space partitioning (BSP) tree representing a region in two dimensional
  * Euclidean space.
  */
 public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D> {
     /** List of line segment paths comprising the region boundary. */
     private List<Polyline> boundaryPaths;

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

     /** Create a new region. If {@code full} is true, then the region will
      * represent the entire 2D space. Otherwise, it will be empty.
      * @param full whether or not the region should contain the entire
      *      2D space or be empty
      */
     public RegionBSPTree2D(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 RegionBSPTree2D copy() {
         RegionBSPTree2D result = RegionBSPTree2D.empty();
         result.copy(this);

         return result;
     }

     /** {@inheritDoc} */
     @Override
     public Iterable<Segment> boundaries() {
         return createBoundaryIterable(b -> (Segment) b);
     }

     /** {@inheritDoc} */
     @Override
     public List<Segment> getBoundaries() {
         return createBoundaryList(b -> (Segment) b);
     }

     /** Get the boundary of the region as a list of connected line segment paths. The
      * line segments are oriented such that their minus (left) side lies on the
      * interior of the region.
      * @return line segment paths representing the region boundary
      */
     public List<Polyline> getBoundaryPaths() {
         if (boundaryPaths == null) {
             boundaryPaths = Collections.unmodifiableList(computeBoundaryPaths());
         }
         return boundaryPaths;
     }

     /** Add a convex area to this region. The resulting region will be the
      * union of the convex area and the region represented by this instance.
      * @param area the convex area to add
      */
     public void add(final ConvexArea area) {
         union(from(area));
     }

     /** Return a list of {@link ConvexArea}s representing the same region
      * as this instance. One convex area is returned for each interior leaf
      * node in the tree.
      * @return a list of convex areas representing the same region as this
      *      instance
      */
     public List<ConvexArea> toConvex() {
         final List<ConvexArea> result = new ArrayList<>();

         toConvexRecursive(getRoot(), ConvexArea.full(), result);

         return result;
     }

     /** Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given
      * node. The computed convex areas are added to the given list.
      * @param node root of the subtree to compute the convex areas for
      * @param nodeArea the convex area for the current node; this will be split by the node's cut hyperplane to
      *      form the convex areas for any child nodes
      * @param result list containing the results of the computation
      */
     private void toConvexRecursive(final RegionNode2D node, final ConvexArea nodeArea, final List<ConvexArea> result) {
         if (node.isLeaf()) {
             // base case; only add to the result list if the node is inside
             if (node.isInside()) {
                 result.add(nodeArea);
             }
         } else {
             // recurse
             Split<ConvexArea> split = nodeArea.split(node.getCutHyperplane());

             toConvexRecursive(node.getMinus(), split.getMinus(), result);
             toConvexRecursive(node.getPlus(), split.getPlus(), result);
         }
     }

     /** {@inheritDoc} */
     @Override
     public Split<RegionBSPTree2D> split(final Hyperplane<Vector2D> splitter) {
         return split(splitter, RegionBSPTree2D.empty(), RegionBSPTree2D.empty());
     }

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

         return projector.getProjected();
     }

     /** Compute the line segment paths comprising the region boundary.
      * @return the line segment paths comprising the region boundary
      */
     private List<Polyline> computeBoundaryPaths() {
         final InteriorAngleSegmentConnector connector = new InteriorAngleSegmentConnector.Minimize();
         connector.connect(boundaries());

         return connector.connectAll().stream()
                 .map(Polyline::simplify).collect(Collectors.toList());
     }

     /** {@inheritDoc} */
     @Override
     protected RegionSizeProperties<Vector2D> computeRegionSizeProperties() {
         // handle simple cases
         if (isFull()) {
             return new RegionSizeProperties<>(Double.POSITIVE_INFINITY, null);
         } else if (isEmpty()) {
             return new RegionSizeProperties<>(0, null);
         }

         // compute the size based on the boundary segments
         double quadrilateralAreaSum = 0.0;

         double scaledSumX = 0.0;
         double scaledSumY = 0.0;

         Vector2D startPoint;
         Vector2D endPoint;
         double signedArea;

         for (Segment segment : boundaries()) {

             if (segment.isInfinite()) {
                 // at least on boundary is infinite, meaning that
                 // the size is also infinite
                 quadrilateralAreaSum = Double.POSITIVE_INFINITY;

                 break;
             }

             startPoint = segment.getStartPoint();
             endPoint = segment.getEndPoint();

             // compute the area
             signedArea = startPoint.signedArea(endPoint);

             quadrilateralAreaSum += signedArea;

             // compute scaled coordinate values for the barycenter
             scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
             scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
         }

         double size = Double.POSITIVE_INFINITY;
         Vector2D barycenter = null;

         // The area is finite only if the computed quadrilateral area is finite and non-negative.
         // Negative areas indicate that the region is inside-out, with a finite outside surrounded
         // by an infinite inside.
         if (quadrilateralAreaSum >= 0.0 && Double.isFinite(quadrilateralAreaSum)) {
             size = 0.5 * quadrilateralAreaSum;

             if (quadrilateralAreaSum > 0.0) {
                 barycenter = Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
             }
         }

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

     /** 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 ConvexArea computeNodeRegion(final RegionNode2D node) {
         ConvexArea area = ConvexArea.full();

         RegionNode2D child = node;
         RegionNode2D parent;

         while ((parent = child.getParent()) != null) {
             Split<ConvexArea> split = area.split(parent.getCutHyperplane());

             area = child.isMinus() ? split.getMinus() : split.getPlus();

             child = parent;
         }

         return area;
     }

     /** {@inheritDoc} */
     @Override
     protected void invalidate() {
         super.invalidate();

         boundaryPaths = null;
     }

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

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

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

     /** Construct a tree from a convex area.
      * @param area the area to construct a tree from
      * @return tree instance representing the same area as the given
      *      convex area
      */
     public static RegionBSPTree2D from(final ConvexArea area) {
         final RegionBSPTree2D tree = RegionBSPTree2D.full();
         tree.insert(area.getBoundaries());

         return tree;
     }

     /** Create a new {@link RegionBSPTree2D.Builder} instance for creating BSP
      * trees from boundary representations.
      * @param precision precision context to use for floating point comparisons.
      * @return a new builder instance
      */
     public static Builder builder(final DoublePrecisionContext precision) {
         return new Builder(precision);
     }

     /** BSP tree node for two dimensional Euclidean space.
      */
     public static final class RegionNode2D extends AbstractRegionBSPTree.AbstractRegionNode<Vector2D, RegionNode2D> {
         /** Simple constructor.
          * @param tree the owning tree instance
          */
         private RegionNode2D(AbstractBSPTree<Vector2D, RegionNode2D> 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 ConvexArea getNodeRegion() {
             return ((RegionBSPTree2D) getTree()).computeNodeRegion(this);
         }

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

     /** Class used to construct {@link RegionBSPTree2D} instances from boundary representations.
      */
     public static final class Builder {

         /** Precision object used to perform floating point comparisons. This object is
          * used when constructing geometric types.
          */
         private final DoublePrecisionContext precision;

         /** The BSP tree being constructed. */
         private final RegionBSPTree2D tree = RegionBSPTree2D.empty();

         /** Create a new builder instance. The given precision context will be used when
          * constructing geometric types.
          * @param precision precision object used to perform floating point comparisons
          */
         public Builder(final DoublePrecisionContext precision) {
             this.precision = precision;
         }

         /** Add a subline to the tree.
          * @param subline subline to add
          * @return this builder instance
          */
         public Builder add(final SubLine subline) {
             tree.insert(subline);
             return this;
         }

         /** Add a segment to the tree.
          * @param segment segment to add
          * @return this builder instance
          */
         public Builder add(final Segment segment) {
             tree.insert(segment);
             return this;
         }

         /** Add the line segments defined in the given segment path.
          * @param path path containing line segments to add
          * @return this builder instance
          */
         public Builder add(final Polyline path) {
             for (Segment segment : path) {
                 add(segment);
             }

             return this;
         }

         /** Add a segment defined by the given points.
          * @param start start point
          * @param end end point
          * @return this builder instance
          */
         public Builder addSegment(final Vector2D start, final Vector2D end) {
             return add(Segment.fromPoints(start, end, precision));
         }

         /** Add segments defining an axis-oriented square with the given corner point and size.
          * @param center center point of the square
          * @param size the size of the square
          * @return this builder instance
          * @throws GeometryValueException if the width or height of the defined rectangle is zero
          *      as evaluated by the precision context.
          */
         public Builder addCenteredSquare(final Vector2D center, final double size) {
             return addCenteredRect(center, size, size);
         }

         /** Add segments defining an axis-oriented square with the given corner point and size.
          * @param corner point in the corner of the square
          * @param size the size of the square
          * @return this builder instance
          * @throws GeometryValueException if the width or height of the defined rectangle is zero
          *      as evaluated by the precision context.
          */
         public Builder addSquare(final Vector2D corner, final double size) {
             return addRect(corner, size, size);
         }

         /** Add segments defining an axis-oriented rectangular region with the given center point and size.
          * @param center center point for the region
          * @param xSize size along the x-axis
          * @param ySize size along the y-axis
          * @return this builder instance
          * @throws GeometryValueException if the width or height of the defined rectangle is zero
          *      as evaluated by the precision context.
          */
         public Builder addCenteredRect(final Vector2D center, final double xSize, final double ySize) {
             return addRect(Vector2D.of(
                         center.getX() - (0.5 * xSize),
                         center.getY() - (0.5 * ySize)
                     ), xSize, ySize);
         }

         /** Add segments defining an axis-oriented rectangular region. The region
          * is constructed by taking {@code pt} as one corner of the region and adding {@code xDelta}
          * and {@code yDelta} to its components to create the opposite corner. If {@code xDelta}
          * and {@code yDelta} are both positive, then the constructed rectangle will have {@code pt}
          * as its lower-left corner and will have a width and height of {@code xDelta} and {@code yDelta}
          * respectively.
          * @param pt point lying in a corner of the region
          * @param xDelta distance to move along the x axis to place the other points in the
          *      rectangle; this value may be negative, in which case {@code pt} will lie
          *      on the right side of the constructed rectangle
          * @param yDelta distance to move along the y axis to place the other points in the
          *      rectangle; this value may be negative, in which case {@code pt} will lie
          *      on the top of the rectangle
          * @return this builder instance
          * @throws GeometryValueException if the width or height of the defined rectangle is zero
          *      as evaluated by the precision context.
          */
         public Builder addRect(final Vector2D pt, final double xDelta, final double yDelta) {
             return addRect(pt, Vector2D.of(
                     pt.getX() + xDelta,
                     pt.getY() + yDelta));
         }

         /** Add segments defining an axis-oriented rectangular region. The points {@code a} and {@code b}
          * are taken to represent opposite corner points in the rectangle and may be specified in any order.
          * @param a first corner point in the rectangle (opposite of {@code b})
          * @param b second corner point in the rectangle (opposite of {@code a})
          * @return this builder instance
          * @throws GeometryValueException if the width or height of the defined rectangle is zero
          *      as evaluated by the precision context.
          */
         public Builder addRect(final Vector2D a, final Vector2D b) {
             final double minX = Math.min(a.getX(), b.getX());
             final double maxX = Math.max(a.getX(), b.getX());

             final double minY = Math.min(a.getY(), b.getY());
             final double maxY = Math.max(a.getY(), b.getY());

             if (precision.eq(minX, maxX) || precision.eq(minY, maxY)) {
                 throw new GeometryValueException("Rectangle has zero size: " + a + ", " + b + ".");
             }

             final Vector2D lowerLeft = Vector2D.of(minX, minY);
             final Vector2D upperLeft = Vector2D.of(minX, maxY);

             final Vector2D upperRight = Vector2D.of(maxX, maxY);
             final Vector2D lowerRight = Vector2D.of(maxX, minY);

             addSegment(lowerLeft, lowerRight);
             addSegment(upperRight, upperLeft);
             addSegment(lowerRight, upperRight);
             addSegment(upperLeft, lowerLeft);

             return this;
         }

         /** Get the created BSP tree.
          * @return the created BSP tree
          */
         public RegionBSPTree2D build() {
             return tree;
         }
     }

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

         /** {@inheritDoc} */
         @Override
         protected Vector2D disambiguateClosestPoint(final Vector2D target, final Vector2D a, final Vector2D b) {
             // return the point with the smallest coordinate values
             final int cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
             return cmp < 0 ? a : b;
         }
     }
 }
	/*
	* 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.twod;

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.List;
	import java.util.stream.Collectors;

	import org.apache.commons.geometry.core.exception.GeometryValueException;
	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;
	import org.apache.commons.geometry.core.precision.DoublePrecisionContext;

	/** Binary space partitioning (BSP) tree representing a region in two dimensional
	* Euclidean space.
	*/
	public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D> {
	/** List of line segment paths comprising the region boundary. */
	private List<Polyline> boundaryPaths;

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

	/** Create a new region. If {@code full} is true, then the region will
	* represent the entire 2D space. Otherwise, it will be empty.
	* @param full whether or not the region should contain the entire
	* 2D space or be empty
	*/
	public RegionBSPTree2D(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 RegionBSPTree2D copy() {
	RegionBSPTree2D result = RegionBSPTree2D.empty();
	result.copy(this);

	return result;
	}

	/** {@inheritDoc} */
	@Override
	public Iterable<Segment> boundaries() {
	return createBoundaryIterable(b -> (Segment) b);
	}

	/** {@inheritDoc} */
	@Override
	public List<Segment> getBoundaries() {
	return createBoundaryList(b -> (Segment) b);
	}

	/** Get the boundary of the region as a list of connected line segment paths. The
	* line segments are oriented such that their minus (left) side lies on the
	* interior of the region.
	* @return line segment paths representing the region boundary
	*/
	public List<Polyline> getBoundaryPaths() {
	if (boundaryPaths == null) {
	boundaryPaths = Collections.unmodifiableList(computeBoundaryPaths());
	}
	return boundaryPaths;
	}

	/** Add a convex area to this region. The resulting region will be the
	* union of the convex area and the region represented by this instance.
	* @param area the convex area to add
	*/
	public void add(final ConvexArea area) {
	union(from(area));
	}

	/** Return a list of {@link ConvexArea}s representing the same region
	* as this instance. One convex area is returned for each interior leaf
	* node in the tree.
	* @return a list of convex areas representing the same region as this
	* instance
	*/
	public List<ConvexArea> toConvex() {
	final List<ConvexArea> result = new ArrayList<>();

	toConvexRecursive(getRoot(), ConvexArea.full(), result);

	return result;
	}

	/** Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given
	* node. The computed convex areas are added to the given list.
	* @param node root of the subtree to compute the convex areas for
	* @param nodeArea the convex area for the current node; this will be split by the node's cut hyperplane to
	* form the convex areas for any child nodes
	* @param result list containing the results of the computation
	*/
	private void toConvexRecursive(final RegionNode2D node, final ConvexArea nodeArea, final List<ConvexArea> result) {
	if (node.isLeaf()) {
	// base case; only add to the result list if the node is inside
	if (node.isInside()) {
	result.add(nodeArea);
	}
	} else {
	// recurse
	Split<ConvexArea> split = nodeArea.split(node.getCutHyperplane());

	toConvexRecursive(node.getMinus(), split.getMinus(), result);
	toConvexRecursive(node.getPlus(), split.getPlus(), result);
	}
	}

	/** {@inheritDoc} */
	@Override
	public Split<RegionBSPTree2D> split(final Hyperplane<Vector2D> splitter) {
	return split(splitter, RegionBSPTree2D.empty(), RegionBSPTree2D.empty());
	}

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

	return projector.getProjected();
	}

	/** Compute the line segment paths comprising the region boundary.
	* @return the line segment paths comprising the region boundary
	*/
	private List<Polyline> computeBoundaryPaths() {
	final InteriorAngleSegmentConnector connector = new InteriorAngleSegmentConnector.Minimize();
	connector.connect(boundaries());

	return connector.connectAll().stream()
	.map(Polyline::simplify).collect(Collectors.toList());
	}

	/** {@inheritDoc} */
	@Override
	protected RegionSizeProperties<Vector2D> computeRegionSizeProperties() {
	// handle simple cases
	if (isFull()) {
	return new RegionSizeProperties<>(Double.POSITIVE_INFINITY, null);
	} else if (isEmpty()) {
	return new RegionSizeProperties<>(0, null);
	}

	// compute the size based on the boundary segments
	double quadrilateralAreaSum = 0.0;

	double scaledSumX = 0.0;
	double scaledSumY = 0.0;

	Vector2D startPoint;
	Vector2D endPoint;
	double signedArea;

	for (Segment segment : boundaries()) {

	if (segment.isInfinite()) {
	// at least on boundary is infinite, meaning that
	// the size is also infinite
	quadrilateralAreaSum = Double.POSITIVE_INFINITY;

	break;
	}

	startPoint = segment.getStartPoint();
	endPoint = segment.getEndPoint();

	// compute the area
	signedArea = startPoint.signedArea(endPoint);

	quadrilateralAreaSum += signedArea;

	// compute scaled coordinate values for the barycenter
	scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
	scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
	}

	double size = Double.POSITIVE_INFINITY;
	Vector2D barycenter = null;

	// The area is finite only if the computed quadrilateral area is finite and non-negative.
	// Negative areas indicate that the region is inside-out, with a finite outside surrounded
	// by an infinite inside.
	if (quadrilateralAreaSum >= 0.0 && Double.isFinite(quadrilateralAreaSum)) {
	size = 0.5 * quadrilateralAreaSum;

	if (quadrilateralAreaSum > 0.0) {
	barycenter = Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
	}
	}

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

	/** 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 ConvexArea computeNodeRegion(final RegionNode2D node) {
	ConvexArea area = ConvexArea.full();

	RegionNode2D child = node;
	RegionNode2D parent;

	while ((parent = child.getParent()) != null) {
	Split<ConvexArea> split = area.split(parent.getCutHyperplane());

	area = child.isMinus() ? split.getMinus() : split.getPlus();

	child = parent;
	}

	return area;
	}

	/** {@inheritDoc} */
	@Override
	protected void invalidate() {
	super.invalidate();

	boundaryPaths = null;
	}

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

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

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

	/** Construct a tree from a convex area.
	* @param area the area to construct a tree from
	* @return tree instance representing the same area as the given
	* convex area
	*/
	public static RegionBSPTree2D from(final ConvexArea area) {
	final RegionBSPTree2D tree = RegionBSPTree2D.full();
	tree.insert(area.getBoundaries());

	return tree;
	}

	/** Create a new {@link RegionBSPTree2D.Builder} instance for creating BSP
	* trees from boundary representations.
	* @param precision precision context to use for floating point comparisons.
	* @return a new builder instance
	*/
	public static Builder builder(final DoublePrecisionContext precision) {
	return new Builder(precision);
	}

	/** BSP tree node for two dimensional Euclidean space.
	*/
	public static final class RegionNode2D extends AbstractRegionBSPTree.AbstractRegionNode<Vector2D, RegionNode2D> {
	/** Simple constructor.
	* @param tree the owning tree instance
	*/
	private RegionNode2D(AbstractBSPTree<Vector2D, RegionNode2D> 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 ConvexArea getNodeRegion() {
	return ((RegionBSPTree2D) getTree()).computeNodeRegion(this);
	}

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

	/** Class used to construct {@link RegionBSPTree2D} instances from boundary representations.
	*/
	public static final class Builder {

	/** Precision object used to perform floating point comparisons. This object is
	* used when constructing geometric types.
	*/
	private final DoublePrecisionContext precision;

	/** The BSP tree being constructed. */
	private final RegionBSPTree2D tree = RegionBSPTree2D.empty();

	/** Create a new builder instance. The given precision context will be used when
	* constructing geometric types.
	* @param precision precision object used to perform floating point comparisons
	*/
	public Builder(final DoublePrecisionContext precision) {
	this.precision = precision;
	}

	/** Add a subline to the tree.
	* @param subline subline to add
	* @return this builder instance
	*/
	public Builder add(final SubLine subline) {
	tree.insert(subline);
	return this;
	}

	/** Add a segment to the tree.
	* @param segment segment to add
	* @return this builder instance
	*/
	public Builder add(final Segment segment) {
	tree.insert(segment);
	return this;
	}

	/** Add the line segments defined in the given segment path.
	* @param path path containing line segments to add
	* @return this builder instance
	*/
	public Builder add(final Polyline path) {
	for (Segment segment : path) {
	add(segment);
	}

	return this;
	}

	/** Add a segment defined by the given points.
	* @param start start point
	* @param end end point
	* @return this builder instance
	*/
	public Builder addSegment(final Vector2D start, final Vector2D end) {
	return add(Segment.fromPoints(start, end, precision));
	}

	/** Add segments defining an axis-oriented square with the given corner point and size.
	* @param center center point of the square
	* @param size the size of the square
	* @return this builder instance
	* @throws GeometryValueException if the width or height of the defined rectangle is zero
	* as evaluated by the precision context.
	*/
	public Builder addCenteredSquare(final Vector2D center, final double size) {
	return addCenteredRect(center, size, size);
	}

	/** Add segments defining an axis-oriented square with the given corner point and size.
	* @param corner point in the corner of the square
	* @param size the size of the square
	* @return this builder instance
	* @throws GeometryValueException if the width or height of the defined rectangle is zero
	* as evaluated by the precision context.
	*/
	public Builder addSquare(final Vector2D corner, final double size) {
	return addRect(corner, size, size);
	}

	/** Add segments defining an axis-oriented rectangular region with the given center point and size.
	* @param center center point for the region
	* @param xSize size along the x-axis
	* @param ySize size along the y-axis
	* @return this builder instance
	* @throws GeometryValueException if the width or height of the defined rectangle is zero
	* as evaluated by the precision context.
	*/
	public Builder addCenteredRect(final Vector2D center, final double xSize, final double ySize) {
	return addRect(Vector2D.of(
	center.getX() - (0.5 * xSize),
	center.getY() - (0.5 * ySize)
	), xSize, ySize);
	}

	/** Add segments defining an axis-oriented rectangular region. The region
	* is constructed by taking {@code pt} as one corner of the region and adding {@code xDelta}
	* and {@code yDelta} to its components to create the opposite corner. If {@code xDelta}
	* and {@code yDelta} are both positive, then the constructed rectangle will have {@code pt}
	* as its lower-left corner and will have a width and height of {@code xDelta} and {@code yDelta}
	* respectively.
	* @param pt point lying in a corner of the region
	* @param xDelta distance to move along the x axis to place the other points in the
	* rectangle; this value may be negative, in which case {@code pt} will lie
	* on the right side of the constructed rectangle
	* @param yDelta distance to move along the y axis to place the other points in the
	* rectangle; this value may be negative, in which case {@code pt} will lie
	* on the top of the rectangle
	* @return this builder instance
	* @throws GeometryValueException if the width or height of the defined rectangle is zero
	* as evaluated by the precision context.
	*/
	public Builder addRect(final Vector2D pt, final double xDelta, final double yDelta) {
	return addRect(pt, Vector2D.of(
	pt.getX() + xDelta,
	pt.getY() + yDelta));
	}

	/** Add segments defining an axis-oriented rectangular region. The points {@code a} and {@code b}
	* are taken to represent opposite corner points in the rectangle and may be specified in any order.
	* @param a first corner point in the rectangle (opposite of {@code b})
	* @param b second corner point in the rectangle (opposite of {@code a})
	* @return this builder instance
	* @throws GeometryValueException if the width or height of the defined rectangle is zero
	* as evaluated by the precision context.
	*/
	public Builder addRect(final Vector2D a, final Vector2D b) {
	final double minX = Math.min(a.getX(), b.getX());
	final double maxX = Math.max(a.getX(), b.getX());

	final double minY = Math.min(a.getY(), b.getY());
	final double maxY = Math.max(a.getY(), b.getY());

	if (precision.eq(minX, maxX) \|\| precision.eq(minY, maxY)) {
	throw new GeometryValueException("Rectangle has zero size: " + a + ", " + b + ".");
	}

	final Vector2D lowerLeft = Vector2D.of(minX, minY);
	final Vector2D upperLeft = Vector2D.of(minX, maxY);

	final Vector2D upperRight = Vector2D.of(maxX, maxY);
	final Vector2D lowerRight = Vector2D.of(maxX, minY);

	addSegment(lowerLeft, lowerRight);
	addSegment(upperRight, upperLeft);
	addSegment(lowerRight, upperRight);
	addSegment(upperLeft, lowerLeft);

	return this;
	}

	/** Get the created BSP tree.
	* @return the created BSP tree
	*/
	public RegionBSPTree2D build() {
	return tree;
	}
	}

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

	/** {@inheritDoc} */
	@Override
	protected Vector2D disambiguateClosestPoint(final Vector2D target, final Vector2D a, final Vector2D b) {
	// return the point with the smallest coordinate values
	final int cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
	return cmp < 0 ? a : b;
	}
	}
	}