ConvexArea.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.euclidean.twod;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;

import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.AbstractConvexHyperplaneBoundedRegion;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector;
import org.apache.commons.geometry.euclidean.twod.path.LinePath;
import org.apache.commons.numbers.core.Precision;

/** Class representing a finite or infinite convex area in Euclidean 2D space.
 * The boundaries of this area, if any, are composed of convex line subsets.
 */
public class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vector2D, LineConvexSubset>
    implements BoundarySource2D {

    /** Error message used when attempting to construct a convex polygon from a non-convex line path. */
    private static final String NON_CONVEX_PATH_ERROR = "Cannot construct convex polygon from non-convex path: ";

    /** Instance representing the full 2D plane. */
    private static final ConvexArea FULL = new ConvexArea(Collections.emptyList());

    /** Simple constructor. 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
     */
    protected ConvexArea(final List<LineConvexSubset> boundaries) {
        super(boundaries);
    }

    /** {@inheritDoc} */
    @Override
    public Stream<LineConvexSubset> boundaryStream() {
        return getBoundaries().stream();
    }

    /** Get the connected line subset paths comprising the boundary of the area. The
     * line subsets are oriented so that their minus sides point toward the interior of the
     * region. The size of the returned list is
     * <ul>
     *      <li><strong>0</strong> if the convex area is full,</li>
     *      <li><strong>1</strong> if at least one boundary is present and
     *          a single path can connect all line subsets (this will be the case
     *          for most instances), and</li>
     *      <li><strong>2</strong> if only two boundaries exist and they are
     *          parallel to each other (in which case they cannot be connected
     *          as a single path).</li>
     * </ul>
     * @return the line subset paths comprising the boundary of the area.
     */
    public List<LinePath> getBoundaryPaths() {
        // use connectMaximized() here since that will prevent us from skipping vertices
        // when there are multiple equivalent vertices to choose from for a given endpoint
        return InteriorAngleLinePathConnector.connectMaximized(getBoundaries());
    }

    /** Get the vertices for the area in a counter-clockwise order. Each vertex in the
     * returned list is unique. If the boundary of the area is closed, the start vertex is
     * <em>not</em> repeated at the end of the list.
     *
     * <p>It is important to note that, in general, the list of vertices returned by this method
     * is not sufficient to completely characterize the area. For example, a simple triangle
     * has 3 vertices, but an infinite area constructed from two parallel lines and two lines that
     * intersect between them will also have 3 vertices. It is also possible for non-empty areas to
     * contain no vertices at all. For example, an area with no boundaries (representing the full
     * space), an area with a single boundary, or an area with two parallel boundaries will not
     * contain any vertices.</p>
     * @return the list of vertices for the area in a counter-clockwise order
     */
    public List<Vector2D> getVertices() {
        final List<LinePath> paths = getBoundaryPaths();

        // we will only have vertices if we have a single path; otherwise, we have a full
        // area or two non-intersecting infinite line subsets
        if (paths.size() == 1) {
            final LinePath path = paths.get(0);
            final List<Vector2D> vertices = path.getVertexSequence();

            if (path.isClosed()) {
                // do not include the repeated start point
                return vertices.subList(0, vertices.size() - 1);
            }
            return vertices;
        }

        return Collections.emptyList();
    }

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

    /** {@inheritDoc} */
    @Override
    public LineConvexSubset trim(final HyperplaneConvexSubset<Vector2D> convexSubset) {
        return (LineConvexSubset) super.trim(convexSubset);
    }

    /** {@inheritDoc} */
    @Override
    public double getSize() {
        if (isFull()) {
            return Double.POSITIVE_INFINITY;
        }

        double quadrilateralAreaSum = 0.0;

        for (final LineConvexSubset boundary : getBoundaries()) {
            if (boundary.isInfinite()) {
                return Double.POSITIVE_INFINITY;
            }

            quadrilateralAreaSum += boundary.getStartPoint().signedArea(boundary.getEndPoint());
        }

        return 0.5 * quadrilateralAreaSum;
    }

    /** {@inheritDoc} */
    @Override
    public Vector2D getCentroid() {
        final List<LineConvexSubset> boundaries = getBoundaries();

        double quadrilateralAreaSum = 0.0;
        double scaledSumX = 0.0;
        double scaledSumY = 0.0;

        double signedArea;
        Vector2D startPoint;
        Vector2D endPoint;

        for (final LineConvexSubset seg : boundaries) {
            if (seg.isInfinite()) {
                // infinite => no centroid
                return null;
            }

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

            signedArea = startPoint.signedArea(endPoint);

            quadrilateralAreaSum += signedArea;

            scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
            scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
        }

        if (quadrilateralAreaSum > 0) {
            return Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
        }

        return null;
    }

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

    /** Return a BSP tree representing the same region as this instance.
     */
    @Override
    public RegionBSPTree2D toTree() {
        return RegionBSPTree2D.from(getBoundaries(), true);
    }

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

    /** Construct a convex polygon from the given vertices.
     * @param vertices vertices to use to construct the polygon
     * @param precision precision context used for floating point comparisons
     * @return a convex polygon constructed using the given vertices
     * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
     * @throws IllegalArgumentException if the constructed path does not define a closed, convex polygon
     * @see LinePath#fromVertexLoop(Collection, Precision.DoubleEquivalence)
     */
    public static ConvexArea convexPolygonFromVertices(final Collection<Vector2D> vertices,
            final Precision.DoubleEquivalence precision) {
        return convexPolygonFromPath(LinePath.fromVertexLoop(vertices, precision));
    }

    /** Construct a convex polygon from a line path.
     * @param path path to construct the polygon from
     * @return a convex polygon constructed from the given line path
     * @throws IllegalArgumentException if the path does not define a closed, convex polygon
     */
    public static ConvexArea convexPolygonFromPath(final LinePath path) {
        // ensure that the path is closed; this also ensures that we do not have any infinite elements
        if (!path.isClosed()) {
            throw new IllegalArgumentException("Cannot construct convex polygon from unclosed path: " + path);
        }

        final List<LineConvexSubset> elements = path.getElements();
        if (elements.size() < 3) {
            throw new IllegalArgumentException(
                    "Cannot construct convex polygon from path with less than 3 elements: " + path);
        }

        // go through the elements and validate that the produced area is convex and finite
        // using the precision context from the first path element
        final LineConvexSubset startElement = elements.get(0);
        final Vector2D startVertex = startElement.getStartPoint();
        final Precision.DoubleEquivalence precision = startElement.getPrecision();

        Vector2D curVector;
        Vector2D prevVector = null;

        double signedArea;
        double totalSignedArea = 0.0;

        LineConvexSubset element;

        // we can skip the last element since the we know that the path is closed, meaning that the
        // last element's end point is equal to our start point
        for (int i = 0; i < elements.size() - 1; ++i) {
            element = elements.get(i);

            curVector = startVertex.vectorTo(element.getEndPoint());

            if (prevVector != null) {
                signedArea = prevVector.signedArea(curVector);
                if (precision.lt(signedArea, 0.0)) {
                    throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
                }

                totalSignedArea += signedArea;
            }

            prevVector = curVector;
        }

        if (precision.lte(totalSignedArea, 0.0)) {
            throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
        }

        return new ConvexArea(elements);
    }

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

    /** Create a convex area formed by the intersection of the negative half-spaces of the
     * given bounding lines. The returned instance represents the area that is on the
     * minus side of all of the given lines. Note that this method does not support areas
     * of zero size (ie, infinitely thin areas or points.)
     * @param bounds lines used to define the convex area
     * @return a new convex area instance representing the area on the minus side of all
     *      of the bounding lines or an instance representing the full area if the collection
     *      is empty
     * @throws IllegalArgumentException if the given set of bounding lines do not form a convex area,
     *      meaning that there is no region that is on the minus side of all of the bounding lines.
     */
    public static ConvexArea fromBounds(final Iterable<Line> bounds) {
        final List<LineConvexSubset> subsets =
                new ConvexRegionBoundaryBuilder<>(LineConvexSubset.class).build(bounds);
        return subsets.isEmpty() ? full() : new ConvexArea(subsets);
    }
}