001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.euclidean.twod.hull;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.List;
022
023import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
024
025/**
026 * A simple heuristic to improve the performance of convex hull algorithms.
027 * <p>
028 * The heuristic is based on the idea of a convex quadrilateral, which is formed by
029 * four points with the lowest and highest x / y coordinates. Any point that lies inside
030 * this quadrilateral can not be part of the convex hull and can thus be safely discarded
031 * before generating the convex hull itself.
032 * <p>
033 * The complexity of the operation is O(n), and may greatly improve the time it takes to
034 * construct the convex hull afterwards, depending on the point distribution.
035 *
036 * @see <a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms#Akl-Toussaint_heuristic">
037 * Akl-Toussaint heuristic (Wikipedia)</a>
038 * @since 3.3
039 */
040public final class AklToussaintHeuristic {
041
042    /** Hide utility constructor. */
043    private AklToussaintHeuristic() {
044    }
045
046    /**
047     * Returns a point set that is reduced by all points for which it is safe to assume
048     * that they are not part of the convex hull.
049     *
050     * @param points the original point set
051     * @return a reduced point set, useful as input for convex hull algorithms
052     */
053    public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
054
055        // find the leftmost point
056        int size = 0;
057        Vector2D minX = null;
058        Vector2D maxX = null;
059        Vector2D minY = null;
060        Vector2D maxY = null;
061        for (Vector2D p : points) {
062            if (minX == null || p.getX() < minX.getX()) {
063                minX = p;
064            }
065            if (maxX == null || p.getX() > maxX.getX()) {
066                maxX = p;
067            }
068            if (minY == null || p.getY() < minY.getY()) {
069                minY = p;
070            }
071            if (maxY == null || p.getY() > maxY.getY()) {
072                maxY = p;
073            }
074            size++;
075        }
076
077        if (size < 4) {
078            return points;
079        }
080
081        final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX);
082        // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce
083        if (quadrilateral.size() < 3) {
084            return points;
085        }
086
087        final List<Vector2D> reducedPoints = new ArrayList<Vector2D>(quadrilateral);
088        for (final Vector2D p : points) {
089            // check all points if they are within the quadrilateral
090            // in which case they can not be part of the convex hull
091            if (!insideQuadrilateral(p, quadrilateral)) {
092                reducedPoints.add(p);
093            }
094        }
095
096        return reducedPoints;
097    }
098
099    /**
100     * Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
101     *
102     * @param points the respective points with min/max x/y coordinate
103     * @return the quadrilateral
104     */
105    private static List<Vector2D> buildQuadrilateral(final Vector2D... points) {
106        List<Vector2D> quadrilateral = new ArrayList<Vector2D>();
107        for (Vector2D p : points) {
108            if (!quadrilateral.contains(p)) {
109                quadrilateral.add(p);
110            }
111        }
112        return quadrilateral;
113    }
114
115    /**
116     * Checks if the given point is located within the convex quadrilateral.
117     * @param point the point to check
118     * @param quadrilateralPoints the convex quadrilateral, represented by 4 points
119     * @return {@code true} if the point is inside the quadrilateral, {@code false} otherwise
120     */
121    private static boolean insideQuadrilateral(final Vector2D point,
122                                               final List<Vector2D> quadrilateralPoints) {
123
124        Vector2D p1 = quadrilateralPoints.get(0);
125        Vector2D p2 = quadrilateralPoints.get(1);
126
127        if (point.equals(p1) || point.equals(p2)) {
128            return true;
129        }
130
131        // get the location of the point relative to the first two vertices
132        final double last = point.crossProduct(p1, p2);
133        final int size = quadrilateralPoints.size();
134        // loop through the rest of the vertices
135        for (int i = 1; i < size; i++) {
136            p1 = p2;
137            p2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1);
138
139            if (point.equals(p1) || point.equals(p2)) {
140                return true;
141            }
142
143            // do side of line test: multiply the last location with this location
144            // if they are the same sign then the operation will yield a positive result
145            // -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy
146            if (last * point.crossProduct(p1, p2) < 0) {
147                return false;
148            }
149        }
150        return true;
151    }
152
153}