Repository: TheAlgorithms/Java
Pull request #5580 (2024-10-05 07:23:17)

Feature/line clipping algorithms


- [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/5580?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 `78.18182%` with `24 lines` in your changes missing coverage. Please review.
> Project coverage is 54.16%. Comparing base [(`87871ef`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/87871efcdbbcca3a86ac5c2a4e9647b6f8267cf5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`c60c1cf`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/c60c1cfbab092e2a5da7dc43ac35d9578e1332c2?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/5580?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...om/thealgorithms/lineclipping/CohenSutherland.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Flineclipping%2FCohenSutherland.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9saW5lY2xpcHBpbmcvQ29oZW5TdXRoZXJsYW5kLmphdmE=) | 87.50% | [6 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...ava/com/thealgorithms/lineclipping/utils/Line.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Flineclipping%2Futils%2FLine.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9saW5lY2xpcHBpbmcvdXRpbHMvTGluZS5qYXZh) | 36.36% | [4 Missing and 3 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...va/com/thealgorithms/lineclipping/utils/Point.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Flineclipping%2Futils%2FPoint.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9saW5lY2xpcHBpbmcvdXRpbHMvUG9pbnQuamF2YQ==) | 36.36% | [4 Missing and 3 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...va/com/thealgorithms/lineclipping/LiangBarsky.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Flineclipping%2FLiangBarsky.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9saW5lY2xpcHBpbmcvTGlhbmdCYXJza3kuamF2YQ==) | 90.62% | [1 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?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    #5580      +/-   ##
============================================
+ Coverage     53.96%   54.16%   +0.19%     
- Complexity     3387     3418      +31     
============================================
  Files           535      539       +4     
  Lines         15429    15539     +110     
  Branches       2942     2968      +26     
============================================
+ Hits           8327     8417      +90     
- Misses         6749     6762      +13     
- Partials        353      360       +7     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5580?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/src/main/java/com/thealgorithms/lineclipping/CohenSutherland.java b/src/main/java/com/thealgorithms/lineclipping/CohenSutherland.java
new file mode 100644
index 00000000..6e8611b8
--- /dev/null
+++ b/src/main/java/com/thealgorithms/lineclipping/CohenSutherland.java
@@ -0,0 +1,133 @@
+package com.thealgorithms.lineclipping;
+
+import com.thealgorithms.lineclipping.utils.Line;
+import com.thealgorithms.lineclipping.utils.Point;
+
+/**
+ * @author shikarisohan
+ * @since 10/4/24
+ * Cohen-Sutherland Line Clipping Algorithm
+ *
+ * This algorithm is used to clip a line segment to a rectangular window.
+ * It assigns a region code to each endpoint of the line segment, and
+ * then efficiently determines whether the line segment is fully inside,
+ * fully outside, or partially inside the window.
+ *
+ * Reference:
+ * https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
+ *
+ * Clipping window boundaries are defined as (xMin, yMin) and (xMax, yMax).
+ * The algorithm computes the clipped line segment if it's partially or
+ * fully inside the clipping window.
+ */
+public class CohenSutherland {
+
+    // Region codes for the 9 regions
+    private static final int INSIDE = 0; // 0000
+    private static final int LEFT = 1; // 0001
+    private static final int RIGHT = 2; // 0010
+    private static final int BOTTOM = 4; // 0100
+    private static final int TOP = 8; // 1000
+
+    // Define the clipping window
+    double xMin;
+    double yMin;
+    double xMax;
+    double yMax;
+
+    public CohenSutherland(double xMin, double yMin, double xMax, double yMax) {
+        this.xMin = xMin;
+        this.yMin = yMin;
+        this.xMax = xMax;
+        this.yMax = yMax;
+    }
+
+    // Compute the region code for a point (x, y)
+    private int computeCode(double x, double y) {
+        int code = INSIDE;
+
+        if (x < xMin) // to the left of rectangle
+        {
+            code |= LEFT;
+        } else if (x > xMax) // to the right of rectangle
+        {
+            code |= RIGHT;
+        }
+        if (y < yMin) // below the rectangle
+        {
+            code |= BOTTOM;
+        } else if (y > yMax) // above the rectangle
+        {
+            code |= TOP;
+        }
+
+        return code;
+    }
+
+    // Cohen-Sutherland algorithm to return the clipped line
+    public Line cohenSutherlandClip(Line line) {
+        double x1 = line.start.x;
+        double y1 = line.start.y;
+        double x2 = line.end.x;
+        double y2 = line.end.y;
+
+        int code1 = computeCode(x1, y1);
+        int code2 = computeCode(x2, y2);
+        boolean accept = false;
+
+        while (true) {
+            if ((code1 == 0) && (code2 == 0)) {
+                // Both points are inside the rectangle
+                accept = true;
+                break;
+            } else if ((code1 & code2) != 0) {
+                // Both points are outside the rectangle in the same region
+                break;
+            } else {
+                // Some segment of the line is inside the rectangle
+                double x = 0;
+                double y = 0;
+
+                // Pick an endpoint that is outside the rectangle
+                int codeOut = (code1 != 0) ? code1 : code2;
+
+                // Find the intersection point using the line equation
+                if ((codeOut & TOP) != 0) {
+                    // Point is above the rectangle
+                    x = x1 + (x2 - x1) * (yMax - y1) / (y2 - y1);
+                    y = yMax;
+                } else if ((codeOut & BOTTOM) != 0) {
+                    // Point is below the rectangle
+                    x = x1 + (x2 - x1) * (yMin - y1) / (y2 - y1);
+                    y = yMin;
+                } else if ((codeOut & RIGHT) != 0) {
+                    // Point is to the right of the rectangle
+                    y = y1 + (y2 - y1) * (xMax - x1) / (x2 - x1);
+                    x = xMax;
+                } else if ((codeOut & LEFT) != 0) {
+                    // Point is to the left of the rectangle
+                    y = y1 + (y2 - y1) * (xMin - x1) / (x2 - x1);
+                    x = xMin;
+                }
+
+                // Replace the point outside the rectangle with the intersection point
+                if (codeOut == code1) {
+                    x1 = x;
+                    y1 = y;
+                    code1 = computeCode(x1, y1);
+                } else {
+                    x2 = x;
+                    y2 = y;
+                    code2 = computeCode(x2, y2);
+                }
+            }
+        }
+
+        if (accept) {
+            return new Line(new Point(x1, y1), new Point(x2, y2));
+        } else {
+
+            return null; // The line is fully rejected
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/lineclipping/LiangBarsky.java b/src/main/java/com/thealgorithms/lineclipping/LiangBarsky.java
new file mode 100644
index 00000000..723e2bb2
--- /dev/null
+++ b/src/main/java/com/thealgorithms/lineclipping/LiangBarsky.java
@@ -0,0 +1,93 @@
+package com.thealgorithms.lineclipping;
+
+import com.thealgorithms.lineclipping.utils.Line;
+import com.thealgorithms.lineclipping.utils.Point;
+
+/**
+ * @author shikarisohan
+ * @since 10/5/24
+ *
+ *  * The Liang-Barsky line clipping algorithm is an efficient algorithm for
+ *  * line clipping against a rectangular window. It is based on the parametric
+ *  * equation of a line and checks the intersections of the line with the
+ *  * window boundaries. This algorithm calculates the intersection points,
+ *  * if any, and returns the clipped line that lies inside the window.
+ *  *
+ *  * Reference:
+ *  * https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm
+ *
+ * Clipping window boundaries are defined as (xMin, yMin) and (xMax, yMax).
+ * The algorithm computes the clipped line segment if it's partially or
+ * fully inside the clipping window.
+ */
+public class LiangBarsky {
+
+    // Define the clipping window
+    double xMin;
+    double xMax;
+    double yMin;
+    double yMax;
+
+    public LiangBarsky(double xMin, double yMin, double xMax, double yMax) {
+        this.xMin = xMin;
+        this.yMin = yMin;
+        this.xMax = xMax;
+        this.yMax = yMax;
+    }
+
+    // Liang-Barsky algorithm to return the clipped line
+    public Line liangBarskyClip(Line line) {
+        double dx = line.end.x - line.start.x;
+        double dy = line.end.y - line.start.y;
+
+        double[] p = {-dx, dx, -dy, dy};
+        double[] q = {line.start.x - xMin, xMax - line.start.x, line.start.y - yMin, yMax - line.start.y};
+
+        double[] resultT = clipLine(p, q);
+
+        if (resultT == null) {
+            return null; // Line is outside the clipping window
+        }
+
+        return calculateClippedLine(line, resultT[0], resultT[1], dx, dy);
+    }
+
+    // clip the line by adjusting t0 and t1 for each edge
+    private double[] clipLine(double[] p, double[] q) {
+        double t0 = 0.0;
+        double t1 = 1.0;
+
+        for (int i = 0; i < 4; i++) {
+            double t = q[i] / p[i];
+            if (p[i] == 0 && q[i] < 0) {
+                return null; // Line is outside the boundary
+            } else if (p[i] < 0) {
+                if (t > t1) {
+                    return null;
+                } // Line is outside
+                if (t > t0) {
+                    t0 = t;
+                } // Update t0
+            } else if (p[i] > 0) {
+                if (t < t0) {
+                    return null;
+                } // Line is outside
+                if (t < t1) {
+                    t1 = t;
+                } // Update t1
+            }
+        }
+
+        return new double[] {t0, t1}; // Return valid t0 and t1
+    }
+
+    // calculate the clipped line based on t0 and t1
+    private Line calculateClippedLine(Line line, double t0, double t1, double dx, double dy) {
+        double clippedX1 = line.start.x + t0 * dx;
+        double clippedY1 = line.start.y + t0 * dy;
+        double clippedX2 = line.start.x + t1 * dx;
+        double clippedY2 = line.start.y + t1 * dy;
+
+        return new Line(new Point(clippedX1, clippedY1), new Point(clippedX2, clippedY2));
+    }
+}
diff --git a/src/main/java/com/thealgorithms/lineclipping/utils/Line.java b/src/main/java/com/thealgorithms/lineclipping/utils/Line.java
new file mode 100644
index 00000000..56cd52e3
--- /dev/null
+++ b/src/main/java/com/thealgorithms/lineclipping/utils/Line.java
@@ -0,0 +1,43 @@
+package com.thealgorithms.lineclipping.utils;
+
+import java.util.Objects;
+
+/**
+ * @author moksedursohan
+ * @since 10/4/24
+ */
+public class Line {
+
+    public Point start;
+    public Point end;
+
+    public Line() {
+    }
+
+    public Line(Point start, Point end) {
+        this.start = start;
+        this.end = end;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof Line line)) {
+            return false;
+        }
+
+        return Objects.equals(start, line.start) && Objects.equals(end, line.end);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(start, end);
+    }
+
+    @Override
+    public String toString() {
+        return "Line from " + start + " to " + end;
+    }
+}
diff --git a/src/main/java/com/thealgorithms/lineclipping/utils/Point.java b/src/main/java/com/thealgorithms/lineclipping/utils/Point.java
new file mode 100644
index 00000000..7ef58c78
--- /dev/null
+++ b/src/main/java/com/thealgorithms/lineclipping/utils/Point.java
@@ -0,0 +1,43 @@
+package com.thealgorithms.lineclipping.utils;
+
+import java.util.Objects;
+
+/**
+ * @author moksedursohan
+ * @since 10/4/24
+ */
+public class Point {
+
+    public double x;
+    public double y;
+
+    public Point() {
+    }
+
+    public Point(double x, double y) {
+        this.x = x;
+        this.y = y;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof Point point)) {
+            return false;
+        }
+
+        return Double.compare(x, point.x) == 0 && Double.compare(y, point.y) == 0;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(x, y);
+    }
+
+    @Override
+    public String toString() {
+        return "(" + x + ", " + y + ")";
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/lineclipping/CohenSutherlandTest.java b/src/test/java/com/thealgorithms/lineclipping/CohenSutherlandTest.java
new file mode 100644
index 00000000..064f71a1
--- /dev/null
+++ b/src/test/java/com/thealgorithms/lineclipping/CohenSutherlandTest.java
@@ -0,0 +1,81 @@
+package com.thealgorithms.lineclipping;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import com.thealgorithms.lineclipping.utils.Line;
+import com.thealgorithms.lineclipping.utils.Point;
+import org.junit.jupiter.api.Test;
+
+/**
+ * @author shikarisohan
+ * @since 10/4/24
+ */
+class CohenSutherlandTest {
+
+    // Define the clipping window (1.0, 1.0) to (10.0, 10.0)
+    CohenSutherland cs = new CohenSutherland(1.0, 1.0, 10.0, 10.0);
+
+    @Test
+    void testLineCompletelyInside() {
+        // Line fully inside the clipping window
+        Line line = new Line(new Point(2.0, 2.0), new Point(8.0, 8.0));
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(line, clippedLine, "Line inside the window should remain unchanged.");
+    }
+
+    @Test
+    void testLineCompletelyOutside() {
+        // Line completely outside and above the clipping window
+        Line line = new Line(new Point(11.0, 12.0), new Point(15.0, 18.0));
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNull(clippedLine, "Line should be null because it's completely outside.");
+    }
+
+    @Test
+    void testLinePartiallyInside() {
+        // Line partially inside the clipping window
+        Line line = new Line(new Point(5.0, 5.0), new Point(12.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(5.0, 5.0), new Point(10.0, 10.0)); // Clipped at (10, 10)
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Line should be clipped correctly.");
+    }
+
+    @Test
+    void testLineOnBoundary() {
+        // Line exactly on the boundary of the clipping window
+        Line line = new Line(new Point(1.0, 5.0), new Point(10.0, 5.0));
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(line, clippedLine, "Line on the boundary should remain unchanged.");
+    }
+
+    @Test
+    void testDiagonalLineThroughClippingWindow() {
+        // Diagonal line crossing from outside to outside through the window
+        Line line = new Line(new Point(0.0, 0.0), new Point(12.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(1.0, 1.0), new Point(10.0, 10.0)); // Clipped at both boundaries
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Diagonal line should be clipped correctly.");
+    }
+
+    @Test
+    void testVerticalLineClipping() {
+        // Vertical line crossing the top and bottom of the clipping window
+        Line line = new Line(new Point(5.0, 0.0), new Point(5.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(5.0, 1.0), new Point(5.0, 10.0)); // Clipped at yMin and yMax
+        Line clippedLine = cs.cohenSutherlandClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Vertical line should be clipped correctly.");
+    }
+}
diff --git a/src/test/java/com/thealgorithms/lineclipping/LiangBarskyTest.java b/src/test/java/com/thealgorithms/lineclipping/LiangBarskyTest.java
new file mode 100644
index 00000000..1c48cd10
--- /dev/null
+++ b/src/test/java/com/thealgorithms/lineclipping/LiangBarskyTest.java
@@ -0,0 +1,65 @@
+package com.thealgorithms.lineclipping;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import com.thealgorithms.lineclipping.utils.Line;
+import com.thealgorithms.lineclipping.utils.Point;
+import org.junit.jupiter.api.Test;
+
+/**
+ * @author shikarisohan
+ * @since 10/5/24
+ */
+class LiangBarskyTest {
+
+    LiangBarsky lb = new LiangBarsky(1.0, 1.0, 10.0, 10.0);
+
+    @Test
+    void testLineCompletelyInside() {
+        Line line = new Line(new Point(2.0, 2.0), new Point(8.0, 8.0));
+        Line clippedLine = lb.liangBarskyClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(line, clippedLine, "Line inside the window should remain unchanged.");
+    }
+
+    @Test
+    void testLineCompletelyOutside() {
+        Line line = new Line(new Point(12.0, 12.0), new Point(15.0, 18.0));
+        Line clippedLine = lb.liangBarskyClip(line);
+
+        assertNull(clippedLine, "Line should be null because it's completely outside.");
+    }
+
+    @Test
+    void testLinePartiallyInside() {
+        Line line = new Line(new Point(5.0, 5.0), new Point(12.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(5.0, 5.0), new Point(10.0, 10.0)); // Clipped at (10, 10)
+        Line clippedLine = lb.liangBarskyClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Line should be clipped correctly.");
+    }
+
+    @Test
+    void testDiagonalLineThroughClippingWindow() {
+        Line line = new Line(new Point(0.0, 0.0), new Point(12.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(1.0, 1.0), new Point(10.0, 10.0)); // Clipped at both boundaries
+        Line clippedLine = lb.liangBarskyClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Diagonal line should be clipped correctly.");
+    }
+
+    @Test
+    void testVerticalLineClipping() {
+        Line line = new Line(new Point(5.0, 0.0), new Point(5.0, 12.0));
+        Line expectedClippedLine = new Line(new Point(5.0, 1.0), new Point(5.0, 10.0)); // Clipped at yMin and yMax
+        Line clippedLine = lb.liangBarskyClip(line);
+
+        assertNotNull(clippedLine, "Line should not be null.");
+        assertEquals(expectedClippedLine, clippedLine, "Vertical line should be clipped correctly.");
+    }
+}