View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.euclidean.twod;
    18
    19  import java.util.Arrays;
    20  import java.util.Collection;
    21  import java.util.Collections;
    22  import java.util.List;
    23  import java.util.stream.Stream;
    24
    25  import org.apache.commons.geometry.core.Transform;
    26  import org.apache.commons.geometry.core.partitioning.AbstractConvexHyperplaneBoundedRegion;
    27  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    28  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    29  import org.apache.commons.geometry.core.partitioning.Split;
    30  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    31  import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector;
    32  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    33
    34  /** Class representing a finite or infinite convex area in Euclidean 2D space.
    35   * The boundaries of this area, if any, are composed of convex line subsets.
    36   */
    37  public class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vector2D, LineConvexSubset>
    38      implements BoundarySource2D {
    39
    40      /** Error message used when attempting to construct a convex polygon from a non-convex line path. */
    41      private static final String NON_CONVEX_PATH_ERROR = "Cannot construct convex polygon from non-convex path: ";
    42
    43      /** Instance representing the full 2D plane. */
    44      private static final ConvexArea FULL = new ConvexArea(Collections.emptyList());
    45
    46      /** Simple constructor. Callers are responsible for ensuring that the given path
    47       * represents the boundary of a convex area. No validation is performed.
    48       * @param boundaries the boundaries of the convex area
    49       */
    50      protected ConvexArea(final List<LineConvexSubset> boundaries) {
    51          super(boundaries);
    52      }
    53
    54      /** {@inheritDoc} */
    55      @Override
    56      public Stream<LineConvexSubset> boundaryStream() {
    57          return getBoundaries().stream();
    58      }
    59
    60      /** Get the connected line subset paths comprising the boundary of the area. The
    61       * line subsets are oriented so that their minus sides point toward the interior of the
    62       * region. The size of the returned list is
    63       * <ul>
    64       *      <li><strong>0</strong> if the convex area is full,</li>
    65       *      <li><strong>1</strong> if at least one boundary is present and
    66       *          a single path can connect all line subsets (this will be the case
    67       *          for most instances), and</li>
    68       *      <li><strong>2</strong> if only two boundaries exist and they are
    69       *          parallel to each other (in which case they cannot be connected
    70       *          as a single path).</li>
    71       * </ul>
    72       * @return the line subset paths comprising the boundary of the area.
    73       */
    74      public List<LinePath> getBoundaryPaths() {
    75          // use connectMaximized() here since that will prevent us from skipping vertices
    76          // when there are multiple equivalent vertices to choose from for a given endpoint
    77          return InteriorAngleLinePathConnector.connectMaximized(getBoundaries());
    78      }
    79
    80      /** Get the vertices for the area in a counter-clockwise order. Each vertex in the
    81       * returned list is unique. If the boundary of the area is closed, the start vertex is
    82       * <em>not</em> repeated at the end of the list.
    83       *
    84       * <p>It is important to note that, in general, the list of vertices returned by this method
    85       * is not sufficient to completely characterize the area. For example, a simple triangle
    86       * has 3 vertices, but an infinite area constructed from two parallel lines and two lines that
    87       * intersect between them will also have 3 vertices. It is also possible for non-empty areas to
    88       * contain no vertices at all. For example, an area with no boundaries (representing the full
    89       * space), an area with a single boundary, or an area with two parallel boundaries will not
    90       * contain any vertices.</p>
    91       * @return the list of vertices for the area in a counter-clockwise order
    92       */
    93      public List<Vector2D> getVertices() {
    94          final List<LinePath> paths = getBoundaryPaths();
    95
    96          // we will only have vertices if we have a single path; otherwise, we have a full
    97          // area or two non-intersecting infinite line subsets
    98          if (paths.size() == 1) {
    99              final LinePath path = paths.get(0);
    100             final List<Vector2D> vertices = path.getVertexSequence();
    101
    102             if (path.isClosed()) {
    103                 // do not include the repeated start point
    104                 return vertices.subList(0, vertices.size() - 1);
    105             }
    106             return vertices;
    107         }
    108
    109         return Collections.emptyList();
    110     }
    111
    112     /** Return a new instance transformed by the argument.
    113      * @param transform transform to apply
    114      * @return a new instance transformed by the argument
    115      */
    116     public ConvexArea transform(final Transform<Vector2D> transform) {
    117         return transformInternal(transform, this, LineConvexSubset.class, ConvexArea::new);
    118     }
    119
    120     /** {@inheritDoc} */
    121     @Override
    122     public LineConvexSubset trim(final HyperplaneConvexSubset<Vector2D> convexSubset) {
    123         return (LineConvexSubset) super.trim(convexSubset);
    124     }
    125
    126     /** {@inheritDoc} */
    127     @Override
    128     public double getSize() {
    129         if (isFull()) {
    130             return Double.POSITIVE_INFINITY;
    131         }
    132
    133         double quadrilateralAreaSum = 0.0;
    134
    135         for (final LineConvexSubset boundary : getBoundaries()) {
    136             if (boundary.isInfinite()) {
    137                 return Double.POSITIVE_INFINITY;
    138             }
    139
    140             quadrilateralAreaSum += boundary.getStartPoint().signedArea(boundary.getEndPoint());
    141         }
    142
    143         return 0.5 * quadrilateralAreaSum;
    144     }
    145
    146     /** {@inheritDoc} */
    147     @Override
    148     public Vector2D getCentroid() {
    149         final List<LineConvexSubset> boundaries = getBoundaries();
    150
    151         double quadrilateralAreaSum = 0.0;
    152         double scaledSumX = 0.0;
    153         double scaledSumY = 0.0;
    154
    155         double signedArea;
    156         Vector2D startPoint;
    157         Vector2D endPoint;
    158
    159         for (final LineConvexSubset seg : boundaries) {
    160             if (seg.isInfinite()) {
    161                 // infinite => no centroid
    162                 return null;
    163             }
    164
    165             startPoint = seg.getStartPoint();
    166             endPoint = seg.getEndPoint();
    167
    168             signedArea = startPoint.signedArea(endPoint);
    169
    170             quadrilateralAreaSum += signedArea;
    171
    172             scaledSumX += signedArea * (startPoint.getX() + endPoint.getX());
    173             scaledSumY += signedArea * (startPoint.getY() + endPoint.getY());
    174         }
    175
    176         if (quadrilateralAreaSum > 0) {
    177             return Vector2D.of(scaledSumX, scaledSumY).multiply(1.0 / (3.0 * quadrilateralAreaSum));
    178         }
    179
    180         return null;
    181     }
    182
    183     /** {@inheritDoc} */
    184     @Override
    185     public Split<ConvexArea> split(final Hyperplane<Vector2D> splitter) {
    186         return splitInternal(splitter, this, LineConvexSubset.class, ConvexArea::new);
    187     }
    188
    189     /** Return a BSP tree representing the same region as this instance.
    190      */
    191     @Override
    192     public RegionBSPTree2D toTree() {
    193         return RegionBSPTree2D.from(getBoundaries(), true);
    194     }
    195
    196     /** Return an instance representing the full 2D area.
    197      * @return an instance representing the full 2D area.
    198      */
    199     public static ConvexArea full() {
    200         return FULL;
    201     }
    202
    203     /** Construct a convex polygon from the given vertices.
    204      * @param vertices vertices to use to construct the polygon
    205      * @param precision precision context used for floating point comparisons
    206      * @return a convex polygon constructed using the given vertices
    207      * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
    208      * @throws IllegalArgumentException if the constructed path does not define a closed, convex polygon
    209      * @see LinePath#fromVertexLoop(Collection, DoublePrecisionContext)
    210      */
    211     public static ConvexArea convexPolygonFromVertices(final Collection<Vector2D> vertices,
    212             final DoublePrecisionContext precision) {
    213         return convexPolygonFromPath(LinePath.fromVertexLoop(vertices, precision));
    214     }
    215
    216     /** Construct a convex polygon from a line path.
    217      * @param path path to construct the polygon from
    218      * @return a convex polygon constructed from the given line path
    219      * @throws IllegalArgumentException if the path does not define a closed, convex polygon
    220      */
    221     public static ConvexArea convexPolygonFromPath(final LinePath path) {
    222         // ensure that the path is closed; this also ensures that we do not have any infinite elements
    223         if (!path.isClosed()) {
    224             throw new IllegalArgumentException("Cannot construct convex polygon from unclosed path: " + path);
    225         }
    226
    227         final List<LineConvexSubset> elements = path.getElements();
    228         if (elements.size() < 3) {
    229             throw new IllegalArgumentException(
    230                     "Cannot construct convex polygon from path with less than 3 elements: " + path);
    231         }
    232
    233         // go through the elements and validate that the produced area is convex and finite;
    234         // use the precision context from the first path element
    235         final LineConvexSubset startElement = elements.get(0);
    236         final Vector2D startVertex = startElement.getStartPoint();
    237         final DoublePrecisionContext precision = startElement.getPrecision();
    238
    239         Vector2D curVector;
    240         Vector2D prevVector = null;
    241
    242         double signedArea;
    243         double totalSignedArea = 0.0;
    244
    245         LineConvexSubset element;
    246
    247         // we can skip the last element since the we know that the path is closed, meaning that the
    248         // last element's end point is equal to our start point
    249         for (int i = 0; i < elements.size() - 1; ++i) {
    250             element = elements.get(i);
    251
    252             curVector = startVertex.vectorTo(element.getEndPoint());
    253
    254             if (prevVector != null) {
    255                 signedArea = prevVector.signedArea(curVector);
    256                 if (precision.lt(signedArea, 0.0)) {
    257                     throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
    258                 }
    259
    260                 totalSignedArea += signedArea;
    261             }
    262
    263             prevVector = curVector;
    264         }
    265
    266         if (precision.lte(totalSignedArea, 0.0)) {
    267             throw new IllegalArgumentException(NON_CONVEX_PATH_ERROR + path);
    268         }
    269
    270         return new ConvexArea(elements);
    271     }
    272
    273     /** Create a convex area formed by the intersection of the negative half-spaces of the
    274      * given bounding lines. The returned instance represents the area that is on the
    275      * minus side of all of the given lines. Note that this method does not support areas
    276      * of zero size (ie, infinitely thin areas or points.)
    277      * @param bounds lines used to define the convex area
    278      * @return a new convex area instance representing the area on the minus side of all
    279      *      of the bounding lines or an instance representing the full area if no lines are
    280      *      given
    281      * @throws IllegalArgumentException if the given set of bounding lines do not form a convex area,
    282      *      meaning that there is no region that is on the minus side of all of the bounding lines.
    283      */
    284     public static ConvexArea fromBounds(final Line... bounds) {
    285         return fromBounds(Arrays.asList(bounds));
    286     }
    287
    288     /** Create a convex area formed by the intersection of the negative half-spaces of the
    289      * given bounding lines. The returned instance represents the area that is on the
    290      * minus side of all of the given lines. Note that this method does not support areas
    291      * of zero size (ie, infinitely thin areas or points.)
    292      * @param bounds lines used to define the convex area
    293      * @return a new convex area instance representing the area on the minus side of all
    294      *      of the bounding lines or an instance representing the full area if the collection
    295      *      is empty
    296      * @throws IllegalArgumentException if the given set of bounding lines do not form a convex area,
    297      *      meaning that there is no region that is on the minus side of all of the bounding lines.
    298      */
    299     public static ConvexArea fromBounds(final Iterable<Line> bounds) {
    300         final List<LineConvexSubset> subsets =
    301                 new ConvexRegionBoundaryBuilder<>(LineConvexSubset.class).build(bounds);
    302         return subsets.isEmpty() ? full() : new ConvexArea(subsets);
    303     }
    304 }