Geometric Algorithms

Arguably, Geometric Algorithms (GA) stand side by side with Dynamic Programming (DP) as the hardest-to-grasp out of all the undergrad-level algorithms (clearly I'm not referring to advanced algorithms, for which GA and DP don't even scratch the surface in terms of difficulties).

The complexities manifest in different ways, though: DP seems to challenge you to think from a completely different perspective on how to solve the problem, whereas GA is not necessarily hard to come up with a solution, however it requires few things:

a) Brush up your high school geometry knowledge again
b) Pencil and paper
c) A formidable attention to details when coding

Seems like GA is more "mechanically laborious" whereas DP is more "intellectually challenging".

Example of GA: https://leetcode.com/problems/circle-and-rectangle-overlapping/

1401. Circle and Rectangle Overlapping

Medium

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0) 

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

• 1 <= radius <= 2000
• -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
• x1 < x2
• y1 < y2

Accepted

2,698

Submissions

7,163

There are basically three possibilities for the overlap to happen:
1) Either the rectangle is inside the circle
2) Or the circle is inside the rectangle
3) Or there is an intersection of the circumference with one of the edges of the rectangle

For each one you'll need to follow {a,b,c} above. Below is a manuscript of the sketch of me thinking about the solution. After fixing a mistake in my calculations, it worked. Code is below, cheers, ACC.

public class Solution
{
    public bool CheckOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2)
    {
        return RectangleInsideCircle(x1, y1, x2, y2, x_center, y_center, radius) ||
                CircleInsideRectangle(x1, y1, x2, y2, x_center, y_center) ||
                Overlap(x1, y1, x2, y2, x_center, y_center, radius);
    }

    private bool RectangleInsideCircle(int x1,
                                        int y1,
                                        int x2,
                                        int y2,
                                        int x_center,
                                        int y_center,
                                        int radius)
    {
        int[] xd = { x1, x1, x2, x2 };
        int[] yd = { y2, y1, y2, y1 };

        for (int i = 0; i < xd.Length; i++)
            if ((xd[i] - x_center) * (xd[i] - x_center) + (yd[i] - y_center) * (yd[i] - y_center) <= radius * radius) return true;

        return false;
    }

    private bool CircleInsideRectangle(int x1,
                                        int y1,
                                        int x2,
                                        int y2,
                                        int x_center,
                                        int y_center)
    {
        if (x1 <= x_center &&
            x_center <= x2 &&
            y1 <= y_center &&
            y_center <= y2)
        {
            return true;
        }
        return false;
    }

    private bool Overlap(int x1,
                            int y1,
                            int x2,
                            int y2,
                            int x_center,
                            int y_center,
                            int radius)
    {
        double xa = 0;
        double xb = 0;
        double ya = 0;
        double yb = 0;

        //Horizontal
        xa = Math.Sqrt(radius * radius - (y1 - y_center) * (y1 - y_center)) + x_center;
        xb = -Math.Sqrt(radius * radius - (y1 - y_center) * (y1 - y_center)) + x_center;
        if ((x1 <= xa && xa <= x2) ||
            (x1 <= xb && xb <= x2))
        {
            return true;
        }
        xa = Math.Sqrt(radius * radius - (y2 - y_center) * (y2 - y_center)) + x_center;
        xb = -Math.Sqrt(radius * radius - (y2 - y_center) * (y2 - y_center)) + x_center;
        if ((x1 <= xa && xa <= x2) ||
            (x1 <= xb && xb <= x2))
        {
            return true;
        }

        //Vertical
        ya = Math.Sqrt(radius * radius - (x1 - x_center) * (x1 - x_center)) + y_center;
        yb = -Math.Sqrt(radius * radius - (x1 - x_center) * (x1 - x_center)) + y_center;
        if ((y1 <= ya && ya <= y2) ||
            (y1 <= yb && yb <= y2))
        {
            return true;
        }
        ya = Math.Sqrt(radius * radius - (x2 - x_center) * (x2 - x_center)) + y_center;
        yb = -Math.Sqrt(radius * radius - (x2 - x_center) * (x2 - x_center)) + y_center;
        if ((y1 <= ya && ya <= y2) ||
            (y1 <= yb && yb <= y2))
        {
            return true;
        }

        return false;
    }
}