rpthegreat's blog

Intersection of a polygon and circles
By rpthegreat, history, 7 years ago, In English

Hello,

I am trying to find intersection area of given circles and a polygon.

My approach is ,

  • Calculate all intersection points ( intersection of all circles with polygon and all remaining circles).
  • Keep track of all arcs encountered in above step.
  • Now remove all intersection points which are not inside polygon or does not follow the equation of any circle. Also remove the arcs that start or end with this particular intersection point.
  • Now all points which are left after above, will be my bounded region. So using formula of finding area of polygon, i
    will find area (say area1 ) and then i will calculate area which is left due to arc(say area2) .
  • return area1+area2

Is my approach correct or not?

I know that to implement this problem, I need to use floating point arithmetic. Which points are important while implementing this problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rpthegreat (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

There are a lot of cases for this and it becomes way more difficult than it looks to implement. I recommend just writing code to find the intersection area between a triangle and a circle. Once you have that working, it is possible to triangulate an arbitrary polygon in n*log(n) time, so you can just iterate through all of your triangles and sum the intersection area.

The hard part of doing that is finding the intersection between a triangle and a circle. That's a lot more difficult than you would think.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One possible solution is as follows : Break the polygon into some triangles as said by SecondThread. Now, take a large rectangle s.t. all circles and the triangle is inside it. Now, we'll recursively solve the problem by breaking the rectangles into 4 equal parts. If the rectangle is completely inside all the circles and the triangle, add the area of rectangle to the answer and stop. If the rectangle is outside any of the circles or the triangle, it won't affect the answer and you can stop. Otherwise break the rectangle into 4 equal parts and call recursively. When the size of the rectangle is very small, you can stop the recursion. The precision won't be too good, but otherwise it's not very difficult to implement. I have solved a problem which involves three circles and a triangle using this method. Here's the problem : link.

→ Reply