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.ArrayList;
    20  import java.util.Collection;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    24  import org.apache.commons.geometry.euclidean.twod.Lines;
    25  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    26
    27  /**
    28   * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
    29   * points in the two-dimensional Euclidean space.
    30   * <p>
    31   * The runtime complexity is O(n log n), with n being the number of input points. If the
    32   * point set is already sorted (by x-coordinate), the runtime complexity is O(n).
    33   * <p>
    34   * The implementation is not sensitive to collinear points on the hull. The parameter
    35   * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points.
    36   * If {@code true}, all points on the boundary of the hull will be added to the hull vertices,
    37   * otherwise only the extreme points will be present. By default, collinear points are not added
    38   * as hull vertices.
    39   * <p>
    40   *
    41   * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
    42   * Andrew's monotone chain algorithm (Wikibooks)</a>
    43   */
    44  public class MonotoneChain extends AbstractConvexHullGenerator2D {
    45
    46      /** Create a new instance that only includes extreme points as hull vertices.
    47       * @param precision precision context used to compare floating point numbers
    48       */
    49      public MonotoneChain(final DoublePrecisionContext precision) {
    50          this(false, precision);
    51      }
    52
    53      /** Create a new instance with the given parameters.
    54       * @param includeCollinearPoints whether collinear points shall be added as hull vertices
    55       * @param precision precision context used to compare floating point numbers
    56       */
    57      public MonotoneChain(final boolean includeCollinearPoints, final DoublePrecisionContext precision) {
    58          super(includeCollinearPoints, precision);
    59      }
    60
    61      /** {@inheritDoc} */
    62      @Override
    63      public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
    64
    65          final List<Vector2D> pointsSortedByXAxis = new ArrayList<>(points);
    66
    67          // sort the points in increasing order on the x-axis
    68          pointsSortedByXAxis.sort((o1, o2) -> {
    69              final DoublePrecisionContext precision = getPrecision();
    70              // need to take the tolerance value into account, otherwise collinear points
    71              // will not be handled correctly when building the upper/lower hull
    72              final int cmp = precision.compare(o1.getX(), o2.getX());
    73              if (cmp == 0) {
    74                  return precision.compare(o1.getY(), o2.getY());
    75              } else {
    76                  return cmp;
    77              }
    78          });
    79
    80          // build lower hull
    81          final List<Vector2D> lowerHull = new ArrayList<>();
    82          for (final Vector2D p : pointsSortedByXAxis) {
    83              updateHull(p, lowerHull);
    84          }
    85
    86          // build upper hull
    87          final List<Vector2D> upperHull = new ArrayList<>();
    88          for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
    89              final Vector2D p = pointsSortedByXAxis.get(idx);
    90              updateHull(p, upperHull);
    91          }
    92
    93          // concatenate the lower and upper hulls
    94          // the last point of each list is omitted as it is repeated at the beginning of the other list
    95          final List<Vector2D> hullVertices = new ArrayList<>(lowerHull.size() + upperHull.size() - 2);
    96          for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
    97              hullVertices.add(lowerHull.get(idx));
    98          }
    99          for (int idx = 0; idx < upperHull.size() - 1; idx++) {
    100             hullVertices.add(upperHull.get(idx));
    101         }
    102
    103         // special case: if the lower and upper hull may contain only 1 point if all are identical
    104         if (hullVertices.isEmpty() && !lowerHull.isEmpty()) {
    105             hullVertices.add(lowerHull.get(0));
    106         }
    107
    108         return hullVertices;
    109     }
    110
    111     /**
    112      * Update the partial hull with the current point.
    113      *
    114      * @param point the current point
    115      * @param hull the partial hull
    116      */
    117     private void updateHull(final Vector2D point, final List<Vector2D> hull) {
    118         final DoublePrecisionContext precision = getPrecision();
    119
    120         if (hull.size() == 1) {
    121             // ensure that we do not add an identical point
    122             final Vector2D p1 = hull.get(0);
    123             if (p1.eq(point, precision)) {
    124                 return;
    125             }
    126         }
    127
    128         while (hull.size() >= 2) {
    129             final int size = hull.size();
    130             final Vector2D p1 = hull.get(size - 2);
    131             final Vector2D p2 = hull.get(size - 1);
    132
    133             final double offset = Lines.fromPoints(p1, p2, precision).offset(point);
    134             if (precision.eqZero(offset)) {
    135                 // the point is collinear to the line (p1, p2)
    136
    137                 final double distanceToCurrent = p1.distance(point);
    138                 if (precision.eqZero(distanceToCurrent) || precision.eqZero(p2.distance(point))) {
    139                     // the point is assumed to be identical to either p1 or p2
    140                     return;
    141                 }
    142
    143                 final double distanceToLast = p1.distance(p2);
    144                 if (isIncludeCollinearPoints()) {
    145                     final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
    146                     hull.add(index, point);
    147                 } else {
    148                     if (distanceToCurrent > distanceToLast) {
    149                         hull.remove(size - 1);
    150                         hull.add(point);
    151                     }
    152                 }
    153                 return;
    154             } else if (offset > 0) {
    155                 hull.remove(size - 1);
    156             } else {
    157                 break;
    158             }
    159         }
    160         hull.add(point);
    161     }
    162 }