commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/ConvexArea2S.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.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.commons.geometry.core.Geometry;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.AbstractConvexHyperplaneBoundedRegion;
import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.euclidean.threed.Vector3D;

/** Class representing a convex area in 2D spherical space. The boundaries of this
 * area, if any, are composed of convex great circle arcs.
 */
public final class ConvexArea2S extends AbstractConvexHyperplaneBoundedRegion<Point2S, GreatArc> {
    /** Instance representing the full spherical area. */
    private static final ConvexArea2S FULL = new ConvexArea2S(Collections.emptyList());

    /** Constant containing the area of the full spherical space. */
    private static final double FULL_SIZE = 4 * Geometry.PI;

    /** Constant containing the area of half of the spherical space. */
    private static final double HALF_SIZE = Geometry.TWO_PI;

    /** Construct an instance from its boundaries. Callers are responsible for ensuring
     * that the given path represents the boundary of a convex area. No validation is
     * performed.
     * @param boundaries the boundaries of the convex area
     */
    private ConvexArea2S(final List<GreatArc> boundaries) {
        super(boundaries);
    }

    /** Get a path instance representing the boundary of the area. The path is oriented
     * so that the minus sides of the arcs lie on the inside of the area.
     * @return the boundary path of the area
     */
    public GreatArcPath getBoundaryPath() {
        final List<GreatArcPath> paths = InteriorAngleGreatArcConnector.connectMinimized(getBoundaries());
        if (paths.isEmpty()) {
            return GreatArcPath.empty();
        }

        return paths.get(0);
    }

    /** Get an array of interior angles for the area. An empty array is returned if there
     * are no boundary intersections (ie, it has only one boundary or no boundaries at all).
     *
     * <p>The order of the angles corresponds with the order of the boundaries returned
     * by {@link #getBoundaries()}: if {@code i} is an index into the boundaries list,
     * then {@code angles[i]} is the angle between boundaries {@code i} and {@code (i+1) % boundariesSize}.</p>
     * @return an array of interior angles for the area
     */
    public double[] getInteriorAngles() {
        final List<GreatArc> arcs = getBoundaryPath().getArcs();
        final int numSides = arcs.size();

        if (numSides < 2) {
            return new double[0];
        }

        final double[] angles = new double[numSides];

        GreatArc current;
        GreatArc next;
        for (int i = 0; i < numSides; ++i) {
            current = arcs.get(i);
            next = arcs.get((i + 1) % numSides);

            angles[i] = Geometry.PI - current.getCircle()
                    .angle(next.getCircle(), current.getEndPoint());
        }

        return angles;
    }

    /** {@inheritDoc} */
    @Override
    public double getSize() {
        final int numSides = getBoundaries().size();

        if (numSides == 0) {
            return FULL_SIZE;
        } else if (numSides == 1) {
            return HALF_SIZE;
        } else {
            // use the extended version of Girard's theorem
            // https://en.wikipedia.org/wiki/Spherical_trigonometry#Girard's_theorem
            final double[] angles = getInteriorAngles();
            final double sum = Arrays.stream(angles).sum();

            return sum - ((angles.length - 2) * Geometry.PI);
        }
    }

    /** {@inheritDoc} */
    @Override
    public Point2S getBarycenter() {
        List<GreatArc> arcs = getBoundaries();
        int numSides = arcs.size();

        if (numSides == 0) {
            // full space; no barycenter
            return null;
        } else if (numSides == 1) {
            // hemisphere; barycenter is the pole of the hemisphere
            return arcs.get(0).getCircle().getPolePoint();
        } else {
            // 2 or more sides; use an extension of the approach outlined here:
            // https://archive.org/details/centroidinertiat00broc
            // In short, the barycenter is the sum of the pole vectors of each side
            // multiplied by their arc lengths.
            Vector3D barycenter = Vector3D.ZERO;

            for (GreatArc arc : getBoundaries()) {
                barycenter = Vector3D.linearCombination(
                        1, barycenter,
                        arc.getSize(), arc.getCircle().getPole());
            }

            return Point2S.from(barycenter);
        }
    }

    /** {@inheritDoc} */
    @Override
    public Split<ConvexArea2S> split(final Hyperplane<Point2S> splitter) {
        return splitInternal(splitter, this, GreatArc.class, ConvexArea2S::new);
    }

    /** Return a new instance transformed by the argument.
     * @param transform transform to apply
     * @return a new instance transformed by the argument
     */
    public ConvexArea2S transform(final Transform<Point2S> transform) {
        return transformInternal(transform, this, GreatArc.class, ConvexArea2S::new);
    }

    /** {@inheritDoc} */
    @Override
    public GreatArc trim(final ConvexSubHyperplane<Point2S> convexSubHyperplane) {
        return (GreatArc) super.trim(convexSubHyperplane);
    }

    /** Return a BSP tree instance representing the same region as the current instance.
     * @return a BSP tree instance representing the same region as the current instance
     */
    public RegionBSPTree2S toTree() {
        return RegionBSPTree2S.from(this);
    }

    /** Return an instance representing the full spherical 2D space.
     * @return an instance representing the full spherical 2D space.
     */
    public static ConvexArea2S full() {
        return FULL;
    }

    /** Construct a convex area by creating great circles between adjacent vertices. The vertices must be given
     * in a counter-clockwise around order the interior of the shape. If the area is intended to be closed, the
     * beginning point must be repeated at the end of the path.
     * @param vertices vertices to use to construct the area
     * @param precision precision context used to create new great circle instances
     * @return a convex area constructed using great circles between adjacent vertices
     * @see #fromVertexLoop(Collection, DoublePrecisionContext)
     */
    public static ConvexArea2S fromVertices(final Collection<Point2S> vertices,
            final DoublePrecisionContext precision) {
        return fromVertices(vertices, false, precision);
    }

    /** Construct a convex area by creating great circles between adjacent vertices. An implicit great circle is
     * created between the last vertex given and the first one, if needed. The vertices must be given in a
     * counter-clockwise around order the interior of the shape.
     * @param vertices vertices to use to construct the area
     * @param precision precision context used to create new great circles instances
     * @return a convex area constructed using great circles between adjacent vertices
     * @see #fromVertices(Collection, DoublePrecisionContext)
     */
    public static ConvexArea2S fromVertexLoop(final Collection<Point2S> vertices,
            final DoublePrecisionContext precision) {
        return fromVertices(vertices, true, precision);
    }

    /** Construct a convex area from great circles between adjacent vertices.
     * @param vertices vertices to use to construct the area
     * @param close if true, an additional great circle will be created between the last and first vertex
     * @param precision precision context used to create new great circle instances
     * @return a convex area constructed using great circles between adjacent vertices
     */
    public static ConvexArea2S fromVertices(final Collection<Point2S> vertices, final boolean close,
            final DoublePrecisionContext precision) {

        if (vertices.isEmpty()) {
            return full();
        }

        final List<GreatCircle> circles = new ArrayList<>();

        Point2S first = null;
        Point2S prev = null;
        Point2S cur = null;

        for (Point2S vertex : vertices) {
            cur = vertex;

            if (first == null) {
                first = cur;
            }

            if (prev != null && !cur.eq(prev, precision)) {
                circles.add(GreatCircle.fromPoints(prev, cur, precision));
            }

            prev = cur;
        }

        if (close && cur != null && !cur.eq(first, precision)) {
            circles.add(GreatCircle.fromPoints(cur, first, precision));
        }

        if (!vertices.isEmpty() && circles.isEmpty()) {
            throw new IllegalStateException("Unable to create convex area: only a single unique vertex provided");
        }

        return fromBounds(circles);
    }

    /** Construct a convex area from an arc path. The area represents the intersection of all of the negative
     * half-spaces of the great circles in the path. The boundaries of the returned area may therefore not match
     * the arcs in the path.
     * @param path path to construct the area from
     * @return a convex area constructed from the great circles in the given path
     */
    public static ConvexArea2S fromPath(final GreatArcPath path) {
        final List<GreatCircle> bounds = path.getArcs().stream()
                .map(a -> a.getCircle())
                .collect(Collectors.toList());

        return fromBounds(bounds);
    }

    /** Create a convex area formed by the intersection of the negative half-spaces of the
     * given bounding great circles. The returned instance represents the area that is on the
     * minus side of all of the given circles. Note that this method does not support areas
     * of zero size (ie, infinitely thin areas or points.)
     * @param bounds great circles used to define the convex area
     * @return a new convex area instance representing the area on the minus side of all
     *      of the bounding great circles or an instance representing the full area if no
     *      circles are given
     * @throws org.apache.commons.geometry.core.exception.GeometryException if the given set of bounding great
     *      circles do not form a convex area, meaning that there is no region that is on the minus side of all
     *      of the bounding circles.
     */
    public static ConvexArea2S fromBounds(final GreatCircle... bounds) {
        return fromBounds(Arrays.asList(bounds));
    }

    /** Create a convex area formed by the intersection of the negative half-spaces of the
     * given bounding great circles. The returned instance represents the area that is on the
     * minus side of all of the given circles. Note that this method does not support areas
     * of zero size (ie, infinitely thin areas or points.)
     * @param bounds great circles used to define the convex area
     * @return a new convex area instance representing the area on the minus side of all
     *      of the bounding great circles or an instance representing the full area if no
     *      circles are given
     * @throws org.apache.commons.geometry.core.exception.GeometryException if the given set of bounding great
     *      circles do not form a convex area, meaning that there is no region that is on the minus side of all
     *      of the bounding circles.
     */
    public static ConvexArea2S fromBounds(final Iterable<GreatCircle> bounds) {
        final List<GreatArc> arcs = new ConvexRegionBoundaryBuilder<>(GreatArc.class).build(bounds);
        return arcs.isEmpty() ?
                full() :
                new ConvexArea2S(arcs);
    }
}