Repository: TheAlgorithms/Java
Pull request #5789 (2024-10-14 03:31:16)

feat: Add `ConvexHull` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5789?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `94.73684%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 64.37%. Comparing base [(`213fd5a`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/213fd5a4931ba1cb74fed76ff97043ae34ff174b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`77f739b`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/77f739bca92faddbfd7e114a8649a0d0df73c687?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5789?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...com/thealgorithms/divideandconquer/ConvexHull.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5789?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdivideandconquer%2FConvexHull.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kaXZpZGVhbmRjb25xdWVyL0NvbnZleEh1bGwuamF2YQ==) | 94.73% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5789?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5789      +/-   ##
============================================
+ Coverage     64.21%   64.37%   +0.15%     
- Complexity     4216     4241      +25     
============================================
  Files           588      589       +1     
  Lines         16426    16502      +76     
  Branches       3170     3189      +19     
============================================
+ Hits          10548    10623      +75     
- Misses         5448     5449       +1     
  Partials        430      430              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5789?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 4c454088..a1feab7b 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -304,7 +304,9 @@
             * [WildcardMatching](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java)
             * [WineProblem](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/WineProblem.java)
           * geometry
+            * [ConvexHull](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/geometry/ConvexHull.java)
             * [GrahamScan](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/geometry/GrahamScan.java)
+            * [Point](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/geometry/Point.java)
           * greedyalgorithms
             * [ActivitySelection](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java)
             * [BinaryAddition](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/BinaryAddition.java)
@@ -896,6 +898,7 @@
             * [WildcardMatchingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java)
             * [WineProblemTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/WineProblemTest.java)
           * geometry
+            * [ConvexHullTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/geometry/ConvexHullTest.java)
             * [GrahamScanTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java)
           * greedyalgorithms
             * [ActivitySelectionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/ActivitySelectionTest.java)
diff --git a/src/main/java/com/thealgorithms/geometry/ConvexHull.java b/src/main/java/com/thealgorithms/geometry/ConvexHull.java
new file mode 100644
index 00000000..19cecdc3
--- /dev/null
+++ b/src/main/java/com/thealgorithms/geometry/ConvexHull.java
@@ -0,0 +1,116 @@
+package com.thealgorithms.geometry;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+/**
+ * A class providing algorithms to compute the convex hull of a set of points
+ * using brute-force and recursive methods.
+ *
+ * Convex hull: The smallest convex polygon that contains all the given points.
+ *
+ * Algorithms provided:
+ * 1. Brute-Force Method
+ * 2. Recursive (Divide-and-Conquer) Method
+ *
+ * @author Hardvan
+ */
+public final class ConvexHull {
+    private ConvexHull() {
+    }
+
+    private static boolean checkPointOrientation(Point i, Point j, Point k) {
+        int detK = Point.orientation(i, j, k);
+        if (detK > 0) {
+            return true; // pointsLeftOfIJ
+        } else if (detK < 0) {
+            return false; // pointsRightOfIJ
+        } else {
+            return k.compareTo(i) >= 0 && k.compareTo(j) <= 0;
+        }
+    }
+
+    public static List<Point> convexHullBruteForce(List<Point> points) {
+        Set<Point> convexSet = new TreeSet<>(Comparator.naturalOrder());
+
+        for (int i = 0; i < points.size() - 1; i++) {
+            for (int j = i + 1; j < points.size(); j++) {
+                boolean allPointsOnOneSide = true;
+                boolean leftSide = checkPointOrientation(points.get(i), points.get(j), points.get((i + 1) % points.size()));
+
+                for (int k = 0; k < points.size(); k++) {
+                    if (k != i && k != j && checkPointOrientation(points.get(i), points.get(j), points.get(k)) != leftSide) {
+                        allPointsOnOneSide = false;
+                        break;
+                    }
+                }
+
+                if (allPointsOnOneSide) {
+                    convexSet.add(points.get(i));
+                    convexSet.add(points.get(j));
+                }
+            }
+        }
+
+        return new ArrayList<>(convexSet);
+    }
+
+    public static List<Point> convexHullRecursive(List<Point> points) {
+        Collections.sort(points);
+        Set<Point> convexSet = new HashSet<>();
+        Point leftMostPoint = points.get(0);
+        Point rightMostPoint = points.get(points.size() - 1);
+
+        convexSet.add(leftMostPoint);
+        convexSet.add(rightMostPoint);
+
+        List<Point> upperHull = new ArrayList<>();
+        List<Point> lowerHull = new ArrayList<>();
+
+        for (int i = 1; i < points.size() - 1; i++) {
+            int det = Point.orientation(leftMostPoint, rightMostPoint, points.get(i));
+            if (det > 0) {
+                upperHull.add(points.get(i));
+            } else if (det < 0) {
+                lowerHull.add(points.get(i));
+            }
+        }
+
+        constructHull(upperHull, leftMostPoint, rightMostPoint, convexSet);
+        constructHull(lowerHull, rightMostPoint, leftMostPoint, convexSet);
+
+        List<Point> result = new ArrayList<>(convexSet);
+        Collections.sort(result);
+        return result;
+    }
+
+    private static void constructHull(List<Point> points, Point left, Point right, Set<Point> convexSet) {
+        if (!points.isEmpty()) {
+            Point extremePoint = null;
+            int extremePointDistance = Integer.MIN_VALUE;
+            List<Point> candidatePoints = new ArrayList<>();
+
+            for (Point p : points) {
+                int det = Point.orientation(left, right, p);
+                if (det > 0) {
+                    candidatePoints.add(p);
+                    if (det > extremePointDistance) {
+                        extremePointDistance = det;
+                        extremePoint = p;
+                    }
+                }
+            }
+
+            if (extremePoint != null) {
+                constructHull(candidatePoints, left, extremePoint, convexSet);
+                convexSet.add(extremePoint);
+                constructHull(candidatePoints, extremePoint, right, convexSet);
+            }
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/geometry/GrahamScan.java b/src/main/java/com/thealgorithms/geometry/GrahamScan.java
index 1a361378..1a373cf3 100644
--- a/src/main/java/com/thealgorithms/geometry/GrahamScan.java
+++ b/src/main/java/com/thealgorithms/geometry/GrahamScan.java
@@ -2,7 +2,6 @@ package com.thealgorithms.geometry;
 
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Comparator;
 import java.util.Stack;
 
 /**
@@ -66,93 +65,4 @@ public class GrahamScan {
     public Iterable<Point> hull() {
         return new ArrayList<>(hull);
     }
-
-    public record Point(int x, int y) implements Comparable<Point> {
-
-        /**
-         * Default constructor
-         * @param x x-coordinate
-         * @param y y-coordinate
-         */
-        public Point {
-        }
-
-        /**
-         * @return the x-coordinate
-         */
-        @Override
-        public int x() {
-            return x;
-        }
-
-        /**
-         * @return the y-coordinate
-         */
-        @Override
-        public int y() {
-            return y;
-        }
-
-        /**
-         * Determines the orientation of the triplet (a, b, c).
-         *
-         * @param a The first point
-         * @param b The second point
-         * @param c The third point
-         * @return -1 if (a, b, c) is clockwise, 0 if collinear, +1 if counterclockwise
-         */
-        public static int orientation(Point a, Point b, Point c) {
-            int val = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
-            return Integer.compare(val, 0);
-        }
-
-        /**
-         * Compares this point with another point.
-         *
-         * @param p2 The point to compare to
-         * @return A positive integer if this point is greater, a negative integer if less, or 0 if equal
-         */
-        @Override
-        public int compareTo(Point p2) {
-            int cmpY = Integer.compare(this.y, p2.y);
-            return cmpY != 0 ? cmpY : Integer.compare(this.x, p2.x);
-        }
-
-        /**
-         * Returns a comparator to sort points by their polar order relative to this point.
-         *
-         * @return A polar order comparator
-         */
-        public Comparator<Point> polarOrder() {
-            return new PolarOrder();
-        }
-
-        private final class PolarOrder implements Comparator<Point> {
-            @Override
-            public int compare(Point p1, Point p2) {
-                int dx1 = p1.x - x;
-                int dy1 = p1.y - y;
-                int dx2 = p2.x - x;
-                int dy2 = p2.y - y;
-
-                if (dy1 >= 0 && dy2 < 0) {
-                    return -1; // p1 above p2
-                } else if (dy2 >= 0 && dy1 < 0) {
-                    return 1; // p1 below p2
-                } else if (dy1 == 0 && dy2 == 0) { // Collinear and horizontal
-                    return Integer.compare(dx2, dx1);
-                } else {
-                    return -orientation(Point.this, p1, p2); // Compare orientation
-                }
-            }
-        }
-
-        /**
-         * @return A string representation of this point in the format (x, y)
-         */
-        @Override
-        public String toString() {
-            return String.format("(%d, %d)", x, y);
-        }
-    }
 }
diff --git a/src/main/java/com/thealgorithms/geometry/Point.java b/src/main/java/com/thealgorithms/geometry/Point.java
new file mode 100644
index 00000000..564edb4b
--- /dev/null
+++ b/src/main/java/com/thealgorithms/geometry/Point.java
@@ -0,0 +1,45 @@
+package com.thealgorithms.geometry;
+
+import java.util.Comparator;
+
+public record Point(int x, int y) implements Comparable<Point> {
+
+    @Override
+    public int compareTo(Point other) {
+        int cmpY = Integer.compare(this.y, other.y);
+        return cmpY != 0 ? cmpY : Integer.compare(this.x, other.x);
+    }
+
+    @Override
+    public String toString() {
+        return String.format("(%d, %d)", x, y);
+    }
+
+    public Comparator<Point> polarOrder() {
+        return new PolarOrder();
+    }
+
+    public static int orientation(Point a, Point b, Point c) {
+        return Integer.compare((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x), 0);
+    }
+
+    private final class PolarOrder implements Comparator<Point> {
+        @Override
+        public int compare(Point p1, Point p2) {
+            int dx1 = p1.x - x;
+            int dy1 = p1.y - y;
+            int dx2 = p2.x - x;
+            int dy2 = p2.y - y;
+
+            if (dy1 >= 0 && dy2 < 0) {
+                return -1; // p1 above p2
+            } else if (dy2 >= 0 && dy1 < 0) {
+                return 1; // p1 below p2
+            } else if (dy1 == 0 && dy2 == 0) { // Collinear and horizontal
+                return Integer.compare(dx2, dx1);
+            } else {
+                return -orientation(Point.this, p1, p2); // Compare orientation
+            }
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/geometry/ConvexHullTest.java b/src/test/java/com/thealgorithms/geometry/ConvexHullTest.java
new file mode 100644
index 00000000..e3e32e43
--- /dev/null
+++ b/src/test/java/com/thealgorithms/geometry/ConvexHullTest.java
@@ -0,0 +1,40 @@
+package com.thealgorithms.geometry;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Arrays;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+public class ConvexHullTest {
+
+    @Test
+    void testConvexHullBruteForce() {
+        List<Point> points = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 1));
+        List<Point> expected = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 1));
+        assertEquals(expected, ConvexHull.convexHullBruteForce(points));
+
+        points = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 0));
+        expected = Arrays.asList(new Point(0, 0), new Point(10, 0));
+        assertEquals(expected, ConvexHull.convexHullBruteForce(points));
+
+        points = Arrays.asList(new Point(0, 3), new Point(2, 2), new Point(1, 1), new Point(2, 1), new Point(3, 0), new Point(0, 0), new Point(3, 3), new Point(2, -1), new Point(2, -4), new Point(1, -3));
+        expected = Arrays.asList(new Point(2, -4), new Point(1, -3), new Point(0, 0), new Point(3, 0), new Point(0, 3), new Point(3, 3));
+        assertEquals(expected, ConvexHull.convexHullBruteForce(points));
+    }
+
+    @Test
+    void testConvexHullRecursive() {
+        List<Point> points = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 1));
+        List<Point> expected = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 1));
+        assertEquals(expected, ConvexHull.convexHullRecursive(points));
+
+        points = Arrays.asList(new Point(0, 0), new Point(1, 0), new Point(10, 0));
+        expected = Arrays.asList(new Point(0, 0), new Point(10, 0));
+        assertEquals(expected, ConvexHull.convexHullRecursive(points));
+
+        points = Arrays.asList(new Point(0, 3), new Point(2, 2), new Point(1, 1), new Point(2, 1), new Point(3, 0), new Point(0, 0), new Point(3, 3), new Point(2, -1), new Point(2, -4), new Point(1, -3));
+        expected = Arrays.asList(new Point(2, -4), new Point(1, -3), new Point(0, 0), new Point(3, 0), new Point(0, 3), new Point(3, 3));
+        assertEquals(expected, ConvexHull.convexHullRecursive(points));
+    }
+}
diff --git a/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java b/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java
index e59cd6b8..62227388 100644
--- a/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java
+++ b/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java
@@ -7,7 +7,7 @@ import org.junit.jupiter.api.Test;
 public class GrahamScanTest {
     @Test
     void testGrahamScan() {
-        GrahamScan.Point[] points = {new GrahamScan.Point(0, 3), new GrahamScan.Point(1, 1), new GrahamScan.Point(2, 2), new GrahamScan.Point(4, 4), new GrahamScan.Point(0, 0), new GrahamScan.Point(1, 2), new GrahamScan.Point(3, 1), new GrahamScan.Point(3, 3)};
+        Point[] points = {new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4), new Point(0, 0), new Point(1, 2), new Point(3, 1), new Point(3, 3)};
         String expectedResult = "[(0, 0), (3, 1), (4, 4), (0, 3)]";
 
         GrahamScan graham = new GrahamScan(points);