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);
}
}