RegionBSPTree2S.java

/*
 * 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.spherical.twod;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

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.euclidean.threed.Vector3D;
import org.apache.commons.numbers.core.Precision;
import org.apache.commons.numbers.core.Sum;

/** BSP tree representing regions in 2D spherical space.
 */
public class RegionBSPTree2S extends AbstractRegionBSPTree<Point2S, RegionBSPTree2S.RegionNode2S>
    implements BoundarySource2S {
    /** Constant containing the area of the full spherical space. */
    private static final double FULL_SIZE = 4 * Math.PI;

    /** List of great arc path comprising the region boundary. */
    private List<GreatArcPath> boundaryPaths;

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

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

        return result;
    }

    /** {@inheritDoc} */
    @Override
    public Iterable<GreatArc> boundaries() {
        return createBoundaryIterable(GreatArc.class::cast);
    }

    /** {@inheritDoc} */
    @Override
    public Stream<GreatArc> boundaryStream() {
        return StreamSupport.stream(boundaries().spliterator(), false);
    }

    /** {@inheritDoc} */
    @Override
    public List<GreatArc> getBoundaries() {
        return createBoundaryList(GreatArc.class::cast);
    }

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

    /** Return a list of {@link ConvexArea2S}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<ConvexArea2S> toConvex() {
        final List<ConvexArea2S> result = new ArrayList<>();

        toConvexRecursive(getRoot(), ConvexArea2S.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 RegionNode2S node, final ConvexArea2S nodeArea,
            final List<? super ConvexArea2S> 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
            final Split<ConvexArea2S> split = nodeArea.split(node.getCutHyperplane());

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

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

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

        return projector.getProjected();
    }

    /** Return the current instance.
     */
    @Override
    public RegionBSPTree2S toTree() {
        return this;
    }

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

        final List<ConvexArea2S> areas = toConvex();
        final Precision.DoubleEquivalence precision = ((GreatArc) getRoot().getCut()).getPrecision();

        final Sum sizeSum = Sum.create();
        final Vector3D.Sum centroidVectorSum = Vector3D.Sum.create();

        double maxCentroidVectorWeightSq = 0.0;

        for (final ConvexArea2S area : areas) {
            sizeSum.add(area.getSize());

            final Vector3D areaCentroidVector = area.getWeightedCentroidVector();
            maxCentroidVectorWeightSq = Math.max(maxCentroidVectorWeightSq, areaCentroidVector.normSq());

            centroidVectorSum.add(areaCentroidVector);
        }

        final double size = sizeSum.getAsDouble();
        final Vector3D centroidVector = centroidVectorSum.get();

        // Convert the weighted centroid vector to a point on the sphere surface. If the centroid vector
        // length is less than the max length of the combined convex areas and the vector itself is
        // equivalent to zero, then we know that there are opposing and approximately equal areas in the
        // region, resulting in an indeterminate centroid. This would occur, for example, if there were
        // equal areas around each pole.
        final Point2S centroid;
        if (centroidVector.normSq() < maxCentroidVectorWeightSq &&
                centroidVector.eq(Vector3D.ZERO, precision)) {
            centroid = null;
        } else {
            centroid = Point2S.from(centroidVector);
        }

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

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

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

        boundaryPaths = null;
    }

    /** Compute the great arc paths comprising the region boundary.
     * @return the great arc paths comprising the region boundary
     */
    private List<GreatArcPath> computeBoundaryPaths() {
        final InteriorAngleGreatArcConnector connector = new InteriorAngleGreatArcConnector.Minimize();
        return connector.connectAll(boundaries());
    }

    /** Return a new, empty BSP tree.
     * @return a new, empty BSP tree.
     */
    public static RegionBSPTree2S empty() {
        return new RegionBSPTree2S(false);
    }

    /** Return a new, full BSP tree. The returned tree represents the
     * full space.
     * @return a new, full BSP tree.
     */
    public static RegionBSPTree2S full() {
        return new RegionBSPTree2S(true);
    }

    /** Construct a new tree from the given boundaries. If no boundaries
     * are present, the returned tree is empty.
     * @param boundaries boundaries to construct the tree from
     * @return a new tree instance constructed from the given boundaries
     * @see #from(Iterable, boolean)
     */
    public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries) {
        return from(boundaries, false);
    }

    /** Construct a new tree from the given boundaries. If {@code full} is true, then
     * the initial tree before boundary insertion contains the entire space. Otherwise,
     * it is empty.
     * @param boundaries boundaries to construct the tree from
     * @param full if true, the initial tree will contain the entire space
     * @return a new tree instance constructed from the given boundaries
     */
    public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries, final boolean full) {
        final RegionBSPTree2S tree = new RegionBSPTree2S(full);
        tree.insert(boundaries);

        return tree;
    }

    /** BSP tree node for two dimensional spherical space.
     */
    public static final class RegionNode2S extends AbstractRegionBSPTree.AbstractRegionNode<Point2S, RegionNode2S> {
        /** Simple constructor.
         * @param tree tree owning the instance.
         */
        private RegionNode2S(final AbstractBSPTree<Point2S, RegionNode2S> 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 ConvexArea2S getNodeRegion() {
            ConvexArea2S area = ConvexArea2S.full();

            RegionNode2S child = this;
            RegionNode2S parent;

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

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

                child = parent;
            }

            return area;
        }

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

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

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