MonotoneChain.java

  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.math3.geometry.euclidean.twod.hull;

  19. import java.util.ArrayList;
  20. import java.util.Collection;
  21. import java.util.Collections;
  22. import java.util.Comparator;
  23. import java.util.List;

  25. import org.apache.commons.math3.geometry.euclidean.twod.Line;
  26. import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
  27. import org.apache.commons.math3.util.FastMath;
  28. import org.apache.commons.math3.util.Precision;

  30. /**
  31.  * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
  32.  * points in the two-dimensional euclidean space.
  33.  * <p>
  34.  * The runtime complexity is O(n log n), with n being the number of input points. If the
  35.  * point set is already sorted (by x-coordinate), the runtime complexity is O(n).
  36.  * <p>
  37.  * The implementation is not sensitive to collinear points on the hull. The parameter
  38.  * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points.
  39.  * If {@code true}, all points on the boundary of the hull will be added to the hull vertices,
  40.  * otherwise only the extreme points will be present. By default, collinear points are not added
  41.  * as hull vertices.
  42.  * <p>
  43.  * The {@code tolerance} parameter (default: 1e-10) is used as epsilon criteria to determine
  44.  * identical and collinear points.
  45.  *
  46.  * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
  47.  * Andrew's monotone chain algorithm (Wikibooks)</a>
  48.  * @since 3.3
  49.  */
  50. public class MonotoneChain extends AbstractConvexHullGenerator2D {

  52.     /**
  53.      * Create a new MonotoneChain instance.
  54.      */
  55.     public MonotoneChain() {
  56.         this(false);
  57.     }

  59.     /**
  60.      * Create a new MonotoneChain instance.
  61.      * @param includeCollinearPoints whether collinear points shall be added as hull vertices
  62.      */
  63.     public MonotoneChain(final boolean includeCollinearPoints) {
  64.         super(includeCollinearPoints);
  65.     }

  67.     /**
  68.      * Create a new MonotoneChain instance.
  69.      * @param includeCollinearPoints whether collinear points shall be added as hull vertices
  70.      * @param tolerance tolerance below which points are considered identical
  71.      */
  72.     public MonotoneChain(final boolean includeCollinearPoints, final double tolerance) {
  73.         super(includeCollinearPoints, tolerance);
  74.     }

  76.     @Override
  77.     public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {

  79.         final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points);

  81.         // sort the points in increasing order on the x-axis
  82.         Collections.sort(pointsSortedByXAxis, new Comparator<Vector2D>() {
  83.             public int compare(final Vector2D o1, final Vector2D o2) {
  84.                 final double tolerance = getTolerance();
  85.                 // need to take the tolerance value into account, otherwise collinear points
  86.                 // will not be handled correctly when building the upper/lower hull
  87.                 final int diff = Precision.compareTo(o1.getX(), o2.getX(), tolerance);
  88.                 if (diff == 0) {
  89.                     return Precision.compareTo(o1.getY(), o2.getY(), tolerance);
  90.                 } else {
  91.                     return diff;
  92.                 }
  93.             }
  94.         });

  96.         // build lower hull
  97.         final List<Vector2D> lowerHull = new ArrayList<Vector2D>();
  98.         for (Vector2D p : pointsSortedByXAxis) {
  99.             updateHull(p, lowerHull);
  100.         }

  102.         // build upper hull
  103.         final List<Vector2D> upperHull = new ArrayList<Vector2D>();
  104.         for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
  105.             final Vector2D p = pointsSortedByXAxis.get(idx);
  106.             updateHull(p, upperHull);
  107.         }

  109.         // concatenate the lower and upper hulls
  110.         // the last point of each list is omitted as it is repeated at the beginning of the other list
  111.         final List<Vector2D> hullVertices = new ArrayList<Vector2D>(lowerHull.size() + upperHull.size() - 2);
  112.         for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
  113.             hullVertices.add(lowerHull.get(idx));
  114.         }
  115.         for (int idx = 0; idx < upperHull.size() - 1; idx++) {
  116.             hullVertices.add(upperHull.get(idx));
  117.         }

  119.         // special case: if the lower and upper hull may contain only 1 point if all are identical
  120.         if (hullVertices.isEmpty() && ! lowerHull.isEmpty()) {
  121.             hullVertices.add(lowerHull.get(0));
  122.         }

  124.         return hullVertices;
  125.     }

  127.     /**
  128.      * Update the partial hull with the current point.
  129.      *
  130.      * @param point the current point
  131.      * @param hull the partial hull
  132.      */
  133.     private void updateHull(final Vector2D point, final List<Vector2D> hull) {
  134.         final double tolerance = getTolerance();

  136.         if (hull.size() == 1) {
  137.             // ensure that we do not add an identical point
  138.             final Vector2D p1 = hull.get(0);
  139.             if (p1.distance(point) < tolerance) {
  140.                 return;
  141.             }
  142.         }

  144.         while (hull.size() >= 2) {
  145.             final int size = hull.size();
  146.             final Vector2D p1 = hull.get(size - 2);
  147.             final Vector2D p2 = hull.get(size - 1);

  149.             final double offset = new Line(p1, p2, tolerance).getOffset(point);
  150.             if (FastMath.abs(offset) < tolerance) {
  151.                 // the point is collinear to the line (p1, p2)

  153.                 final double distanceToCurrent = p1.distance(point);
  154.                 if (distanceToCurrent < tolerance || p2.distance(point) < tolerance) {
  155.                     // the point is assumed to be identical to either p1 or p2
  156.                     return;
  157.                 }

  159.                 final double distanceToLast = p1.distance(p2);
  160.                 if (isIncludeCollinearPoints()) {
  161.                     final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
  162.                     hull.add(index, point);
  163.                 } else {
  164.                     if (distanceToCurrent > distanceToLast) {
  165.                         hull.remove(size - 1);
  166.                         hull.add(point);
  167.                     }
  168.                 }
  169.                 return;
  170.             } else if (offset > 0) {
  171.                 hull.remove(size - 1);
  172.             } else {
  173.                 break;
  174.             }
  175.         }
  176.         hull.add(point);
  177.     }

  179. }
Created with JaCoCo 0.7.2.201409121644