[commons-geometry] 18/25: GEOMETRY-144

[mattjuntunen]

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 ffc419c4f89a479c82f2dd97fcded467a30a7040
Author: Andreas <andreas.goss1...@gmail.com>
AuthorDate: Sat Aug 12 15:11:29 2023 +0200

    GEOMETRY-144
    
    Remove unnecessary check and fix error for not yet well formed
    quadrilaterals. Valid points are not dismissed anymore.
---
 .../geometry/euclidean/twod/hull/ConvexHull2D.java |  6 +--
 .../euclidean/twod/hull/ConvexHullBuilderTest.java | 54 ++++++++++++++++++++++
 2 files changed, 56 insertions(+), 4 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 b67b1550..3b8710ce 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
@@ -178,14 +178,12 @@ public final class ConvexHull2D implements 
ConvexHull<Vector2D> {
             // Checks if the given point supersedes one of the corners.
             checkCorners(point);
 
-            // Only proceed if the quadrilateral is complete.
-            if (candidates.size() < 4) {
-                return this;
-            }
 
             buildQuadrilateral(minY, maxX, maxY, minX);
             // if the quadrilateral is not well formed, e.g. only 2 points, do 
not attempt to reduce
             if (quadrilateral.size() < 3) {
+               //Point cannot yet be dismissed.
+               candidates.add(point);
                 return this;
             }
 
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
index 735f4767..249ee015 100644
--- 
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
@@ -230,6 +230,43 @@ class ConvexHullBuilderTest {
         checkConvexHull(points, hull, true);
     }
 
+    @Test
+    void testCollinearPointsIncludedColinearToFirstSide() {
+       // arrange
+       final Collection<Vector2D> points = new ArrayList<>();
+       points.add(Vector2D.of(1, 1));
+       points.add(Vector2D.of(2, 4));
+       points.add(Vector2D.of(10, 1));
+       points.add(Vector2D.of(1.5, 2.5));
+
+       // act
+       ConvexHull2D.Builder builder = createConvexHullGenerator(true);
+       builder.append(points);
+       final ConvexHull2D hull = builder.build();
+
+       // assert
+       checkConvexHull(points, hull, true);
+    }
+
+    @Test
+    void testCollinearPointsExcludedColinearToFirstSide() {
+       // arrange
+       final Collection<Vector2D> points = new ArrayList<>();
+       points.add(Vector2D.of(1, 1));
+       points.add(Vector2D.of(2, 4));
+       points.add(Vector2D.of(10, 1));
+       points.add(Vector2D.of(1.5, 2.5));
+
+       // act
+       ConvexHull2D.Builder builder = createConvexHullGenerator(false);
+       builder.append(points);
+       final ConvexHull2D hull = builder.build();
+
+       points.remove(Vector2D.of(1.5, 2.5));
+       // assert
+       checkConvexHull(points, hull, false);
+    }
+
     @Test
     void testIdenticalPoints() {
         // arrange
@@ -285,6 +322,23 @@ class ConvexHullBuilderTest {
         checkConvexHull(points, hull);
     }
 
+    @Test
+    void testOrderisIrrelevant() {
+       // arrange
+       final Collection<Vector2D> points = new ArrayList<>();
+       points.add(Vector2D.of(0, 0));
+       points.add(Vector2D.of(6, 6));
+       points.add(Vector2D.of(3, 4));
+       points.add(Vector2D.of(12, 0));
+
+       // act
+       generator.append(points);
+       final ConvexHull2D hull = generator.build();
+
+       // assert
+       checkConvexHull(points, hull);
+    }
+
     @Test
     void testCollinearPointOnExistingBoundary() {
         // --- arrange