Total circles area: Difference between revisions

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. This means keeping both slower and faster solutions for a language (like C) is welcome.

 

 

 

<pre>

 

 

 

 

 

=={{header|C}}==

This program uses a Montecarlo sampling. For this problem this is less efficient (converges more slowly) than a regular grid sampling, like in the Python entry.

#include <stdlib.h>

#include <math.h>

 

return 0;

{{out}}

<pre>21.4498 +/- 0.0370 (65536 samples)

21.5637 +/- 0.0003 (1073741824 samples)</pre>

 

This version performs about 5 million scanlines in about a second, result should be accurate to maybe 10 decimal points.

#include <string.h>

#include <stdlib.h>

 

return 0;

{{out}}

area = 21.5650366037 at 5637290 scanlines

 

=={{header|D}}==

This version converges much faster than both the ordered grid and Montecarlo sampling solutions.

 

struct Circle { Fp x, y, r; }

 

static bool isFullyInternal(in Circle c1, in Circle c2)

return false;

return (c1.x - c2.x) ^^ 2 + (c1.y - c2.y) ^^ 2 <

 

// Heuristics for performance: large radii first.

 

}

 

void main() {

(Fp.max, circles[]);

immutable Fp xMax = reduce!((acc, c) => max(acc, c.x + c.r))

 

auto yRanges = new YRange[circles.length];

 

Fp total = 0;

 

// Adapted from an idea by Cosmologicon.

immutable Fp x = p / nSlicesX;

size_t nPairs = 0;

// Look for the circles intersecting the current

// vertical secant:

immutable Fp d = c.r ^^ 2 - (c.x - x) ^^ 2;

if (d > 0)

// And keep only the intersection chords.

yRanges[0 .. nPairs].sort();

Fp y = -Fp.max;

if (y < r.y1) {

total += r.y1 - max(y, r.y0);

nSlicesX *= 2;

}

{{out}}

<pre>Input Circles: 25

N. vertical slices: 256000

Approximate area: 21.56503660593628004</pre>

 

=={{header|Haskell}}==

{{trans|Python}}

 

isInside :: Double -> Double -> Circle -> Bool

 

isInsideAny :: Double -> Double -> [Circle] -> Bool

 

approximatedArea :: [Circle] -> Int -> Double

c <- [0 .. box_side - 1],

isInsideAny (posx c) (posy r) circles]

 

circles :: [Circle]

 

main = putStrLn $ "Approximated area: " ++

{{out}}

<pre>Approximated area: 21.564955642878786</pre>

 

Breaking down circles to non-intersecting arcs and assemble zero winding paths, then calculate their areas. Pro: precision doesn't depend on a step size, so no need to wait longer for a more precise result; Con: probably not numerically stable in marginal situations, which can be catastrophic.

 

import Data.List (sort)

splitCircles :: [Circle] -> [Arc]

splitCircles cs = filter (not . inAnyCircle) arcs where

zipWith Arc (repeat c) $ zipWith Angle2 angs $ tail angs

 

inCircle :: (Vec, Circle) -> Circle -> Bool

 

inAnyCircle :: Arc -> Bool

 

 

makePaths :: [Arc] -> [[Arc]]

makePaths arcs = joinArcs [] arcs where

joinArcs a [] = [a]

joinArcs [] (x:xs) = joinArcs [x] xs

 

pathArea :: [Arc] -> Double

 

 

polylineArea :: [Vec] -> Double

 

 

Circle ( 0.0152957411) ( 0.0638919221) 0.9771215985]

 

{{out}}

21.5650366038564

 

 

 

 

 

 

 

 

 

}

}

 

 

}

 

}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

}

}

 

 

{{out}}

 

=={{header|Python}}==

This implements a regular grid sampling. For this problems this is more efficient than a Montecarlo sampling.

 

Circle = namedtuple("Circle", "x y r")

for c in xrange(box_side):

x = x_min + c * dx

 

print "Approximated area:", count * dx * dy

 

{{out}}

<pre>Approximated area: 21.561559772</pre>

 

 

def area_scan(prec, circs):

for (x0, x1) in sorted(sect((cx, cy, r), y)

for (cx, cy, r) in circs

if x1 <= right:

continue

print "@stepsize", p, "area = %.4f" % area_scan(p, circles)

 

[[File:Van_der_Corput_2D.png|200px|thumb|right]]

 

To aid in efficiency:

* Wholly obscured circles removed,

* And the square of the radius computed outside the main loops.

from math import sqrt

from itertools import count

x1, y1, r1 = c1

x2, y2, r2 = c2

 

def remove_covered_circles(circles):

'Takes circles in decreasing radius order. Removes those covered by others'

if eliminate: covered += [c1, eliminate]

for c in eliminate: circles.remove(c)

#pp(covered)

 

pcount += 1

px *= scalex; py *= scaley

if not pcount % 100000:

area = (inside/pcount) * scalex * scaley

 

if __name__ == '__main__':

The above is tested to work with Python v.2.7, Python3 and PyPy.

{{out}}

Points: 900000, Area estimate: 21.56596788610526

The value has settled to 21.5660</pre>