I am running a Computer Simulation where 2 Shapes are moving towards each other and will eventually overlap. I want to calculate the overlapping Area of the shapes - in this example a Circle and a Square in a $2$-Dimensional Room.
Let's describe the Circle as $(x_r, y_r, r)$ and the square as $(x_s, y_s, w, h)$.
Unfortunately I don't find the hint that shows me how to start approaching this problem. How do I start solving this problem?
Hint:
This is a pretty complex problem as there are many possible cases, but you can address it in a manageable way by the sweepline approach.
Draw horizontals by the square corners and by the N and S pole of the circle. The two shapes delimit line segments on these horizontals, and finding the intersection of two segments is trivial. When you go down from one line to the next, if the endpoints switch position, you have an intersection between the circle and the square outlines.
Scanning all horizontals in turn, you can follow the outline of the intersection shape, and as you go you describe curvilinear trapezoids (the oblique sides are circular arcs). Now it "suffices" to accumulate the areas of these trapezoids, using the standard formula, corrected with the areas of circular segments.
Warning:
The criterion "if the endpoints switch position" is not sufficient. You can very well have a large arc which is intersected twice by a vertical side, so that the endpoints switch position twice. So it is safer to write a test that explicitly looks for intersections between an arc and a vertical line in the current vertical span.