RegionBSPTree1S.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.oned;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
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.twod.Vector2D;
import org.apache.commons.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;

/** BSP tree representing regions in 1D spherical space.
 */
public class RegionBSPTree1S extends AbstractRegionBSPTree<Point1S, RegionBSPTree1S.RegionNode1S> {
    /** Comparator used to sort BoundaryPairs by ascending azimuth.  */
    private static final Comparator<BoundaryPair> BOUNDARY_PAIR_COMPARATOR =
            Comparator.comparingDouble(BoundaryPair::getMinValue);

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

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

    /** {@inheritDoc} */
    @Override
    public Point1S project(final Point1S pt) {
        final BoundaryProjector1S projector = new BoundaryProjector1S(pt);
        accept(projector);

        return projector.getProjected();
    }

    /** {@inheritDoc}
     *
     * <p>Each interval of the region is transformed individually and the
     * results are unioned. If the size of any transformed interval is greater
     * than or equal to 2pi, then the region is set to the full space.</p>
     */
    @Override
    public void transform(final Transform<Point1S> transform) {
        if (!isFull() && !isEmpty()) {
            // transform each interval individually to handle wrap-around
            final List<AngularInterval> intervals = toIntervals();

            setEmpty();

            for (final AngularInterval interval : intervals) {
                union(interval.transform(transform).toTree());
            }
        }
    }

    /** {@inheritDoc}
     *
     * <p>It is important to note that split operations occur according to the rules of the
     * {@link CutAngle} hyperplane class. In this class, the continuous circle is viewed
     * as a non-circular segment of the number line in the range {@code [0, 2pi)}. Hyperplanes
     * are placed along this line and partition it into the segments {@code [0, x]}
     * and {@code [x, 2pi)}, where {@code x} is the location of the hyperplane. For example,
     * a positive-facing {@link CutAngle} instance with an azimuth of {@code 0.5pi} has
     * a minus side consisting of the angles {@code [0, 0.5pi]} and a plus side consisting of
     * the angles {@code [0.5pi, 2pi)}. Similarly, a positive-facing {@link CutAngle} with
     * an azimuth of {@code 0pi} has a plus side of {@code [0, 2pi)} (the full space) and
     * a minus side that is completely empty (since no points exist in our domain that are
     * less than zero). These rules can result in somewhat non-intuitive behavior at times.
     * For example, splitting a non-empty region with a hyperplane at {@code 0pi} is
     * essentially a no-op, since the region will either lie entirely on the plus or minus
     * side of the hyperplane (depending on the hyperplane's orientation) regardless of the actual
     * content of the region. In these situations, a copy of the tree is returned on the
     * appropriate side of the split.</p>
     *
     * @see CutAngle
     * @see #splitDiameter(CutAngle)
     */
    @Override
    public Split<RegionBSPTree1S> split(final Hyperplane<Point1S> splitter) {
        // Handle the special case where the cut is on the azimuth equivalent to zero.
        // In this case, it is not possible for any points to lie between it and zero.
        if (!isEmpty() && splitter.classify(Point1S.ZERO) == HyperplaneLocation.ON) {
            final CutAngle cut = (CutAngle) splitter;
            if (cut.isPositiveFacing()) {
                return new Split<>(null, copy());
            } else {
                return new Split<>(copy(), null);
            }
        }

        return split(splitter, RegionBSPTree1S.empty(), RegionBSPTree1S.empty());
    }

    /** Split the instance along a circle diameter.The diameter is defined by the given
     * split point and its reversed antipodal point.
     * @param splitter split point defining one side of the split diameter
     * @return result of the split operation
     */
    public Split<RegionBSPTree1S> splitDiameter(final CutAngle splitter) {

        final CutAngle opposite = CutAngles.fromPointAndDirection(
                splitter.getPoint().antipodal(),
                !splitter.isPositiveFacing(),
                splitter.getPrecision());

        final double plusPoleOffset = splitter.isPositiveFacing() ?
                +Angle.PI_OVER_TWO :
                -Angle.PI_OVER_TWO;
        final Point1S plusPole = Point1S.of(splitter.getAzimuth() + plusPoleOffset);

        final boolean zeroOnPlusSide = splitter.getPrecision()
                .lte(plusPole.distance(Point1S.ZERO), Angle.PI_OVER_TWO);

        final Split<RegionBSPTree1S> firstSplit = split(splitter);
        final Split<RegionBSPTree1S> secondSplit = split(opposite);

        RegionBSPTree1S minus = RegionBSPTree1S.empty();
        RegionBSPTree1S plus = RegionBSPTree1S.empty();

        if (zeroOnPlusSide) {
            // zero wrap-around needs to be handled on the plus side of the split
            safeUnion(plus, firstSplit.getPlus());
            safeUnion(plus, secondSplit.getPlus());

            minus = firstSplit.getMinus();
            if (minus != null) {
                minus = minus.split(opposite).getMinus();
            }
        } else {
            // zero wrap-around needs to be handled on the minus side of the split
            safeUnion(minus, firstSplit.getMinus());
            safeUnion(minus, secondSplit.getMinus());

            plus = firstSplit.getPlus();
            if (plus != null) {
                plus = plus.split(opposite).getPlus();
            }
        }

        return new Split<>(
                (minus != null && !minus.isEmpty()) ? minus : null,
                (plus != null && !plus.isEmpty()) ? plus : null);
    }


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

        final List<BoundaryPair> insideBoundaryPairs = new ArrayList<>();
        for (final RegionNode1S node : nodes()) {
            if (node.isInside()) {
                insideBoundaryPairs.add(getNodeBoundaryPair(node));
            }
        }

        insideBoundaryPairs.sort(BOUNDARY_PAIR_COMPARATOR);

        final int boundaryPairCount = insideBoundaryPairs.size();

        // Get the start point for merging intervals together.
        final int startOffset = getIntervalStartIndex(insideBoundaryPairs);

        // Go through the pairs starting at the start offset and create intervals
        // for each set of adjacent pairs.
        final List<AngularInterval> intervals = new ArrayList<>();

        BoundaryPair start = null;
        BoundaryPair end = null;
        BoundaryPair current;

        for (int i = 0; i < boundaryPairCount; ++i) {
            current = insideBoundaryPairs.get((i + startOffset) % boundaryPairCount);

            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 be separate
                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;
    }

    /** Get the index that should be used as the starting point for combining adjacent boundary pairs
     * into contiguous intervals. This is computed as the first boundary pair found that is not connected
     * to the pair before it, or {@code 0} if no such entry exists.
     * @param boundaryPairs list of boundary pairs to search; must be ordered by increasing azimuth
     * @return the index to use as a starting place for combining adjacent boundary pairs
     *      into contiguous intervals
     */
    private int getIntervalStartIndex(final List<BoundaryPair> boundaryPairs) {
        final int size = boundaryPairs.size();

        if (size > 0) {
            BoundaryPair current;
            BoundaryPair previous = boundaryPairs.get(size - 1);

            for (int i = 0; i < size; ++i, previous = current) {
                current = boundaryPairs.get(i);

                if (!Objects.equals(current.getMin(), previous.getMax())) {
                    return i;
                }
            }
        }

        return 0;
    }

    /** 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 AngularInterval createInterval(final BoundaryPair start, final BoundaryPair end) {
        CutAngle min = start.getMin();
        CutAngle max = end.getMax();

        final Precision.DoubleEquivalence precision = (min != null) ? min.getPrecision() : max.getPrecision();

        // 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) {
            if (min.isPositiveFacing()) {
                min = min.reverse();
            }
        } else {
            min = CutAngles.createNegativeFacing(0.0, precision);
        }

        if (max != null) {
            if (!max.isPositiveFacing()) {
                max = max.reverse();
            }
        } else {
            max = CutAngles.createPositiveFacing(Angle.TWO_PI, precision);
        }

        return AngularInterval.of(min, max);
    }

    /** Return the min/max boundary pair for the convex region represented by the given node.
     * @param node the node to compute the interval for
     * @return the min/max boundary pair for the convex region represented by the given node
     */
    private BoundaryPair getNodeBoundaryPair(final RegionNode1S node) {
        CutAngle min = null;
        CutAngle max = null;

        CutAngle pt;
        RegionNode1S child = node;
        RegionNode1S parent;

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

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

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

            child = parent;
        }

        return new BoundaryPair(min, max);
    }

    /** {@inheritDoc} */
    @Override
    protected RegionSizeProperties<Point1S> computeRegionSizeProperties() {
        if (isFull()) {
            return new RegionSizeProperties<>(Angle.TWO_PI, null);
        } else if (isEmpty()) {
            return new RegionSizeProperties<>(0, null);
        }

        double size = 0;
        Vector2D scaledCentroidSum = Vector2D.ZERO;

        double intervalSize;

        for (final AngularInterval interval : toIntervals()) {
            intervalSize = interval.getSize();

            size += intervalSize;
            scaledCentroidSum = scaledCentroidSum.add(interval.getCentroid().getVector().withNorm(intervalSize));
        }

        final Precision.DoubleEquivalence precision = ((CutAngle) getRoot().getCutHyperplane()).getPrecision();

        final Point1S centroid = scaledCentroidSum.eq(Vector2D.ZERO, precision) ?
                 null :
                 Point1S.from(scaledCentroidSum);

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

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

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

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

    /** Return a new BSP tree representing the same region as the given angular interval.
     * @param interval the input interval
     * @return a new BSP tree representing the same region as the given angular interval
     */
    public static RegionBSPTree1S fromInterval(final AngularInterval interval) {
        final CutAngle minBoundary = interval.getMinBoundary();
        final CutAngle maxBoundary = interval.getMaxBoundary();

        final RegionBSPTree1S tree = full();

        if (minBoundary != null) {
            tree.insert(minBoundary.span());
        }

        if (maxBoundary != null) {
            tree.insert(maxBoundary.span());
        }

        return tree;
    }

    /** Perform a union operation with {@code target} and {@code input}, storing the result
     * in {@code target}; does nothing if {@code input} is null.
     * @param target target tree
     * @param input input tree
     */
    private static void safeUnion(final RegionBSPTree1S target, final RegionBSPTree1S input) {
        if (input != null) {
            target.union(input);
        }
    }

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

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

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

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

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

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

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

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

        /** Get the minimum value of the interval or zero if no minimum value exists.
         * @return the minimum value of the interval or zero
         *      if no minimum value exists.
         */
        public double getMinValue() {
            return (min != null) ? min.getNormalizedAzimuth() : 0;
        }
    }

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

        /** {@inheritDoc} */
        @Override
        protected boolean isPossibleClosestCut(final HyperplaneSubset<Point1S> cut, final Point1S target,
                final double minDist) {
            // since the space wraps around, consider any cut as possibly being the closest
            return true;
        }

        /** {@inheritDoc} */
        @Override
        protected Point1S disambiguateClosestPoint(final Point1S target, final Point1S a, final Point1S b) {
            // prefer the point with the smaller normalize azimuth value
            return a.getNormalizedAzimuth() < b.getNormalizedAzimuth() ? a : b;
        }
    }
}