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