You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2020/01/10 13:11:52 UTC
[commons-geometry] 01/04: GEOMETRY-84: updating convex hull API:
making methods return lists instead of arrays,
removing default epsilon value,
other updates for consistency with rest of library
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 7f7b195938ed670abe036a2873393f20390b07d7
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Thu Jan 9 21:38:11 2020 -0500
GEOMETRY-84: updating convex hull API: making methods return lists instead of arrays, removing default epsilon value, other updates for consistency with rest of library
---
commons-geometry-euclidean/pom.xml | 12 ++
commons-geometry-hull/pom.xml | 8 +
.../apache/commons/geometry/hull/ConvexHull.java | 22 +--
.../commons/geometry/hull/ConvexHullGenerator.java | 4 +-
.../twod/AbstractConvexHullGenerator2D.java | 65 +++++---
.../geometry/hull/euclidean/twod/ConvexHull2D.java | 165 +++++++------------
.../hull/euclidean/twod/MonotoneChain.java | 30 ++--
.../geometry/hull/DocumentationExamplesTest.java | 74 +++++++++
.../euclidean/twod/AklToussaintHeuristicTest.java | 2 +-
.../hull/euclidean/twod/ConvexHull2DTest.java | 179 +++++++++++++++++++++
.../twod/ConvexHullGenerator2DAbstractTest.java | 139 ++++++++++++----
.../hull/euclidean/twod/MonotoneChainTest.java | 8 +-
src/site/site.xml | 1 +
src/site/xdoc/userguide/index.xml | 74 +++++++++
14 files changed, 579 insertions(+), 204 deletions(-)
diff --git a/commons-geometry-euclidean/pom.xml b/commons-geometry-euclidean/pom.xml
index 5544db0..239c4ab 100644
--- a/commons-geometry-euclidean/pom.xml
+++ b/commons-geometry-euclidean/pom.xml
@@ -95,6 +95,18 @@
<build>
<plugins>
+ <!-- Make the core test utilities accessible to other projects. -->
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-jar-plugin</artifactId>
+ <executions>
+ <execution>
+ <goals>
+ <goal>test-jar</goal>
+ </goals>
+ </execution>
+ </executions>
+ </plugin>
<plugin>
<groupId>org.apache.rat</groupId>
<artifactId>apache-rat-plugin</artifactId>
diff --git a/commons-geometry-hull/pom.xml b/commons-geometry-hull/pom.xml
index ab94116..c6d4283 100644
--- a/commons-geometry-hull/pom.xml
+++ b/commons-geometry-hull/pom.xml
@@ -63,6 +63,14 @@
<type>test-jar</type>
<scope>test</scope>
</dependency>
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-geometry-euclidean</artifactId>
+ <version>${project.version}</version>
+ <classifier>tests</classifier>
+ <type>test-jar</type>
+ <scope>test</scope>
+ </dependency>
<dependency>
<groupId>org.apache.commons</groupId>
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java
index 1e0399e..09a7477 100644
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java
+++ b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHull.java
@@ -16,27 +16,29 @@
*/
package org.apache.commons.geometry.hull;
+import java.util.List;
+
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.Region;
/**
* This class represents a convex hull.
*
- * @param <P> Point type.
+ * @param <P> Point implementation type.
*/
public interface ConvexHull<P extends Point<P>> {
- /**
- * Get the vertices of the convex hull.
+ /** Get the vertices of the convex hull.
* @return vertices of the convex hull
*/
- P[] getVertices();
+ List<P> getVertices();
- /**
- * Returns a new region that is enclosed by the convex hull.
- * @return the region enclosed by the convex hull
- * @throws IllegalStateException if the number of vertices is not enough to
- * build a region in the respective space
+ /** Return the region representing the convex hull. This will return
+ * null in cases where the hull does not define a region with non-zero
+ * size, such as when only a single unique point exists or when all points
+ * are collinear.
+ * @return the region representing by the convex hull or null if the
+ * convex hull does not define a region of non-zero size
*/
- Region<P> createRegion();
+ Region<P> getRegion();
}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java
index fdf40a7..3db030b 100644
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java
+++ b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/ConvexHullGenerator.java
@@ -30,12 +30,12 @@ import org.apache.commons.geometry.core.Point;
*/
public interface ConvexHullGenerator<P extends Point<P>> {
/**
- * Builds the convex hull from the set of input points.
+ * Build a convex hull from the set of input points.
*
* @param points the set of input points
* @return the convex hull
* @throws IllegalStateException if generator fails to generate a convex hull for
- * the given set of input points
+ * the given set of input points
*/
ConvexHull<P> generate(Collection<P> points);
}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java
index 948e5fa..7770fdb 100644
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java
+++ b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AbstractConvexHullGenerator2D.java
@@ -17,9 +17,9 @@
package org.apache.commons.geometry.hull.euclidean.twod;
import java.util.Collection;
+import java.util.Iterator;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
-import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
/**
@@ -27,9 +27,6 @@ import org.apache.commons.geometry.euclidean.twod.Vector2D;
*/
abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
- /** Default epsilon value. */
- private static final double DEFAULT_EPSILON = 1e-10;
-
/** Precision context used to compare floating point numbers. */
private final DoublePrecisionContext precision;
@@ -41,18 +38,6 @@ abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
/**
* Simple constructor.
- * <p>
- * The default epsilon (1e-10) will be used to determine identical points.
- *
- * @param includeCollinearPoints indicates if collinear points on the hull shall be
- * added as hull vertices
- */
- protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints) {
- this(includeCollinearPoints, new EpsilonDoublePrecisionContext(DEFAULT_EPSILON));
- }
-
- /**
- * Simple constructor.
*
* @param includeCollinearPoints indicates if collinear points on the hull shall be
* added as hull vertices
@@ -90,13 +75,11 @@ abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
hullVertices = findHullVertices(points);
}
- try {
- return new ConvexHull2D(hullVertices.toArray(new Vector2D[hullVertices.size()]),
- precision);
- } catch (IllegalArgumentException e) {
- // the hull vertices may not form a convex hull if the tolerance value is to large
- throw new IllegalStateException("Convex hull algorithm failed to generate solution", e);
+ if (!isConvex(hullVertices)) {
+ throw new IllegalStateException("Convex hull algorithm failed to generate solution");
}
+
+ return new ConvexHull2D(hullVertices, precision);
}
/**
@@ -106,4 +89,42 @@ abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
*/
protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
+ /** Return true if the given vertices define a convex hull.
+ * @param vertices the hull vertices
+ * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
+ */
+ private boolean isConvex(final Collection<Vector2D> vertices) {
+ int size = vertices.size();
+
+ if (size < 3) {
+ // 1 or 2 points always define a convex set
+ return true;
+ }
+
+ Iterator<Vector2D> it = vertices.iterator();
+
+ Vector2D p1 = it.next();
+ Vector2D p2 = it.next();
+ Vector2D p3;
+
+ Vector2D v1;
+ Vector2D v2;
+
+ while (it.hasNext()) {
+ p3 = it.next();
+
+ v1 = p1.vectorTo(p2);
+ v2 = p2.vectorTo(p3);
+
+ // negative signed areas mean a clockwise winding
+ if (precision.compare(v1.signedArea(v2), 0.0) < 0) {
+ return false;
+ }
+
+ p1 = p2;
+ p2 = p3;
+ }
+
+ return true;
+ }
}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java
index cfcc054..cf669ca 100644
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java
+++ b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.java
@@ -16,144 +16,91 @@
*/
package org.apache.commons.geometry.hull.euclidean.twod;
-import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
import java.util.List;
-import java.util.stream.Collectors;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.euclidean.twod.ConvexArea;
-import org.apache.commons.geometry.euclidean.twod.Line;
-import org.apache.commons.geometry.euclidean.twod.Segment;
+import org.apache.commons.geometry.euclidean.twod.Polyline;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.geometry.hull.ConvexHull;
-import org.apache.commons.numbers.arrays.LinearCombination;
/**
- * This class represents a convex hull in an two-dimensional Euclidean space.
+ * This class represents a convex hull in two-dimensional Euclidean space.
*/
-public class ConvexHull2D implements ConvexHull<Vector2D> {
- /** Vertices of the hull. */
- private final Vector2D[] vertices;
+public final class ConvexHull2D implements ConvexHull<Vector2D> {
- /** Precision context used to compare floating point numbers. */
- private final DoublePrecisionContext precision;
+ /** Vertices for the convex hull, in order. */
+ private final List<Vector2D> vertices;
- /**
- * Line segments of the hull.
- * The array is not serialized and will be created from the vertices on first access.
- */
- private Segment[] lineSegments;
+ /** Polyline path for the convex hull. */
+ private final Polyline path;
- /**
- * Simple constructor.
- * @param vertices the vertices of the convex hull, must be ordered
+ /** Simple constructor; no validation is performed.
+ * @param vertices the vertices of the convex hull; callers are responsible for ensuring that
+ * the given vertices are in order, unique, and define a convex hull.
* @param precision precision context used to compare floating point numbers
- * @throws IllegalArgumentException if the vertices do not form a convex hull
- */
- public ConvexHull2D(final Vector2D[] vertices, final DoublePrecisionContext precision) {
- this.precision = precision;
-
- if (!isConvex(vertices)) {
- throw new IllegalArgumentException("Vertices do not form a convex hull in CCW winding");
- }
-
- this.vertices = vertices.clone();
- }
-
- /**
- * Checks whether the given hull vertices form a convex hull.
- * @param hullVertices the hull vertices
- * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
*/
- private boolean isConvex(final Vector2D[] hullVertices) {
- if (hullVertices.length < 3) {
- return true;
- }
-
- int sign = 0;
- for (int i = 0; i < hullVertices.length; i++) {
- final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1];
- final Vector2D p2 = hullVertices[i];
- final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1];
-
- final Vector2D d1 = p2.subtract(p1);
- final Vector2D d2 = p3.subtract(p2);
-
- final double crossProduct = LinearCombination.value(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
- final int cmp = precision.compare(crossProduct, 0.0);
- // in case of collinear points the cross product will be zero
- if (cmp != 0.0) {
- if (sign != 0.0 && cmp != sign) {
- return false;
- }
- sign = cmp;
- }
- }
-
- return true;
+ ConvexHull2D(final Collection<Vector2D> vertices, final DoublePrecisionContext precision) {
+ this.vertices = Collections.unmodifiableList(new ArrayList<>(vertices));
+ this.path = buildHullPath(vertices, precision);
}
/** {@inheritDoc} */
@Override
- public Vector2D[] getVertices() {
- return vertices.clone();
+ public List<Vector2D> getVertices() {
+ return vertices;
}
- /**
- * Get the line segments of the convex hull, ordered.
- * @return the line segments of the convex hull
+ /** Get a path defining the convex hull. The path will contain
+ * <ul>
+ * <li>zero segments if the hull consists of only a single point,</li>
+ * <li>one segment if the hull consists of two points,</li>
+ * <li>three or more segments defining a closed loop if the hull consists of more than
+ * two non-collinear points.</li>
+ * </ul>
+ * @return polyline path defining the convex hull
*/
- public Segment[] getLineSegments() {
- return retrieveLineSegments().clone();
+ public Polyline getPath() {
+ return path;
}
- /**
- * Retrieve the line segments from the cached array or create them if needed.
- *
- * @return the array of line segments
- */
- private Segment[] retrieveLineSegments() {
- if (lineSegments == null) {
- // construct the line segments - handle special cases of 1 or 2 points
- final int size = vertices.length;
- if (size <= 1) {
- this.lineSegments = new Segment[0];
- } else if (size == 2) {
- this.lineSegments = new Segment[1];
- final Vector2D p1 = vertices[0];
- final Vector2D p2 = vertices[1];
- this.lineSegments[0] = Segment.fromPoints(p1, p2, precision);
- } else {
- this.lineSegments = new Segment[size];
- Vector2D firstPoint = null;
- Vector2D lastPoint = null;
- int index = 0;
- for (Vector2D point : vertices) {
- if (lastPoint == null) {
- firstPoint = point;
- lastPoint = point;
- } else {
- this.lineSegments[index++] = Segment.fromPoints(lastPoint, point, precision);
- lastPoint = point;
- }
- }
- this.lineSegments[index] = Segment.fromPoints(lastPoint, firstPoint, precision);
- }
- }
- return lineSegments;
+ /** {@inheritDoc} */
+ @Override
+ public ConvexArea getRegion() {
+ return path.isClosed() ?
+ ConvexArea.fromPath(path) :
+ null;
}
/** {@inheritDoc} */
@Override
- public ConvexArea createRegion() {
- if (vertices.length < 3) {
- throw new IllegalStateException("Region generation requires at least 3 vertices but found only " +
- vertices.length);
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName())
+ .append("[vertices= ")
+ .append(getVertices())
+ .append(']');
+
+ return sb.toString();
+ }
+
+ /** Build a polyline representing the path for a convex hull.
+ * @param vertices convex hull vertices
+ * @param precision precision context used to compare floating point values
+ * @return path for the convex hull defined by the given vertices
+ */
+ private static Polyline buildHullPath(final Collection<Vector2D> vertices, final DoublePrecisionContext precision) {
+ if (vertices.size() < 2) {
+ return Polyline.empty();
}
- List<Line> bounds = Arrays.asList(retrieveLineSegments()).stream()
- .map(Segment::getLine).collect(Collectors.toList());
+ final boolean closeLoop = vertices.size() > 2;
- return ConvexArea.fromBounds(bounds);
+ return Polyline.builder(precision)
+ .appendVertices(vertices)
+ .build(closeLoop);
}
}
diff --git a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java
index defac7e..844bb31 100644
--- a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java
+++ b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java
@@ -38,31 +38,20 @@ import org.apache.commons.geometry.euclidean.twod.Vector2D;
* otherwise only the extreme points will be present. By default, collinear points are not added
* as hull vertices.
* <p>
- * The {@code tolerance} parameter (default: 1e-10) is used as epsilon criteria to determine
- * identical and collinear points.
*
* @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
* Andrew's monotone chain algorithm (Wikibooks)</a>
*/
public class MonotoneChain extends AbstractConvexHullGenerator2D {
- /**
- * Create a new MonotoneChain instance.
- */
- public MonotoneChain() {
- this(false);
- }
-
- /**
- * Create a new MonotoneChain instance.
- * @param includeCollinearPoints whether collinear points shall be added as hull vertices
+ /** Create a new instance that only includes extreme points as hull vertices.
+ * @param precision precision context used to compare floating point numbers
*/
- public MonotoneChain(final boolean includeCollinearPoints) {
- super(includeCollinearPoints);
+ public MonotoneChain(final DoublePrecisionContext precision) {
+ this(false, precision);
}
- /**
- * Create a new MonotoneChain instance.
+ /** Create a new instance with the given parameters.
* @param includeCollinearPoints whether collinear points shall be added as hull vertices
* @param precision precision context used to compare floating point numbers
*/
@@ -81,11 +70,11 @@ public class MonotoneChain extends AbstractConvexHullGenerator2D {
final DoublePrecisionContext precision = getPrecision();
// need to take the tolerance value into account, otherwise collinear points
// will not be handled correctly when building the upper/lower hull
- final int diff = precision.compare(o1.getX(), o2.getX());
- if (diff == 0) {
+ final int cmp = precision.compare(o1.getX(), o2.getX());
+ if (cmp == 0) {
return precision.compare(o1.getY(), o2.getY());
} else {
- return diff;
+ return cmp;
}
});
@@ -132,7 +121,7 @@ public class MonotoneChain extends AbstractConvexHullGenerator2D {
if (hull.size() == 1) {
// ensure that we do not add an identical point
final Vector2D p1 = hull.get(0);
- if (precision.eqZero(p1.distance(point))) {
+ if (p1.eq(point, precision)) {
return;
}
}
@@ -171,5 +160,4 @@ public class MonotoneChain extends AbstractConvexHullGenerator2D {
}
hull.add(point);
}
-
}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java
new file mode 100644
index 0000000..5df2d86
--- /dev/null
+++ b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/DocumentationExamplesTest.java
@@ -0,0 +1,74 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.hull;
+
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
+import org.apache.commons.geometry.euclidean.twod.ConvexArea;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.geometry.hull.euclidean.twod.ConvexHull2D;
+import org.apache.commons.geometry.hull.euclidean.twod.MonotoneChain;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class DocumentationExamplesTest {
+
+ private static final double TEST_EPS = 1e-15;
+
+ @Test
+ public void testMonotoneChainExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-10);
+
+ // create a list of input points for the algorithm
+ List<Vector2D> pts = Arrays.asList(
+ Vector2D.ZERO,
+ Vector2D.of(0.5, 0.5),
+ Vector2D.of(0, 0.5),
+ Vector2D.of(0, 1),
+ Vector2D.of(0.25, 0.1),
+ Vector2D.of(1, 0),
+ Vector2D.of(1, 1),
+ Vector2D.of(0.75, 0.9)
+ );
+
+ // create an instance of the monotone chain convex hull generator
+ MonotoneChain mc = new MonotoneChain(precision);
+
+ // compute the convex hull
+ ConvexHull2D hull = mc.generate(pts);
+
+ // list the vertices from the input that were used in the hull
+ List<Vector2D> vertices = hull.getVertices(); // [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
+
+ // get the hull as a region
+ ConvexArea region = hull.getRegion();
+ boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points
+
+ // ---
+ Assert.assertEquals(4, vertices.size());
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(2), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(3), TEST_EPS);
+
+ Assert.assertTrue(containsAll);
+ }
+}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java
index 2fe06e6..ee72064 100644
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java
+++ b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristicTest.java
@@ -27,7 +27,7 @@ public class AklToussaintHeuristicTest extends ConvexHullGenerator2DAbstractTest
@Override
protected ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints) {
- return new MonotoneChain(includeCollinearPoints);
+ return new MonotoneChain(includeCollinearPoints, TEST_PRECISION);
}
@Override
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java
new file mode 100644
index 0000000..b7bbcc4
--- /dev/null
+++ b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2DTest.java
@@ -0,0 +1,179 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.hull.euclidean.twod;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
+import org.apache.commons.geometry.euclidean.twod.Polyline;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ConvexHull2DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ @Test
+ public void testProperties_noPoints() {
+ // act
+ ConvexHull2D hull = new ConvexHull2D(Collections.emptyList(), TEST_PRECISION);
+
+ // assert
+ Assert.assertEquals(0, hull.getVertices().size());
+
+ Polyline path = hull.getPath();
+ Assert.assertEquals(0, path.getSegments().size());
+
+ List<Vector2D> pathVertices = path.getVertices();
+ Assert.assertEquals(0, pathVertices.size());
+
+ Assert.assertNull(hull.getRegion());
+ }
+
+ @Test
+ public void testProperties_singlePoint() {
+ // arrange
+ List<Vector2D> vertices = Arrays.asList(Vector2D.Unit.PLUS_X);
+
+ // act
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assert.assertEquals(vertices, hull.getVertices());
+
+ Polyline path = hull.getPath();
+ Assert.assertEquals(0, path.getSegments().size());
+
+ List<Vector2D> pathVertices = path.getVertices();
+ Assert.assertEquals(0, pathVertices.size());
+
+ Assert.assertNull(hull.getRegion());
+ }
+
+ @Test
+ public void testProperties_twoPoints() {
+ // arrange
+ List<Vector2D> vertices = Arrays.asList(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
+
+ // act
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assert.assertEquals(vertices, hull.getVertices());
+
+ Polyline path = hull.getPath();
+ Assert.assertEquals(1, path.getSegments().size());
+
+ List<Vector2D> pathVertices = path.getVertices();
+ Assert.assertEquals(2, pathVertices.size());
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(0), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(1), TEST_EPS);
+
+ Assert.assertNull(hull.getRegion());
+ }
+
+ @Test
+ public void testProperties_threePoints() {
+ // arrange
+ List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
+
+ // act
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assert.assertEquals(vertices, hull.getVertices());
+
+ Polyline path = hull.getPath();
+ Assert.assertEquals(3, path.getSegments().size());
+
+ List<Vector2D> pathVertices = path.getVertices();
+ Assert.assertEquals(4, pathVertices.size());
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(0), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(1), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(2), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(3), TEST_EPS);
+
+ Assert.assertEquals(0.5, hull.getRegion().getSize(), TEST_EPS);
+ }
+
+ @Test
+ public void testProperties_fourPoints() {
+ // arrange
+ List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X,
+ Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y);
+
+ // act
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assert.assertEquals(vertices, hull.getVertices());
+
+ Polyline path = hull.getPath();
+ Assert.assertEquals(4, path.getSegments().size());
+
+ List<Vector2D> pathVertices = path.getVertices();
+ Assert.assertEquals(5, pathVertices.size());
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(0), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, pathVertices.get(1), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), pathVertices.get(2), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, pathVertices.get(3), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, pathVertices.get(4), TEST_EPS);
+
+ Assert.assertEquals(1.0, hull.getRegion().getSize(), TEST_EPS);
+ }
+
+ @Test
+ public void testVertexListCannotBeModified() {
+ // arrange
+ List<Vector2D> vertices = new ArrayList<>();
+ vertices.add(Vector2D.Unit.PLUS_X);
+
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // act
+ List<Vector2D> hullVertices = hull.getVertices();
+
+ // assert
+ Assert.assertNotSame(vertices, hullVertices);
+ GeometryTestUtils.assertThrows(() -> {
+ hullVertices.add(Vector2D.Unit.PLUS_Y);
+ }, UnsupportedOperationException.class);
+ }
+
+ @Test
+ public void testToString() {
+ // arrange
+ List<Vector2D> vertices = Arrays.asList(Vector2D.Unit.PLUS_X);
+ ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // act
+ String str = hull.toString();
+
+ // assert
+ GeometryTestUtils.assertContains("ConvexHull2D[vertices= [(1", str);
+ }
+}
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java
index d1f9dcb..1bce416 100644
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java
+++ b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2DAbstractTest.java
@@ -17,13 +17,15 @@
package org.apache.commons.geometry.hull.euclidean.twod;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import org.apache.commons.geometry.core.Region;
import org.apache.commons.geometry.core.RegionLocation;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.apache.commons.geometry.euclidean.twod.ConvexArea;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.numbers.arrays.LinearCombination;
import org.apache.commons.numbers.core.Precision;
@@ -35,11 +37,16 @@ import org.junit.Test;
/**
* Abstract base test class for 2D convex hull generators.
- *
*/
public abstract class ConvexHullGenerator2DAbstractTest {
+ protected static final double TEST_EPS = 1e-10;
+
+ protected static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
protected ConvexHullGenerator2D generator;
+
protected UniformRandomProvider random;
protected abstract ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints);
@@ -60,37 +67,59 @@ public abstract class ConvexHullGenerator2DAbstractTest {
@Test
public void testEmpty() {
- ConvexHull2D hull = generator.generate(Collections.<Vector2D>emptyList());
- Assert.assertTrue(hull.getVertices().length == 0);
- Assert.assertTrue(hull.getLineSegments().length == 0);
+ // act
+ ConvexHull2D hull = generator.generate(Collections.emptyList());
+
+ // assert
+ Assert.assertEquals(0, hull.getVertices().size());
+ Assert.assertEquals(0, hull.getPath().getSegments().size());
+ Assert.assertNull(hull.getRegion());
}
@Test
public void testOnePoint() {
+ // arrange
List<Vector2D> points = createRandomPoints(1);
+
+ // act
ConvexHull2D hull = generator.generate(points);
- Assert.assertTrue(hull.getVertices().length == 1);
- Assert.assertTrue(hull.getLineSegments().length == 0);
+
+ // assert
+ Assert.assertEquals(1, hull.getVertices().size());
+ Assert.assertEquals(0, hull.getPath().getSegments().size());
+ Assert.assertNull(hull.getRegion());
}
@Test
public void testTwoPoints() {
+ // arrange
List<Vector2D> points = createRandomPoints(2);
+
+ // act
ConvexHull2D hull = generator.generate(points);
- Assert.assertTrue(hull.getVertices().length == 2);
- Assert.assertTrue(hull.getLineSegments().length == 1);
+
+ // assert
+ Assert.assertEquals(2, hull.getVertices().size());
+ Assert.assertEquals(1, hull.getPath().getSegments().size());
+ Assert.assertNull(hull.getRegion());
}
@Test
public void testAllIdentical() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(1, 1));
+ // act
final ConvexHull2D hull = generator.generate(points);
- Assert.assertTrue(hull.getVertices().length == 1);
+
+ // assert
+ Assert.assertEquals(1, hull.getVertices().size());
+ Assert.assertEquals(0, hull.getPath().getSegments().size());
+ Assert.assertNull(hull.getRegion());
}
@Test
@@ -101,13 +130,18 @@ public abstract class ConvexHullGenerator2DAbstractTest {
int size = (int) Math.floor(random.nextDouble() * 96.0 + 4.0);
List<Vector2D> points = createRandomPoints(size);
+
+ // act
ConvexHull2D hull = generator.generate(reducePoints(points));
+
+ // assert
checkConvexHull(points, hull);
}
}
@Test
public void testCollinearPoints() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -115,12 +149,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4, 1));
points.add(Vector2D.of(10, 1));
+ // act
final ConvexHull2D hull = generator.generate(points);
+
+ // assert
checkConvexHull(points, hull);
}
@Test
public void testCollinearPointsReverse() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -128,12 +166,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(10, 1));
points.add(Vector2D.of(4, 1));
+ // act
final ConvexHull2D hull = generator.generate(points);
+
+ // assert
checkConvexHull(points, hull);
}
@Test
public void testCollinearPointsIncluded() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -141,12 +183,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4, 1));
points.add(Vector2D.of(10, 1));
+ // act
final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+
+ // assert
checkConvexHull(points, hull, true);
}
@Test
public void testCollinearPointsIncludedReverse() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -154,12 +200,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(10, 1));
points.add(Vector2D.of(4, 1));
+ // act
final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+
+ // assert
checkConvexHull(points, hull, true);
}
@Test
public void testIdenticalPoints() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -167,12 +217,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4, 1));
points.add(Vector2D.of(1, 1));
+ // act
final ConvexHull2D hull = generator.generate(points);
+
+ // assert
checkConvexHull(points, hull);
}
@Test
public void testIdenticalPoints2() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -180,12 +234,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4, 1));
points.add(Vector2D.of(1, 1));
+ // act
final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+
+ // assert
checkConvexHull(points, hull, true);
}
@Test
public void testClosePoints() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
points.add(Vector2D.of(2, 2));
@@ -193,12 +251,16 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4, 1));
points.add(Vector2D.of(1.00001, 1));
+ // act
final ConvexHull2D hull = generator.generate(points);
+
+ // assert
checkConvexHull(points, hull);
}
@Test
public void testCollinearPointOnExistingBoundary() {
+ // --- arrange
// MATH-1135: check that collinear points on the hull are handled correctly
// when only a minimal hull shall be constructed
final Collection<Vector2D> points = new ArrayList<>();
@@ -213,33 +275,42 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(7.315199999999996, 34.1376));
points.add(Vector2D.of(7.3152, 30.48));
+ // --- act
final ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
+
+ // --- assert
checkConvexHull(points, hull);
}
@Test
- public void testCollinearPointsInAnyOrder() {
+ public void testCollinearPointsInAnyOrder_threeCollinearPoints() {
+ // --- arrange
// MATH-1148: collinear points on the hull might be in any order
// make sure that they are processed in the proper order
// for each algorithm.
List<Vector2D> points = new ArrayList<>();
-
- // first case: 3 points are collinear
points.add(Vector2D.of(16.078200000000184, -36.52519999989808));
points.add(Vector2D.of(19.164300000000186, -36.52519999989808));
points.add(Vector2D.of(19.1643, -25.28136477910407));
points.add(Vector2D.of(19.1643, -17.678400000004157));
+ // --- act/assert
ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
checkConvexHull(points, hull);
hull = createConvexHullGenerator(true).generate(points);
checkConvexHull(points, hull, true);
+ }
- points.clear();
+ @Test
+ public void testCollinearPointsInAnyOrder_multipleCollinearPoints() {
+ // --- arrange
+ // MATH-1148: collinear points on the hull might be in any order
+ // make sure that they are processed in the proper order
+ // for each algorithm.
- // second case: multiple points are collinear
+ List<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(0, -29.959696875));
points.add(Vector2D.of(0, -31.621809375));
points.add(Vector2D.of(0, -28.435696875));
@@ -250,7 +321,8 @@ public abstract class ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(4.572, -33.145809375));
points.add(Vector2D.of(4.572, -28.435696875));
- hull = createConvexHullGenerator(false).generate(points);
+ // --- act/assert
+ ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
checkConvexHull(points, hull);
hull = createConvexHullGenerator(true).generate(points);
@@ -259,7 +331,7 @@ public abstract class ConvexHullGenerator2DAbstractTest {
@Test
public void testIssue1123() {
-
+ // arrange
List<Vector2D> points = new ArrayList<>();
int[][] data = new int[][] {
@@ -338,9 +410,11 @@ public abstract class ConvexHullGenerator2DAbstractTest {
Vector2D.of(-11.0, 1.0),
};
+ // act
ConvexHull2D convHull = generator.generate(points);
- Region<Vector2D> hullRegion = convHull.createRegion();
+ Region<Vector2D> hullRegion = convHull.getRegion();
+ // assert
Assert.assertEquals(274.0, hullRegion.getSize(), 1.0e-12);
double perimeter = 0;
for (int i = 0; i < referenceHull.length; ++i) {
@@ -373,27 +447,22 @@ public abstract class ConvexHullGenerator2DAbstractTest {
protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
final boolean includesCollinearPoints) {
- checkConvexHull(points, hull, includesCollinearPoints, 1e-10);
- }
-
- protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
- final boolean includesCollinearPoints, final double tolerance) {
Assert.assertNotNull(hull);
- Assert.assertTrue(isConvex(hull, includesCollinearPoints, tolerance));
+ Assert.assertTrue(isConvex(hull, includesCollinearPoints));
checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
}
// verify that the constructed hull is really convex
- protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints,
- final double tolerance) {
+ protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints) {
- final Vector2D[] points = hull.getVertices();
+ final List<Vector2D> points = hull.getVertices();
int sign = 0;
+ int size = points.size();
- for (int i = 0; i < points.length; i++) {
- Vector2D p1 = points[i == 0 ? points.length - 1 : i - 1];
- Vector2D p2 = points[i];
- Vector2D p3 = points[i == points.length - 1 ? 0 : i + 1];
+ for (int i = 0; i < size; i++) {
+ Vector2D p1 = points.get(i == 0 ? size - 1 : i - 1);
+ Vector2D p2 = points.get(i);
+ Vector2D p3 = points.get(i == size - 1 ? 0 : i + 1);
Vector2D d1 = p2.subtract(p1);
Vector2D d2 = p3.subtract(p2);
@@ -402,7 +471,7 @@ public abstract class ConvexHullGenerator2DAbstractTest {
Assert.assertTrue(d2.norm() > 1e-10);
final double cross = LinearCombination.value(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
- final int cmp = Precision.compareTo(cross, 0.0, tolerance);
+ final int cmp = Precision.compareTo(cross, 0.0, TEST_EPS);
if (sign != 0 && cmp != sign) {
if (!includesCollinearPoints || cmp != 0) {
@@ -422,12 +491,12 @@ public abstract class ConvexHullGenerator2DAbstractTest {
final ConvexHull2D hull,
final boolean includesCollinearPoints) {
- final Collection<Vector2D> hullVertices = Arrays.asList(hull.getVertices());
- final Region<Vector2D> region = hull.createRegion();
+ final Collection<Vector2D> hullVertices = hull.getVertices();
+ final ConvexArea region = hull.getRegion();
for (final Vector2D p : points) {
RegionLocation location = region.classify(p);
- Assert.assertTrue(location != RegionLocation.OUTSIDE);
+ Assert.assertNotEquals(RegionLocation.OUTSIDE, location);
if (location == RegionLocation.BOUNDARY && includesCollinearPoints) {
Assert.assertTrue(hullVertices.contains(p));
diff --git a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java
index 71f29e8..aad5455 100644
--- a/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java
+++ b/commons-geometry-hull/src/test/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChainTest.java
@@ -30,13 +30,14 @@ public class MonotoneChainTest extends ConvexHullGenerator2DAbstractTest {
@Override
protected ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints) {
- return new MonotoneChain(includeCollinearPoints);
+ return new MonotoneChain(includeCollinearPoints, TEST_PRECISION);
}
// ------------------------------------------------------------------------------
@Test(expected = IllegalStateException.class)
public void testConvergenceException() {
+ // arrange
final Collection<Vector2D> points = new ArrayList<>();
points.add(Vector2D.of(1, 1));
@@ -48,8 +49,7 @@ public class MonotoneChainTest extends ConvexHullGenerator2DAbstractTest {
points.add(Vector2D.of(20, 40));
points.add(Vector2D.of(40, 1));
- @SuppressWarnings("unused")
- final ConvexHull2D hull = new MonotoneChain(true, new EpsilonDoublePrecisionContext(1)).generate(points);
+ // act/assert
+ new MonotoneChain(true, new EpsilonDoublePrecisionContext(1)).generate(points);
}
-
}
diff --git a/src/site/site.xml b/src/site/site.xml
index 0aa7035..237ef41 100644
--- a/src/site/site.xml
+++ b/src/site/site.xml
@@ -75,6 +75,7 @@
<item name="Core Interfaces" href="/userguide/index.html#interfaces"/>
<item name="Euclidean Space" href="/userguide/index.html#euclidean"/>
<item name="Spherical Space" href="/userguide/index.html#spherical"/>
+ <item name="Convex Hull" href="/userguide/index.html#hull"/>
</menu>
</body>
diff --git a/src/site/xdoc/userguide/index.xml b/src/site/xdoc/userguide/index.xml
index 1c0fd4e..1ddfe22 100644
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@ -76,6 +76,14 @@
</li>
</ul>
</li>
+ <li>
+ <a href="#hull">Convex Hull</a>
+ <ul>
+ <li>
+ <a href="#hull_euclidean_2d">Euclidean 2D</a>
+ </li>
+ </ul>
+ </li>
</ul>
</section>
@@ -1036,6 +1044,72 @@ List<GreatArcPath> minusPaths = minus.getBoundaryPaths(); // size = 1
</section>
+ <section name="Convex Hull" id="hull">
+ <p>
+ A <a href="http://en.wikipedia.org/wiki/Convex_hull">convex hull</a> of a region or shape in the smallest convex
+ set of points that completely contains the shape. For example, if a set of points in Euclidean 2D space are
+ represented by nails in a flat piece of wood, then the convex hull of that shape would be the path made by a
+ rubber band wrapped around all of the nails. Similarly, in Euclidean 3D space, the convex hull of a shape can be
+ visualized as the result of "shrink-wrapping" the shape with a very tight, non-flexible material.
+ </p>
+ <p>
+ A number of convex hull algorithms exist, for various spaces and dimensions, and it is the goal of the
+ <span class="code">commons-geometry-hull</span> module to provide implementations of these algorithms.
+ </p>
+
+ <subsection name="Convex Hull - Euclidean 2D" id="hull_euclidean_2d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/ConvexHullGenerator2D.html">ConvexHullGenerator2D</a> -
+ Interface for classes that implement convex hull algorithms in Euclidean 2D space.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/ConvexHull2D.html">ConvexHull2D</a> -
+ Class representing output from convex hull operations.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-hull/apidocs/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.html">MonotoneChain</a> -
+ Class implementing
+ <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">Andrew's monotone chain algorithm</a>
+ for computing convex hulls.
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>Monotone Chain</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-10);
+
+// create a list of input points for the algorithm
+List<Vector2D> pts = Arrays.asList(
+ Vector2D.ZERO,
+ Vector2D.of(0.5, 0.5),
+ Vector2D.of(0, 0.5),
+ Vector2D.of(0, 1),
+ Vector2D.of(0.25, 0.1),
+ Vector2D.of(1, 0),
+ Vector2D.of(1, 1),
+ Vector2D.of(0.75, 0.9)
+ );
+
+// create an instance of the monotone chain convex hull generator
+MonotoneChain mc = new MonotoneChain(precision);
+
+// compute the convex hull
+ConvexHull2D hull = mc.generate(pts);
+
+// list the vertices from the input that were used in the hull
+List<Vector2D> vertices = hull.getVertices(); // [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
+
+// get the hull as a region
+ConvexArea region = hull.getRegion();
+boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points
+ </source>
+ </subsection>
+ </section>
+
</body>
</document>