Total circles area

Total circles area is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given some partially overlapping circles on the plane, compute and show the total area covered by them, with four or six (or a little more) decimal digits of precision. The area covered by two or more disks needs to be counted only once.

One point of this Task is also to compare and discuss the relative merits of various solution strategies, their performance, precision and simplicity.

To allow a better comparison of the different implementations, solve the problem with this standard dataset, each line contains the x and y coordinates of the centers of the disks and their radii (11 disks are fully contained inside other disks):

      xc             yc        radius
 1.6417233788  1.6121789534 0.0848270516
-1.4944608174  1.2077959613 1.1039549836
 0.6110294452 -0.6907087527 0.9089162485
 0.3844862411  0.2923344616 0.2375743054
-0.2495892950 -0.3832854473 1.0845181219
 1.7813504266  1.6178237031 0.8162655711
-0.1985249206 -0.8343333301 0.0538864941
-1.7011985145 -0.1263820964 0.4776976918
-0.4319462812  1.4104420482 0.7886291537
 0.2178372997 -0.9499557344 0.0357871187
-0.6294854565 -1.3078893852 0.7653357688
 1.7952608455  0.6281269104 0.2727652452
 1.4168575317  1.0683357171 1.1016025378
 1.4637371396  0.9463877418 1.1846214562
-0.5263668798  1.7315156631 1.4428514068
-1.2197352481  0.9144146579 1.0727263474
-0.1389358881  0.1092805780 0.7350208828
 1.5293954595  0.0030278255 1.2472867347
-0.5258728625  1.3782633069 1.3495508831
-0.1403562064  0.2437382535 1.3804956588
 0.8055826339 -0.0482092025 0.3327165165
-0.6311979224  0.7184578971 0.2491045282
 1.4685857879 -0.8347049536 1.3670667538
-0.6855727502  1.6465021616 1.0593087096
 0.0152957411  0.0638919221 0.9771215985

According to one algorithm, the approximate solution is 21.5650366.

Beside solving the standard dataset, optionally solve a larger random dataset.

See also: http://www.reddit.com/r/dailyprogrammer/comments/zff9o/9062012_challenge_96_difficult_water_droplets/

Python

<lang python>from collections import namedtuple

standard_data = """\

1.6417233788  1.6121789534 0.0848270516

-1.4944608174 1.2077959613 1.1039549836

0.6110294452 -0.6907087527 0.9089162485
0.3844862411  0.2923344616 0.2375743054

-0.2495892950 -0.3832854473 1.0845181219

1.7813504266  1.6178237031 0.8162655711

-0.1985249206 -0.8343333301 0.0538864941 -1.7011985145 -0.1263820964 0.4776976918 -0.4319462812 1.4104420482 0.7886291537

0.2178372997 -0.9499557344 0.0357871187

-0.6294854565 -1.3078893852 0.7653357688

1.7952608455  0.6281269104 0.2727652452
1.4168575317  1.0683357171 1.1016025378
1.4637371396  0.9463877418 1.1846214562

-0.5263668798 1.7315156631 1.4428514068 -1.2197352481 0.9144146579 1.0727263474 -0.1389358881 0.1092805780 0.7350208828

1.5293954595  0.0030278255 1.2472867347

-0.5258728625 1.3782633069 1.3495508831 -0.1403562064 0.2437382535 1.3804956588

0.8055826339 -0.0482092025 0.3327165165

-0.6311979224 0.7184578971 0.2491045282

1.4685857879 -0.8347049536 1.3670667538

-0.6855727502 1.6465021616 1.0593087096

0.0152957411  0.0638919221 0.9771215985""".splitlines()

Circle = namedtuple("Circle", "x y r") circles = [Circle(*map(float, r.split())) for r in standard_data]

1. compute the bounding box of the circles

x_min = min(c.x - c.r for c in circles) x_max = max(c.x + c.r for c in circles) y_min = min(c.y - c.r for c in circles) y_max = max(c.y + c.r for c in circles)

box_side = 500

dx = (x_max - x_min) / box_side dy = (y_max - y_min) / box_side

count = 0

for r in xrange(box_side):

   y = y_min + r * dy
   for c in xrange(box_side):
       x = x_min + c * dx
       for circle in circles:
           if (x - circle.x)**2 + (y - circle.y)**2 <= (circle.r ** 2):
               count += 1
               break

print "Approximated area:", count * dx * dy</lang>

Output:

Approximated area: 21.561559772