0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Well there is not much context though $\endgroup$ – ElHombre Jan 11 at 8:49
  • $\begingroup$ @ElHombre What's your motivation for asking this question? $\endgroup$ – Toby Mak Jan 11 at 9:45
  • $\begingroup$ I want to use a specific area size as a trigger. As the idea is that The objects and movements can be set randomly The mentioned Parameters are the only that I can determine for that moment. I think I could also get the Points of Intersection, that might make things easier, won't it? $\endgroup$ – ElHombre Jan 15 at 2:43
0
$\begingroup$

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.

enter image description here


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.

$\endgroup$
  • $\begingroup$ that sounds like a pretty good solution, it nearly covers all possibilities right? $\endgroup$ – ElHombre Jan 15 at 5:52
  • $\begingroup$ @ElHombre: if you take care, it covers all possibilities. I have added a warning. $\endgroup$ – Yves Daoust Jan 15 at 8:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.