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.euclidean.twod.Vector2D;
    24
    25  /**
    26   * A simple heuristic to improve the performance of convex hull algorithms.
    27   * <p>
    28   * The heuristic is based on the idea of a convex quadrilateral, which is formed by
    29   * four points with the lowest and highest x / y coordinates. Any point that lies inside
    30   * this quadrilateral can not be part of the convex hull and can thus be safely discarded
    31   * before generating the convex hull itself.
    32   * <p>
    33   * The complexity of the operation is O(n), and may greatly improve the time it takes to
    34   * construct the convex hull afterwards, depending on the point distribution.
    35   *
    36   * @see <a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms#Akl-Toussaint_heuristic">
    37   * Akl-Toussaint heuristic (Wikipedia)</a>
    38   */
    39  public final class AklToussaintHeuristic {
    40
    41      /** Hide utility constructor. */
    42      private AklToussaintHeuristic() {
    43      }
    44
    45      /**
    46       * Returns a point set that is reduced by all points for which it is safe to assume
    47       * that they are not part of the convex hull.
    48       *
    49       * @param points the original point set
    50       * @return a reduced point set, useful as input for convex hull algorithms
    51       */
    52      public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
    53
    54          // find the leftmost point
    55          int size = 0;
    56          Vector2D minX = null;
    57          Vector2D maxX = null;
    58          Vector2D minY = null;
    59          Vector2D maxY = null;
    60          for (final Vector2D p : points) {
    61              if (minX == null || p.getX() < minX.getX()) {
    62                  minX = p;
    63              }
    64              if (maxX == null || p.getX() > maxX.getX()) {
    65                  maxX = p;
    66              }
    67              if (minY == null || p.getY() < minY.getY()) {
    68                  minY = p;
    69              }
    70              if (maxY == null || p.getY() > maxY.getY()) {
    71                  maxY = p;
    72              }
    73              size++;
    74          }
    75
    76          if (size < 4) {
    77              return points;
    78          }
    79
    80          final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX);
    81          // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce
    82          if (quadrilateral.size() < 3) {
    83              return points;
    84          }
    85
    86          final List<Vector2D> reducedPoints = new ArrayList<>(quadrilateral);
    87          for (final Vector2D p : points) {
    88              // check all points if they are within the quadrilateral
    89              // in which case they can not be part of the convex hull
    90              if (!insideQuadrilateral(p, quadrilateral)) {
    91                  reducedPoints.add(p);
    92              }
    93          }
    94
    95          return reducedPoints;
    96      }
    97
    98      /**
    99       * Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
    100      *
    101      * @param points the respective points with min/max x/y coordinate
    102      * @return the quadrilateral
    103      */
    104     private static List<Vector2D> buildQuadrilateral(final Vector2D... points) {
    105         final List<Vector2D> quadrilateral = new ArrayList<>();
    106         for (final Vector2D p : points) {
    107             if (!quadrilateral.contains(p)) {
    108                 quadrilateral.add(p);
    109             }
    110         }
    111         return quadrilateral;
    112     }
    113
    114     /**
    115      * Checks if the given point is located within the convex quadrilateral.
    116      * @param point the point to check
    117      * @param quadrilateralPoints the convex quadrilateral, represented by 4 points
    118      * @return {@code true} if the point is inside the quadrilateral, {@code false} otherwise
    119      */
    120     private static boolean insideQuadrilateral(final Vector2D point,
    121                                                final List<Vector2D> quadrilateralPoints) {
    122
    123         Vector2D v1 = quadrilateralPoints.get(0);
    124         Vector2D v2 = quadrilateralPoints.get(1);
    125
    126         if (point.equals(v1) || point.equals(v2)) {
    127             return true;
    128         }
    129
    130         // get the location of the point relative to the first two vertices
    131         final double last = signedAreaPoints(v1, v2, point);
    132         final int size = quadrilateralPoints.size();
    133         // loop through the rest of the vertices
    134         for (int i = 1; i < size; i++) {
    135             v1 = v2;
    136             v2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1);
    137
    138             if (point.equals(v1) || point.equals(v2)) {
    139                 return true;
    140             }
    141
    142             // do side of line test: multiply the last location with this location
    143             // if they are the same sign then the operation will yield a positive result
    144             // -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy
    145             if (last * signedAreaPoints(v1, v2, point) < 0) {
    146                 return false;
    147             }
    148         }
    149         return true;
    150     }
    151
    152     /** Compute the signed area of the parallelogram formed by vectors between the given points. The first
    153      * vector points from {@code p0} to {@code p1} and the second from {@code p0} to {@code p3}.
    154      * @param p0 first point
    155      * @param p1 second point
    156      * @param p2 third point
    157      * @return signed area of parallelogram formed by vectors between the given points
    158      */
    159     private static double signedAreaPoints(final Vector2D p0, final Vector2D p1, final Vector2D p2) {
    160         return p0.vectorTo(p1).signedArea(p0.vectorTo(p2));
    161     }
    162
    163 }