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.hull.euclidean.twod;
    18
    19  import java.util.Collection;
    20  import java.util.Iterator;
    21
    22  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    23  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    24
    25  /**
    26   * Abstract base class for convex hull generators in the two-dimensional Euclidean space.
    27   */
    28  abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
    29
    30      /** Precision context used to compare floating point numbers. */
    31      private final DoublePrecisionContext precision;
    32
    33      /**
    34       * Indicates if collinear points on the hull shall be present in the output.
    35       * If {@code false}, only the extreme points are added to the hull.
    36       */
    37      private final boolean includeCollinearPoints;
    38
    39      /**
    40       * Simple constructor.
    41       *
    42       * @param includeCollinearPoints indicates if collinear points on the hull shall be
    43       * added as hull vertices
    44       * @param precision precision context used to compare floating point numbers
    45       */
    46      protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints,
    47              final DoublePrecisionContext precision) {
    48          this.includeCollinearPoints = includeCollinearPoints;
    49          this.precision = precision;
    50      }
    51
    52      /** Get the object used to determine floating point equality for this region.
    53       * @return the floating point precision context for the instance
    54       */
    55      public DoublePrecisionContext getPrecision() {
    56          return precision;
    57      }
    58
    59      /**
    60       * Returns if collinear points on the hull will be added as hull vertices.
    61       * @return {@code true} if collinear points are added as hull vertices, or {@code false}
    62       * if only extreme points are present.
    63       */
    64      public boolean isIncludeCollinearPoints() {
    65          return includeCollinearPoints;
    66      }
    67
    68      /** {@inheritDoc} */
    69      @Override
    70      public ConvexHull2D generate(final Collection<Vector2D> points) {
    71          Collection<Vector2D> hullVertices = null;
    72          if (points.size() < 2) {
    73              hullVertices = points;
    74          } else {
    75              hullVertices = findHullVertices(points);
    76          }
    77
    78          if (!isConvex(hullVertices)) {
    79              throw new IllegalStateException("Convex hull algorithm failed to generate solution");
    80          }
    81
    82          return new ConvexHull2D(hullVertices, precision);
    83      }
    84
    85      /**
    86       * Find the convex hull vertices from the set of input points.
    87       * @param points the set of input points
    88       * @return the convex hull vertices in CCW winding
    89       */
    90      protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
    91
    92      /** Return true if the given vertices define a convex hull.
    93       * @param vertices the hull vertices
    94       * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
    95       */
    96      private boolean isConvex(final Collection<Vector2D> vertices) {
    97          final int size = vertices.size();
    98
    99          if (size < 3) {
    100             // 1 or 2 points always define a convex set
    101             return true;
    102         }
    103
    104         final Iterator<Vector2D> it = vertices.iterator();
    105
    106         Vector2D p1 = it.next();
    107         Vector2D p2 = it.next();
    108         Vector2D p3;
    109
    110         Vector2D v1;
    111         Vector2D v2;
    112
    113         while (it.hasNext()) {
    114             p3 = it.next();
    115
    116             v1 = p1.vectorTo(p2);
    117             v2 = p2.vectorTo(p3);
    118
    119             // negative signed areas mean a clockwise winding
    120             if (precision.compare(v1.signedArea(v2), 0.0) < 0) {
    121                 return false;
    122             }
    123
    124             p1 = p2;
    125             p2 = p3;
    126         }
    127
    128         return true;
    129     }
    130 }