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}