jlcastrillon's blog

Area of Union of Circles
By jlcastrillon, 12 years ago, In English

Given n circles n <= 1000, how can I find the area of union of all this circles?

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I'm interested in that kind of problem too..! http://www.spoj.pl/problems/VCIRCLES/ is a small version but the big one is http://www.spoj.pl/problems/CIRU/

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

The main idea here is to make a vertical decomposition: draw a vertical line through every point of two circles' intersection and through two points with maximal and minimal x of every circle. Hence, you'll have O(N^2) vertical bands. In each band you have something like brackets (arcs) sequence so you can skip inner brackets. At last, you have some trapezoids with arc as side edges. Their area can be easily found in many ways.

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

There is a way, I think. But I never implemented it myself. You can try to build planar graph where vertices are points of circles intersections and edges are arcs. Then you can use standard algorithm for finding the area of faces of the planar graph. The only problem is how to sort edges, connected to one vertex. I am not sure about how do it correctly.

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

are there questions based on area similar to this on CodeForces?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

This problem can be solved with Green’s Theorem : Find the arcs which lies in the border of the union of area (in n^2lgn time with sweep), and apply the formula directly.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

This can be solved using Green's Theorem, with a complexity of n^2log(n). If you're not familiar with the Green's Theorem and want to know more, here is the video and notes from Khan Academy. But for the sake of our problem, I think my description will be enough. The general equation of Green's Theorem is

If I put L and M such that

then the RHS is simply the area of the Region R and can be obtained by solving the closed integral or LHS and this is exactly what we're going to do.

All unions can be broken into such disjoint sets of circles which intersect

So Integrating along the path in the anticlockwise gives us the Area of the region and integrating along the clockwise gives us negative of the Area. So

AreaOfUnion = (Integration along red arcs in anticlockwise direction + Integration along blue arcs in clockwise direction)

But the cool trick is if for each circle if we integrate the arcs which are not inside any other circle we get our required area i.e. we get integration in an anticlockwise direction along all red arcs and integration along all blue arcs along the clockwise direction. JOB DONE!!!

Even the cases when a circle doesn't intersect with any other is taken care of.

Here is the GitHub link to my C++ Code

→ Reply