Repository: TheAlgorithms/Java
Pull request #5779 (2024-10-13 14:21:21)

feat: add bresenham's line drawing algorithm
<!--
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/5779?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 64.18%. Comparing base [(`9b52ac9`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/9b52ac9633c5f58087c2ad7ac8af4a44009cea2b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`11d7cc8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/11d7cc8a3e60cf5046a3b98dd2a4cea745e8b028?dropdown=coverage&el=desc&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    #5779      +/-   ##
============================================
+ Coverage     64.14%   64.18%   +0.04%     
- Complexity     4205     4213       +8     
============================================
  Files           587      588       +1     
  Lines         16390    16409      +19     
  Branches       3163     3168       +5     
============================================
+ Hits          10513    10532      +19     
  Misses         5448     5448              
  Partials        429      429              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5779?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).

saahil-mahato: @alxkm I have resolved the comments. Please review and let me know if anything is missing. Thanks

Patch:
diff --git a/src/main/java/com/thealgorithms/geometry/BresenhamLine.java b/src/main/java/com/thealgorithms/geometry/BresenhamLine.java
new file mode 100644
index 00000000..51d9930c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/geometry/BresenhamLine.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.geometry;
+
+import java.awt.Point;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * The {@code BresenhamLine} class implements the Bresenham's line algorithm,
+ * which is an efficient way to determine the points of a straight line
+ * between two given points in a 2D space.
+ *
+ * <p>This algorithm uses integer arithmetic to calculate the points,
+ * making it suitable for rasterization in computer graphics.</p>
+ *
+ * For more information, please visit {@link https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm}
+ */
+public final class BresenhamLine {
+
+    private BresenhamLine() {
+        // Private constructor to prevent instantiation.
+    }
+
+    /**
+     * Finds the list of points that form a straight line between two endpoints.
+     *
+     * @param x0 the x-coordinate of the starting point
+     * @param y0 the y-coordinate of the starting point
+     * @param x1 the x-coordinate of the ending point
+     * @param y1 the y-coordinate of the ending point
+     * @return a {@code List<Point>} containing all points on the line
+     */
+    public static List<Point> findLine(int x0, int y0, int x1, int y1) {
+        List<Point> line = new ArrayList<>();
+
+        // Calculate differences and steps for each axis
+        int dx = Math.abs(x1 - x0); // Change in x
+        int dy = Math.abs(y1 - y0); // Change in y
+        int sx = (x0 < x1) ? 1 : -1; // Step in x direction
+        int sy = (y0 < y1) ? 1 : -1; // Step in y direction
+        int err = dx - dy; // Initial error term
+
+        // Loop until we reach the endpoint
+        while (true) {
+            line.add(new Point(x0, y0)); // Add current point to the line
+
+            // Check if we've reached the endpoint
+            if (x0 == x1 && y0 == y1) {
+                break; // Exit loop if endpoint is reached
+            }
+
+            // Calculate error term doubled for decision making
+            final int e2 = err * 2;
+
+            // Adjust x coordinate if necessary
+            if (e2 > -dy) {
+                err -= dy; // Update error term
+                x0 += sx; // Move to next point in x direction
+            }
+
+            // Adjust y coordinate if necessary
+            if (e2 < dx) {
+                err += dx; // Update error term
+                y0 += sy; // Move to next point in y direction
+            }
+        }
+
+        return line; // Return the list of points forming the line
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/geometry/BresenhamLineTest.java b/src/test/java/com/thealgorithms/geometry/BresenhamLineTest.java
new file mode 100644
index 00000000..9df30849
--- /dev/null
+++ b/src/test/java/com/thealgorithms/geometry/BresenhamLineTest.java
@@ -0,0 +1,57 @@
+package com.thealgorithms.geometry;
+
+import java.awt.Point;
+import java.util.Collection;
+import java.util.List;
+import java.util.stream.Stream;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+/**
+ * The {@code BresenhamLineTest} class contains unit tests for the
+ * {@code BresenhamLine} class, specifically testing the
+ * {@code findLine} method.
+ *
+ * <p>This class uses parameterized tests to validate the output of
+ * Bresenham's line algorithm for various input points.</p>
+ */
+class BresenhamLineTest {
+
+    /**
+     * Provides test cases for the parameterized test.
+     *
+     * <p>Each test case includes starting coordinates, ending coordinates,
+     * and the expected collection of points that should be generated by the
+     * {@code findLine} method.</p>
+     *
+     * @return a stream of arguments containing test cases
+     */
+    static Stream<Arguments> linePointsProvider() {
+        return Stream.of(Arguments.of(0, 0, 5, 5, List.of(new Point(0, 0), new Point(1, 1), new Point(2, 2), new Point(3, 3), new Point(4, 4), new Point(5, 5))), Arguments.of(0, 0, 5, 0, List.of(new Point(0, 0), new Point(1, 0), new Point(2, 0), new Point(3, 0), new Point(4, 0), new Point(5, 0))),
+            Arguments.of(0, 0, 0, 5, List.of(new Point(0, 0), new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(0, 4), new Point(0, 5))), Arguments.of(-2, -2, -5, -5, List.of(new Point(-2, -2), new Point(-3, -3), new Point(-4, -4), new Point(-5, -5))),
+            Arguments.of(-1, -1, 2, 2, List.of(new Point(-1, -1), new Point(0, 0), new Point(1, 1), new Point(2, 2))), Arguments.of(2, -1, -1, -4, List.of(new Point(2, -1), new Point(1, -2), new Point(0, -3), new Point(-1, -4))));
+    }
+
+    /**
+     * Tests the {@code findLine} method of the {@code BresenhamLine} class.
+     *
+     * <p>This parameterized test runs multiple times with different sets of
+     * starting and ending coordinates to validate that the generated points
+     * match the expected output.</p>
+     *
+     * @param x0      the x-coordinate of the starting point
+     * @param y0      the y-coordinate of the starting point
+     * @param x1      the x-coordinate of the ending point
+     * @param y1      the y-coordinate of the ending point
+     * @param expected a collection of expected points that should form a line
+     */
+    @ParameterizedTest
+    @MethodSource("linePointsProvider")
+    void testFindLine(int x0, int y0, int x1, int y1, Collection<Point> expected) {
+        List<Point> actual = BresenhamLine.findLine(x0, y0, x1, y1);
+        Assertions.assertEquals(expected.size(), actual.size(), "The size of the points list should match.");
+        Assertions.assertTrue(expected.containsAll(actual) && actual.containsAll(expected), "The points generated should match the expected points.");
+    }
+}