You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ma...@apache.org on 2023/09/04 01:04:04 UTC
[commons-geometry] 03/25: GEOMETRY-144
This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 031f91f5696e12163ba43e50f51cbb375ff8d20f
Author: Andreas Goß <an...@gmail.com>
AuthorDate: Wed Jul 19 18:35:50 2023 +0200
GEOMETRY-144
Move Test to euclidean.
---
.../geometry/euclidean/twod/hull/ConvexHull2D.java | 26 +-
.../euclidean/DocumentationExamplesTest.java | 39 ++
.../euclidean/twod/hull/ConvexHull2DTest.java | 177 +++++++
.../euclidean/twod/hull/ConvexHullBuilderTest.java | 58 +++
.../hull/ConvexHullGenerator2DAbstractTest.java | 532 +++++++++++++++++++++
5 files changed, 819 insertions(+), 13 deletions(-)
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
index d7ce45ae..07eed0a9 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
@@ -14,6 +14,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
package org.apache.commons.geometry.euclidean.twod.hull;
import java.util.ArrayList;
@@ -138,7 +139,7 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
private Vector2D maxY;
/** Collection of all remaining candidates for a convex hull. */
- private final Collection<Vector2D> points;
+ private final Collection<Vector2D> candidates;
/** A precision context for comparing points. */
private final Precision.DoubleEquivalence precision;
@@ -160,7 +161,7 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
public Builder(final boolean includeCollinearPoints, final Precision.DoubleEquivalence builderPrecision) {
this.precision = builderPrecision;
this.includeCollinearPoints = includeCollinearPoints;
- points = EuclideanCollections.pointSet2D(precision);
+ candidates = EuclideanCollections.pointSet2D(builderPrecision);
}
/** Appends the given point to a collection of possible hull points, if and only
@@ -175,7 +176,7 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
checkCorners(point);
//Only proceed if the quadrilateral is complete.
- if (points.size() < 4) {
+ if (candidates.size() < 4) {
return this;
}
@@ -188,7 +189,7 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
// check all points if they are within the quadrilateral
// in which case they can not be part of the convex hull
if (!insideQuadrilateral(point, quadrilateral)) {
- points.add(point);
+ candidates.add(point);
}
return this;
@@ -216,10 +217,10 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
*/
public ConvexHull2D build() {
Collection<Vector2D> hullVertices;
- if (points.size() < 2) {
- hullVertices = points;
+ if (candidates.size() < 2) {
+ hullVertices = candidates;
} else {
- hullVertices = findHullVertices(points);
+ hullVertices = findHullVertices(candidates);
}
if (!isConvex(hullVertices)) {
@@ -252,22 +253,21 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
*/
private void checkCorners(Vector2D point) {
if (minX == null || point.getX() < minX.getX()) {
- points.remove(minX);
minX = point;
+ candidates.add(point);
}
if (maxX == null || point.getX() > maxX.getX()) {
- points.remove(maxX);
maxX = point;
+ candidates.add(point);
}
if (minY == null || point.getY() < minY.getY()) {
- points.remove(minY);
minY = point;
+ candidates.add(point);
}
if (maxY == null || point.getY() > maxY.getY()) {
- points.remove(maxY);
maxY = point;
+ candidates.add(point);
}
- points.add(point);
}
/** Checks if the given point is located within the convex quadrilateral.
@@ -459,4 +459,4 @@ public final class ConvexHull2D implements ConvexHull<Vector2D> {
return true;
}
}
-}
\ No newline at end of file
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
index 5fe389cf..0c5dfe69 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
@@ -461,4 +461,43 @@ class DocumentationExamplesTest {
Assertions.assertEquals("b", plusXValue);
Assertions.assertNull(missingValue);
}
+
+// @Test TODO
+// void testMonotoneChainExample() {
+// final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
+//
+// // create a list of input points for the algorithm
+// final 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
+// final MonotoneChain mc = new MonotoneChain(precision);
+//
+// // compute the convex hull
+// final ConvexHull2D hull = mc.generate(pts);
+//
+// // list the vertices from the input that were used in the hull
+// final 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
+// final ConvexArea region = hull.getRegion();
+// final boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points
+//
+// // ---
+// Assertions.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);
+//
+// Assertions.assertTrue(containsAll);
+// }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2DTest.java
new file mode 100644
index 00000000..31279d5a
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2DTest.java
@@ -0,0 +1,177 @@
+/*
+ * 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.euclidean.twod.hull;
+
+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.euclidean.EuclideanTestUtils;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.geometry.euclidean.twod.path.LinePath;
+import org.apache.commons.numbers.core.Precision;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+class ConvexHull2DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final Precision.DoubleEquivalence TEST_PRECISION =
+ Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
+
+ @Test
+ void testProperties_noPoints() {
+ // act
+ final ConvexHull2D hull = new ConvexHull2D(Collections.emptyList(), TEST_PRECISION);
+
+ // assert
+ Assertions.assertEquals(0, hull.getVertices().size());
+
+ final LinePath path = hull.getPath();
+ Assertions.assertEquals(0, path.getElements().size());
+
+ final List<Vector2D> pathVertices = path.getVertexSequence();
+ Assertions.assertEquals(0, pathVertices.size());
+
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testProperties_singlePoint() {
+ // arrange
+ final List<Vector2D> vertices = Collections.singletonList(Vector2D.Unit.PLUS_X);
+
+ // act
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assertions.assertEquals(vertices, hull.getVertices());
+
+ final LinePath path = hull.getPath();
+ Assertions.assertEquals(0, path.getElements().size());
+
+ final List<Vector2D> pathVertices = path.getVertexSequence();
+ Assertions.assertEquals(0, pathVertices.size());
+
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testProperties_twoPoints() {
+ // arrange
+ final List<Vector2D> vertices = Arrays.asList(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
+
+ // act
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assertions.assertEquals(vertices, hull.getVertices());
+
+ final LinePath path = hull.getPath();
+ Assertions.assertEquals(1, path.getElements().size());
+
+ final List<Vector2D> pathVertices = path.getVertexSequence();
+ Assertions.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);
+
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testProperties_threePoints() {
+ // arrange
+ final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y);
+
+ // act
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assertions.assertEquals(vertices, hull.getVertices());
+
+ final LinePath path = hull.getPath();
+ Assertions.assertEquals(3, path.getElements().size());
+
+ final List<Vector2D> pathVertices = path.getVertexSequence();
+ Assertions.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);
+
+ Assertions.assertEquals(0.5, hull.getRegion().getSize(), TEST_EPS);
+ }
+
+ @Test
+ void testProperties_fourPoints() {
+ // arrange
+ final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X,
+ Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y);
+
+ // act
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // assert
+ Assertions.assertEquals(vertices, hull.getVertices());
+
+ final LinePath path = hull.getPath();
+ Assertions.assertEquals(4, path.getElements().size());
+
+ final List<Vector2D> pathVertices = path.getVertexSequence();
+ Assertions.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);
+
+ Assertions.assertEquals(1.0, hull.getRegion().getSize(), TEST_EPS);
+ }
+
+ @Test
+ void testVertexListCannotBeModified() {
+ // arrange
+ final List<Vector2D> vertices = new ArrayList<>();
+ vertices.add(Vector2D.Unit.PLUS_X);
+
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // act
+ final List<Vector2D> hullVertices = hull.getVertices();
+
+ // assert
+ Assertions.assertNotSame(vertices, hullVertices);
+
+ Assertions.assertThrows(UnsupportedOperationException.class, () -> hullVertices.add(Vector2D.Unit.PLUS_Y));
+ }
+
+ @Test
+ void testToString() {
+ // arrange
+ final List<Vector2D> vertices = Collections.singletonList(Vector2D.Unit.PLUS_X);
+ final ConvexHull2D hull = new ConvexHull2D(vertices, TEST_PRECISION);
+
+ // act
+ final String str = hull.toString();
+
+ // assert
+ GeometryTestUtils.assertContains("ConvexHull2D[vertices= [(1", str);
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullBuilderTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullBuilderTest.java
new file mode 100644
index 00000000..d15c72b2
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullBuilderTest.java
@@ -0,0 +1,58 @@
+/*
+ * 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.euclidean.twod.hull;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.numbers.core.Precision;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test class for MonotoneChain.
+ */
+class ConvexHullBuilderTest extends ConvexHullGenerator2DAbstractTest {
+
+ @Override
+ protected ConvexHull2D.Builder createConvexHullGenerator(final boolean includeCollinearPoints) {
+ return new ConvexHull2D.Builder(includeCollinearPoints, TEST_PRECISION);
+ }
+
+ // ------------------------------------------------------------------------------
+
+ @Test
+ void testConvergenceException() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(1, 5));
+ points.add(Vector2D.of(0, 7));
+ points.add(Vector2D.of(1, 10));
+ points.add(Vector2D.of(1, 20));
+ points.add(Vector2D.of(20, 20));
+ points.add(Vector2D.of(20, 40));
+ points.add(Vector2D.of(40, 1));
+
+ // act/assert
+ ConvexHull2D.Builder builder = new ConvexHull2D.Builder(true, Precision.doubleEquivalenceOfEpsilon(1));
+ builder.append(points);
+ Assertions.assertThrows(IllegalStateException.class, () -> builder.build());
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
new file mode 100644
index 00000000..70373314
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
@@ -0,0 +1,532 @@
+/*
+ * 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.euclidean.twod.hull;
+
+import java.util.ArrayList;
+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.euclidean.twod.ConvexArea;
+import org.apache.commons.geometry.euclidean.twod.Vector2D;
+import org.apache.commons.geometry.euclidean.twod.hull.ConvexHull2D.Builder;
+import org.apache.commons.numbers.core.Precision;
+import org.apache.commons.numbers.core.Sum;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.simple.RandomSource;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.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 Precision.DoubleEquivalence TEST_PRECISION =
+ Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
+
+ protected ConvexHull2D.Builder generator;
+
+ protected UniformRandomProvider random;
+
+ protected abstract ConvexHull2D.Builder createConvexHullGenerator(boolean includeCollinearPoints);
+
+ protected Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
+ // do nothing by default, may be overridden by other tests
+ return points;
+ }
+
+ @BeforeEach
+ public void setUp() {
+ // by default, do not include collinear points
+ generator = createConvexHullGenerator(false);
+ random = RandomSource.XO_SHI_RO_256_PP.create(10);
+ }
+
+ // ------------------------------------------------------------------------------
+
+ @Test
+ void testEmpty() {
+ // act
+ generator.append(Collections.emptyList());
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ Assertions.assertEquals(0, hull.getVertices().size());
+ Assertions.assertEquals(0, hull.getPath().getElements().size());
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testOnePoint() {
+ // arrange
+ final List<Vector2D> points = createRandomPoints(1);
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ Assertions.assertEquals(1, hull.getVertices().size());
+ Assertions.assertEquals(0, hull.getPath().getElements().size());
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testTwoPoints() {
+ // arrange
+ final List<Vector2D> points = createRandomPoints(2);
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ Assertions.assertEquals(2, hull.getVertices().size());
+ Assertions.assertEquals(1, hull.getPath().getElements().size());
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ 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
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ Assertions.assertEquals(1, hull.getVertices().size());
+ Assertions.assertEquals(0, hull.getPath().getElements().size());
+ Assertions.assertNull(hull.getRegion());
+ }
+
+ @Test
+ void testConvexHull() {
+ // execute 100 random variations
+ for (int i = 0; i < 100; i++) {
+ // randomize the size from 4 to 100
+ final int size = (int) Math.floor(random.nextDouble() * 96.0 + 4.0);
+
+ final List<Vector2D> points = createRandomPoints(size);
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ checkConvexHull(points, hull);
+ }
+ }
+
+ @Test
+ void testCollinearPoints() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(4, 1));
+ points.add(Vector2D.of(10, 1));
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ checkConvexHull(points, hull);
+ }
+
+ @Test
+ void testCollinearPointsReverse() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(10, 1));
+ points.add(Vector2D.of(4, 1));
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ checkConvexHull(points, hull);
+ }
+
+ @Test
+ void testCollinearPointsIncluded() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(4, 1));
+ points.add(Vector2D.of(10, 1));
+
+ // act
+ ConvexHull2D.Builder builder = createConvexHullGenerator(true);
+ builder.append(points);
+ final ConvexHull2D hull = builder.build();
+
+ // assert
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
+ void testCollinearPointsIncludedReverse() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(10, 1));
+ points.add(Vector2D.of(4, 1));
+
+ // act
+ ConvexHull2D.Builder builder = createConvexHullGenerator(true);
+ builder.append(points);
+ final ConvexHull2D hull = builder.build();
+
+ // assert
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
+ void testIdenticalPoints() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(4, 1));
+ points.add(Vector2D.of(1, 1));
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ checkConvexHull(points, hull);
+ }
+
+ @Test
+ void testIdenticalPoints2() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(4, 1));
+ points.add(Vector2D.of(1, 1));
+
+ // act
+ ConvexHull2D.Builder builder = createConvexHullGenerator(true);
+ builder.append(points);
+ final ConvexHull2D hull = builder.build();
+
+ // assert
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
+ void testClosePoints() {
+ // arrange
+ final Collection<Vector2D> points = new ArrayList<>();
+ points.add(Vector2D.of(1, 1));
+ points.add(Vector2D.of(2, 2));
+ points.add(Vector2D.of(2, 4));
+ points.add(Vector2D.of(4, 1));
+ points.add(Vector2D.of(1.00001, 1));
+
+ // act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // assert
+ checkConvexHull(points, hull);
+ }
+
+ @Test
+ 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<>();
+ points.add(Vector2D.of(7.3152, 34.7472));
+ points.add(Vector2D.of(6.400799999999997, 34.747199999999985));
+ points.add(Vector2D.of(5.486399999999997, 34.7472));
+ points.add(Vector2D.of(4.876799999999999, 34.7472));
+ points.add(Vector2D.of(4.876799999999999, 34.1376));
+ points.add(Vector2D.of(4.876799999999999, 30.48));
+ points.add(Vector2D.of(6.0959999999999965, 30.48));
+ points.add(Vector2D.of(6.0959999999999965, 34.1376));
+ points.add(Vector2D.of(7.315199999999996, 34.1376));
+ points.add(Vector2D.of(7.3152, 30.48));
+
+ // --- act
+ generator.append(points);
+ final ConvexHull2D hull = generator.build();
+
+ // --- assert
+ checkConvexHull(points, hull);
+ }
+
+ @Test
+ 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.
+
+ final List<Vector2D> points = new ArrayList<>();
+ 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.Builder builder = createConvexHullGenerator(false);
+ builder.append(points);
+ ConvexHull2D hull = builder.build();
+ checkConvexHull(points, hull);
+
+ builder = createConvexHullGenerator(true);
+ builder.append(points);
+ hull = builder.build();
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
+ 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.
+
+ final 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));
+ points.add(Vector2D.of(0, -33.145809375));
+ points.add(Vector2D.of(3.048, -33.145809375));
+ points.add(Vector2D.of(3.048, -31.621809375));
+ points.add(Vector2D.of(3.048, -29.959696875));
+ points.add(Vector2D.of(4.572, -33.145809375));
+ points.add(Vector2D.of(4.572, -28.435696875));
+
+ // --- act/assert
+ Builder builder = createConvexHullGenerator(false);
+ builder.append(points);
+ ConvexHull2D hull = builder.build();
+ checkConvexHull(points, hull);
+
+ builder = createConvexHullGenerator(true);
+ builder.append(points);
+ hull = builder.build();
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
+ void testIssue1123() {
+ // arrange
+ final List<Vector2D> points = new ArrayList<>();
+
+ final int[][] data = {
+ {-11, -1}, {-11, 0}, {-11, 1},
+ {-10, -3}, {-10, -2}, {-10, -1}, {-10, 0}, {-10, 1},
+ {-10, 2}, {-10, 3}, {-9, -4}, {-9, -3}, {-9, -2},
+ {-9, -1}, {-9, 0}, {-9, 1}, {-9, 2}, {-9, 3},
+ {-9, 4}, {-8, -5}, {-8, -4}, {-8, -3}, {-8, -2},
+ {-8, -1}, {-8, 0}, {-8, 1}, {-8, 2}, {-8, 3},
+ {-8, 4}, {-8, 5}, {-7, -6}, {-7, -5}, {-7, -4},
+ {-7, -3}, {-7, -2}, {-7, -1}, {-7, 0}, {-7, 1},
+ {-7, 2}, {-7, 3}, {-7, 4}, {-7, 5}, {-7, 6},
+ {-6, -7}, {-6, -6}, {-6, -5}, {-6, -4}, {-6, -3},
+ {-6, -2}, {-6, -1}, {-6, 0}, {-6, 1}, {-6, 2},
+ {-6, 3}, {-6, 4}, {-6, 5}, {-6, 6}, {-6, 7},
+ {-5, -7}, {-5, -6}, {-5, -5}, {-5, -4}, {-5, -3},
+ {-5, -2}, {-5, 4}, {-5, 5}, {-5, 6}, {-5, 7},
+ {-4, -7}, {-4, -6}, {-4, -5}, {-4, -4}, {-4, -3},
+ {-4, -2}, {-4, 4}, {-4, 5}, {-4, 6}, {-4, 7},
+ {-3, -8}, {-3, -7}, {-3, -6}, {-3, -5}, {-3, -4},
+ {-3, -3}, {-3, -2}, {-3, 4}, {-3, 5}, {-3, 6},
+ {-3, 7}, {-3, 8}, {-2, -8}, {-2, -7}, {-2, -6},
+ {-2, -5}, {-2, -4}, {-2, -3}, {-2, -2}, {-2, 4},
+ {-2, 5}, {-2, 6}, {-2, 7}, {-2, 8}, {-1, -8},
+ {-1, -7}, {-1, -6}, {-1, -5}, {-1, -4}, {-1, -3},
+ {-1, -2}, {-1, 4}, {-1, 5}, {-1, 6}, {-1, 7},
+ {-1, 8}, {0, -8}, {0, -7}, {0, -6}, {0, -5},
+ {0, -4}, {0, -3}, {0, -2}, {0, 4}, {0, 5}, {0, 6},
+ {0, 7}, {0, 8}, {1, -8}, {1, -7}, {1, -6}, {1, -5},
+ {1, -4}, {1, -3}, {1, -2}, {1, -1}, {1, 0}, {1, 1},
+ {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7},
+ {1, 8}, {2, -8}, {2, -7}, {2, -6}, {2, -5},
+ {2, -4}, {2, -3}, {2, -2}, {2, -1}, {2, 0}, {2, 1},
+ {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7},
+ {2, 8}, {3, -8}, {3, -7}, {3, -6}, {3, -5},
+ {3, -4}, {3, -3}, {3, -2}, {3, -1}, {3, 0}, {3, 1},
+ {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7},
+ {3, 8}, {4, -7}, {4, -6}, {4, -5}, {4, -4},
+ {4, -3}, {4, -2}, {4, -1}, {4, 0}, {4, 1}, {4, 2},
+ {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {5, -7},
+ {5, -6}, {5, -5}, {5, -4}, {5, -3}, {5, -2},
+ {5, -1}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4},
+ {5, 5}, {5, 6}, {5, 7}, {6, -7}, {6, -6}, {6, -5},
+ {6, -4}, {6, -3}, {6, -2}, {6, -1}, {6, 0}, {6, 1},
+ {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7},
+ {7, -6}, {7, -5}, {7, -4}, {7, -3}, {7, -2},
+ {7, -1}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4},
+ {7, 5}, {7, 6}, {8, -5}, {8, -4}, {8, -3}, {8, -2},
+ {8, -1}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4},
+ {8, 5}, {9, -4}, {9, -3}, {9, -2}, {9, -1}, {9, 0},
+ {9, 1}, {9, 2}, {9, 3}, {9, 4}, {10, -3}, {10, -2},
+ {10, -1}, {10, 0}, {10, 1}, {10, 2}, {10, 3},
+ {11, -1}, {11, 0}, {11, 1}
+ };
+
+ for (final int[] line : data) {
+ points.add(Vector2D.of(line[0], line[1]));
+ }
+
+ final Vector2D[] referenceHull = {
+ Vector2D.of(-11.0, -1.0),
+ Vector2D.of(-10.0, -3.0),
+ Vector2D.of(-6.0, -7.0),
+ Vector2D.of(-3.0, -8.0),
+ Vector2D.of(3.0, -8.0),
+ Vector2D.of(6.0, -7.0),
+ Vector2D.of(10.0, -3.0),
+ Vector2D.of(11.0, -1.0),
+ Vector2D.of(11.0, 1.0),
+ Vector2D.of(10.0, 3.0),
+ Vector2D.of(6.0, 7.0),
+ Vector2D.of(3.0, 8.0),
+ Vector2D.of(-3.0, 8.0),
+ Vector2D.of(-6.0, 7.0),
+ Vector2D.of(-10.0, 3.0),
+ Vector2D.of(-11.0, 1.0),
+ };
+
+ // act
+ generator.append(points);
+ final ConvexHull2D convHull = generator.build();
+ final Region<Vector2D> hullRegion = convHull.getRegion();
+
+ // assert
+ Assertions.assertEquals(274.0, hullRegion.getSize(), 1.0e-12);
+ double perimeter = 0;
+ for (int i = 0; i < referenceHull.length; ++i) {
+ perimeter += referenceHull[i].distance(
+ referenceHull[(i + 1) % referenceHull.length]);
+ }
+ Assertions.assertEquals(perimeter, hullRegion.getBoundarySize(), 1.0e-12);
+
+ for (final Vector2D vector2D : referenceHull) {
+ Assertions.assertEquals(RegionLocation.BOUNDARY, hullRegion.classify(vector2D));
+ }
+
+ }
+
+ // ------------------------------------------------------------------------------
+
+ protected final List<Vector2D> createRandomPoints(final int size) {
+ // create the cloud container
+ final List<Vector2D> points = new ArrayList<>(size);
+ // fill the cloud with a random distribution of points
+ for (int i = 0; i < size; i++) {
+ points.add(Vector2D.of(random.nextDouble() * 2.0 - 1.0, random.nextDouble() * 2.0 - 1.0));
+ }
+ return points;
+ }
+
+ protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
+ checkConvexHull(points, hull, false);
+ }
+
+ protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
+ final boolean includesCollinearPoints) {
+ Assertions.assertNotNull(hull);
+ Assertions.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 List<Vector2D> points = hull.getVertices();
+ int sign = 0;
+ final int size = points.size();
+
+ for (int i = 0; i < size; i++) {
+ final Vector2D p1 = points.get(i == 0 ? size - 1 : i - 1);
+ final Vector2D p2 = points.get(i);
+ final Vector2D p3 = points.get(i == size - 1 ? 0 : i + 1);
+
+ final Vector2D d1 = p2.subtract(p1);
+ final Vector2D d2 = p3.subtract(p2);
+
+ Assertions.assertTrue(d1.norm() > 1e-10);
+ Assertions.assertTrue(d2.norm() > 1e-10);
+
+ final double cross = Sum.create()
+ .addProduct(d1.getX(), d2.getY())
+ .addProduct(-d1.getY(), d2.getX()).getAsDouble();
+ final int cmp = Precision.compareTo(cross, 0.0, TEST_EPS);
+
+ if (sign != 0 && cmp != sign) {
+ if (!includesCollinearPoints || cmp != 0) {
+ // in case of collinear points the cross product will be zero
+ return false;
+ }
+ }
+
+ sign = cmp;
+ }
+
+ return true;
+ }
+
+ // verify that all points are inside the convex hull region
+ protected final void checkPointsInsideHullRegion(final Collection<? extends Vector2D> points,
+ final ConvexHull2D hull,
+ final boolean includesCollinearPoints) {
+
+ final Collection<Vector2D> hullVertices = hull.getVertices();
+ final ConvexArea region = hull.getRegion();
+
+ for (final Vector2D p : points) {
+ final RegionLocation location = region.classify(p);
+ Assertions.assertNotEquals(RegionLocation.OUTSIDE, location);
+
+ if (location == RegionLocation.BOUNDARY && includesCollinearPoints) {
+ Assertions.assertTrue(hullVertices.contains(p));
+ }
+ }
+ }
+}