Repository: TheAlgorithms/Java
Pull request #5870 (2024-10-16 06:59:48)

feat: add midpoint ellipse 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/5870?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 66.82%. Comparing base [(`2a518e3`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/2a518e3c9a44c4333c5ec9283895132264773afb?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`70e6f5f`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/70e6f5fcb80905a404d37b36c9fcc432175b18ef?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    #5870      +/-   ##
============================================
+ Coverage     66.70%   66.82%   +0.12%     
- Complexity     4482     4497      +15     
============================================
  Files           608      609       +1     
  Lines         16913    16961      +48     
  Branches       3264     3273       +9     
============================================
+ Hits          11282    11335      +53     
+ Misses         5182     5180       -2     
+ Partials        449      446       -3     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5870?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/geometry/MidpointEllipse.java b/src/main/java/com/thealgorithms/geometry/MidpointEllipse.java
new file mode 100644
index 00000000..fbd53c67
--- /dev/null
+++ b/src/main/java/com/thealgorithms/geometry/MidpointEllipse.java
@@ -0,0 +1,131 @@
+package com.thealgorithms.geometry;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+/**
+ * The MidpointEllipse class implements the Midpoint Ellipse Drawing Algorithm.
+ * This algorithm efficiently computes the points on an ellipse by dividing it into two regions
+ * and using decision parameters to determine the next point to plot.
+ */
+public final class MidpointEllipse {
+
+    private MidpointEllipse() {
+        // Private constructor to prevent instantiation
+    }
+
+    /**
+     * Draws an ellipse using the Midpoint Ellipse Algorithm.
+     *
+     * @param centerX the x-coordinate of the center of the ellipse
+     * @param centerY the y-coordinate of the center of the ellipse
+     * @param a the length of the semi-major axis (horizontal radius)
+     * @param b the length of the semi-minor axis (vertical radius)
+     * @return a list of points (represented as int arrays) that form the ellipse
+     */
+    public static List<int[]> drawEllipse(int centerX, int centerY, int a, int b) {
+        List<int[]> points = new ArrayList<>();
+
+        // Handle degenerate cases with early returns
+        if (a == 0 && b == 0) {
+            points.add(new int[] {centerX, centerY}); // Only the center point
+            return points;
+        }
+
+        if (a == 0) {
+            // Semi-major axis is zero, create a vertical line
+            for (int y = centerY - b; y <= centerY + b; y++) {
+                points.add(new int[] {centerX, y});
+            }
+            return points; // Early return
+        }
+
+        if (b == 0) {
+            // Semi-minor axis is zero, create a horizontal line
+            for (int x = centerX - a; x <= centerX + a; x++) {
+                points.add(new int[] {x, centerY});
+            }
+            return points; // Early return
+        }
+
+        // Normal case: Non-degenerate ellipse
+        computeEllipsePoints(points, centerX, centerY, a, b);
+
+        return points; // Return all calculated points of the ellipse
+    }
+
+    /**
+     * Computes points of a non-degenerate ellipse using the Midpoint Ellipse Algorithm.
+     *
+     * @param points    the list to which points will be added
+     * @param centerX  the x-coordinate of the center of the ellipse
+     * @param centerY  the y-coordinate of the center of the ellipse
+     * @param a        the length of the semi-major axis (horizontal radius)
+     * @param b        the length of the semi-minor axis (vertical radius)
+     */
+    private static void computeEllipsePoints(Collection<int[]> points, int centerX, int centerY, int a, int b) {
+        int x = 0; // Initial x-coordinate
+        int y = b; // Initial y-coordinate
+
+        // Region 1: Initial decision parameter
+        double d1 = (b * b) - (a * a * b) + (0.25 * a * a); // Decision variable for region 1
+        double dx = 2.0 * b * b * x; // Change in x
+        double dy = 2.0 * a * a * y; // Change in y
+
+        // Region 1: When the slope is less than 1
+        while (dx < dy) {
+            addEllipsePoints(points, centerX, centerY, x, y);
+
+            // Update decision parameter and variables
+            if (d1 < 0) {
+                x++;
+                dx += (2 * b * b); // Update x change
+                d1 += dx + (b * b); // Update decision parameter
+            } else {
+                x++;
+                y--;
+                dx += (2 * b * b); // Update x change
+                dy -= (2 * a * a); // Update y change
+                d1 += dx - dy + (b * b); // Update decision parameter
+            }
+        }
+
+        // Region 2: Initial decision parameter for the second region
+        double d2 = b * b * (x + 0.5) * (x + 0.5) + a * a * (y - 1) * (y - 1) - a * a * b * b;
+
+        // Region 2: When the slope is greater than or equal to 1
+        while (y >= 0) {
+            addEllipsePoints(points, centerX, centerY, x, y);
+
+            // Update decision parameter and variables
+            if (d2 > 0) {
+                y--;
+                dy -= (2 * a * a); // Update y change
+                d2 += (a * a) - dy; // Update decision parameter
+            } else {
+                y--;
+                x++;
+                dx += (2 * b * b); // Update x change
+                dy -= (2 * a * a); // Update y change
+                d2 += dx - dy + (a * a); // Update decision parameter
+            }
+        }
+    }
+
+    /**
+     * Adds points for all four quadrants of the ellipse based on symmetry.
+     *
+     * @param points    the list to which points will be added
+     * @param centerX  the x-coordinate of the center of the ellipse
+     * @param centerY  the y-coordinate of the center of the ellipse
+     * @param x        the x-coordinate relative to the center
+     * @param y        the y-coordinate relative to the center
+     */
+    private static void addEllipsePoints(Collection<int[]> points, int centerX, int centerY, int x, int y) {
+        points.add(new int[] {centerX + x, centerY + y});
+        points.add(new int[] {centerX - x, centerY + y});
+        points.add(new int[] {centerX + x, centerY - y});
+        points.add(new int[] {centerX - x, centerY - y});
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/geometry/MidpointEllipseTest.java b/src/test/java/com/thealgorithms/geometry/MidpointEllipseTest.java
new file mode 100644
index 00000000..9d03909c
--- /dev/null
+++ b/src/test/java/com/thealgorithms/geometry/MidpointEllipseTest.java
@@ -0,0 +1,99 @@
+package com.thealgorithms.geometry;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.List;
+import java.util.stream.Stream;
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+/**
+ * The {@code MidpointEllipseTest} class contains unit tests for the
+ * {@code MidpointEllipse} class, specifically testing the
+ * {@code drawEllipse} method.
+ *
+ * <p>This class uses parameterized tests to validate the output of
+ * Midpoint Ellipse algorithm for various input points.</p>
+ */
+class MidpointEllipseTest {
+
+    /**
+     * Provides test cases for the drawEllipse method.
+     * Each argument contains: centerX, centerY, a, b, and expected points.
+     *
+     * @return a stream of arguments for parameterized testing
+     */
+    static Stream<Arguments> ellipseTestProvider() {
+        return Stream.of(
+            Arguments.of(0, 0, 5, 3, new int[][] {{0, 3}, {0, 3}, {0, -3}, {0, -3}, {1, 3}, {-1, 3}, {1, -3}, {-1, -3}, {2, 3}, {-2, 3}, {2, -3}, {-2, -3}, {3, 2}, {-3, 2}, {3, -2}, {-3, -2}, {4, 2}, {-4, 2}, {4, -2}, {-4, -2}, {5, 1}, {-5, 1}, {5, -1}, {-5, -1}, {5, 0}, {-5, 0}, {5, 0}, {-5, 0}}),
+            Arguments.of(0, 0, 0, 5,
+                new int[][] {
+                    {0, -5}, {0, -4}, {0, -3}, {0, -2}, {0, -1}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5} // Only vertical line points and center
+                }),
+            Arguments.of(0, 0, 5, 0,
+                new int[][] {
+                    {-5, 0}, {-4, 0}, {-3, 0}, {-2, 0}, {-1, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0} // Only horizontal line points and center
+                }),
+            Arguments.of(0, 0, 0, 0,
+                new int[][] {
+                    {0, 0} // Only center point
+                }),
+            Arguments.of(0, 0, 4, 4,
+                new int[][] {
+                    {0, 4},
+                    {0, 4},
+                    {0, -4},
+                    {0, -4},
+                    {1, 4},
+                    {-1, 4},
+                    {1, -4},
+                    {-1, -4},
+                    {2, 3},
+                    {-2, 3},
+                    {2, -3},
+                    {-2, -3},
+                    {3, 3},
+                    {-3, 3},
+                    {3, -3},
+                    {-3, -3},
+                    {3, 2},
+                    {-3, 2},
+                    {3, -2},
+                    {-3, -2},
+                    {4, 1},
+                    {-4, 1},
+                    {4, -1},
+                    {-4, -1},
+                    {4, 0},
+                    {-4, 0},
+                    {4, 0},
+                    {-4, 0},
+                }));
+    }
+
+    /**
+     * Tests the drawEllipse method with various parameters.
+     *
+     * @param centerX       the x-coordinate of the center of the ellipse
+     * @param centerY       the y-coordinate of the center of the ellipse
+     * @param a             the length of the semi-major axis
+     * @param b             the length of the semi-minor axis
+     * @param expectedPoints the expected points forming the ellipse
+     */
+    @ParameterizedTest
+    @MethodSource("ellipseTestProvider")
+    @DisplayName("Test drawing ellipses with various parameters")
+    void testDrawEllipse(int centerX, int centerY, int a, int b, int[][] expectedPoints) {
+        List<int[]> points = MidpointEllipse.drawEllipse(centerX, centerY, a, b);
+
+        // Validate the number of points and the specific points
+        assertEquals(expectedPoints.length, points.size(), "Number of points should match expected.");
+
+        for (int i = 0; i < expectedPoints.length; i++) {
+            assertArrayEquals(expectedPoints[i], points.get(i), "Point mismatch at index " + i);
+        }
+    }
+}