Total circles area: Difference between revisions

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):

<pre>

</pre>

 

 

 

* http://stackoverflow.com/a/1667789/10562

<br><br>

 

=={{header|C}}==

===Montecarlo Sampling===

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)

===Scanline Method===

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}}==

===Scanline Method===

{{trans|C}}

 

alias Fp = real;

nSlicesX *= 2;

}

{{out}}

<pre>Input Circles: 25

{{trans|Haskell}}

This version is not fully idiomatic D, it retains some of the style of the Haskell version.

 

struct Vec { double x, y; }

 

writefln("Area: %1.13f", circles.circlesArea);

{{out}}

<pre>Area: 21.5650366038564</pre>

The run-time is minimal (0.03 seconds or less).

 

=={{header|EchoLisp}}==

Circles included in circles are discarded, and the circles are sorted : largest radius first. The circles bounding box is computed and divided into nxn rectangular tiles of size ds = dx * dy . Surfaces of tiles which are entirely included in a circle are added. Remaining tiles are divided into four smaller tiles, and the process is repeated : recursive call of procedure '''S''' , until ds < s-precision. To optimize things, a first pass - procedure '''S0''' - is performed, which assigns a list of candidates intersecting circles to each tile. This is quite effective, since the mean number of candidates circles for a given tile is 1.008 for n = 800.

 

(lib 'math)

(define (make-circle x0 y0 r)

(// ds 2))

)))

{{out}}

<pre>

→ 21.56503655935408

</pre>

=={{header|Go}}==

This is very memory inefficient and as written will not run on a 32 bit architecture (due mostly to the required size of the "unknown" Rectangle channel buffer to get even a few decimal places). It may be interesting anyway as an example of using channels with Go to split the work among several go routines (and processor cores).

 

import (

fmt.Printf("Area = %v±%v\n", avg, rng)

fmt.Printf("Area ≈ %.*f\n", 5, avg)

{{out}}

<pre>Starting with 25 circles.

===Grid Sampling Version===

{{trans|Python}}

 

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

 

main = putStrLn $ "Approximated area: " ++

{{out}}

<pre>Approximated area: 21.564955642878786</pre>

===Analytical Solution===

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)

Circle ( 0.0152957411) ( 0.0638919221) 0.9771215985]

 

{{out}}

21.5650366038564

===Uniform Grid===

We're missing an error estimate. Because it happened to be fairly accurate isn't proof that it's good. Runtime is 16 seconds on a Lenovo T500 with plenty of memory and connected to the power grid.

 

 

FRACTION*AREA

 

 

=={{header|Java}}==

depth limit is reached.

 

 

/*

System.out.println("Error is " + Math.abs(21.56503660 - ans));

}

 

 

Simple grid algorithm. Borrows the xmin/xmax idea from the Python version. This algorithm is fairly slow.

 

 

xc = [1.6417233788, -1.4944608174, 0.6110294452, 0.3844862411, -0.2495892950, 1.7813504266,

inside = 0

# For every point in my grid.

end

boxarea = (xmax - xmin) * (ymax - ymin)

end

 

 

=={{header|Kotlin}}==

===Grid Sampling Version===

{{trans|Python}}

 

class Circle(val x: Double, val y: Double, val r: Double)

println("Approximate area = ${count * dx * dy}")

}

 

{{out}}

===Scanline Version===

{{trans|Python}}

 

class Point(val x: Double, val y: Double)

val p = 1e-6

println("Approximate area = ${areaScan(p)}")

 

{{out}}

</pre>

 

Simple solution needs Mathematica 10:

-1.4944608174 1.2077959613 1.1039549836

0.6110294452 -0.6907087527 0.9089162485

 

toDisk[{x_, y_, r_}] := Disk[{x, y}, r];

 

Returns 21.5650370663759

 

If one assumes that the input data is exact (all omitted digits are zero) then the exact answer can be derived by changing the definition of toDisk in the above code to

The first 100 digits of the decimal expansion of the result are 21.56503660385639951717662965041005741103435843377395022310218015982077828980273399575555145558778509 so the solution given in the problem statement is incorrect after the first 16 decimal places (if we assume no bugs in the parts of Mathematica used here).

 

Simple grid algorithm. Borrows the xmin/xmax idea from the Python version. This algorithm is fairly slow.

 

 

tic

toc

 

 

=={{header|Nim}}==

===Grid Sampling Version===

{{trans|Python}}

 

type Circle = tuple[x, y, r: float]

( 0.0152957411, 0.0638919221, 0.9771215985)]

 

 

const boxSide = 500

var count = 0

 

let y = yMin + float(r) * dy

let x = xMin + float(c) * dx

for circle in circles:

inc count

break

 

 

 

 

 

 

 

 

}

}

 

 

{{out}}

 

=={{header|Python}}==

===Grid Sampling Version===

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

 

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

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

 

{{out}}

<pre>Approximated area: 21.561559772</pre>

 

===Scanline Conversion===

 

def area_scan(prec, circs):

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

 

===2D Van der Corput sequence===

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

* Wholly obscured circles removed,

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

from math import sqrt

from itertools import count

 

if __name__ == '__main__':

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

{{out}}

This requires the dmath module. Because of the usage of Decimal and trigonometric functions implemented in Python, this program takes few minutes to run.

{{trans|Haskell}}

from functools import partial

from itertools import repeat, imap, izip

print "Total Area:", circles_area(circles)

 

{{out}}

<pre>Total Area: 21.56503660385639895908422492887814801839</pre>

 

See: [[Example:Total_circles_area/Racket]]

 

=={{header|REXX}}==

These REXX programs use the grid sampling method.

===using all circles===

parse arg box dig . /*obtain optional argument from the CL.*/

if box=='' | box==',' then box= 500 /*Not specified? Then use the default.*/

/*stick a fork in it, we're done. */

say 'Using ' box " boxes (which have " box**2 ' points) and ' dig " decimal digits,"

{{out|output|text=&nbsp; when using the internal default input:}}

<pre>

===optimized===

This REXX version elides any circle that is completely contained in another circle.

<br>this reduces the computation time (for overlapping circles) by around 25%.

 

This version also has additional information displayed.

parse arg box dig . /*obtain optional argument from the CL.*/

if box=='' | box==',' then box= -500 /*Not specified? Then use the default.*/

if dig=='' | dig==',' then dig= 12 /* " " " " " " */

numeric digits dig /*have enough decimal digits for points*/

/* ══════x══════ ══════y══════ ═══radius═══ ══════x══════ ══════y══════ ═══radius═══*/

' 1.4685857879 -0.8347049536 1.3670667538 -0.6855727502 1.6465021616 1.0593087096',

' 0.0152957411 0.0638919221 0.9771215985 ' /*define circles with X, Y, and R.*/

if verbose then say 'There are' circles "circles." /*display the number of circles. */

parse var $ minX minY . 1 maxX maxY . /*assign minimum & maximum values.*/

 

end /*j*/

 

if @r.n>@r.m then parse value @x.n @y.n @r.n @x.m @y.m @r.m with,

@x.m @y.m @r.m @x.n @y.n @r.n

end /*m*/

 

@y.j-@r.j < @y.k-@r.k | @x.j+@r.j > @x.k+@r.k then iterate

if verbose then say 'Circle ' right(j,w) ' is contained in circle ' right(k,w)

end /*k*/

end /*j*/ /* [↑] elided overlapping circle.*/

if #in==0 then #in= 'no' /*use gooder English. (humor). */

if verbose then do; say; say #in " circles are fully contained within other circles.";end

say /*stick a fork in it, we're done. */

say 'Using ' box " boxes (which have " box**2 ' points) and ' dig " decimal digits,"

<pre>

There are 25 circles.

11 circles are fully contained within other circles.

 

Using 8000 boxes (which have 64000000 points) and 12 decimal digits,

the approximate area is: 21.5650301120

</pre>

 

=={{header|Ruby}}==

Common code

[ 1.6417233788, 1.6121789534, 0.0848270516],

[-1.4944608174, 1.2077959613, 1.1039549836],

circles.values_at(*select)

end

 

===Grid Sampling===

{{trans|Python}}

# compute the bounding box of the circles

xmin, xmax, ymin, ymax = minmax_circle(circles)

n *= 2

puts "#{Time.now - t0} sec"

 

{{out}}

===Scanline Method===

{{trans|Python}}

sect = ->(y) do

circles.select{|cx,cy,r| (y - cy).abs < r}.map do |cx,cy,r|

puts "%8.6f : %12.9f, %p sec" % [prec, area_scan(prec, circles), Time.now-t0]

prec /= 10

 

{{out}}

=={{header|Tcl}}==

This presents three techniques, a regular grid sampling, a pure Monte Carlo sampling, and a technique where there is a regular grid but then a vote of uniformly-distributed samples within each grid cell is taken to see if the cell is “in” or “out”.

1.6417233788 1.6121789534 0.0848270516

-1.4944608174 1.2077959613 1.1039549836

puts [format "estimated area (grid): %.4f" [sampleGrid $circles 500]]

puts [format "estimated area (monte carlo): %.2f" [sampleMC $circles 1000000]]

{{out}}

<pre>

</pre>

Note that the error on the Monte Carlo sampling is actually very high; the above run happened to deliver a figure closer to the real value than usual.

 

=={{header|zkl}}==

The circle data is stored in a file, just a copy/paste of the task data.

{{trans|Python}}

line.split().apply("toFloat") // L(x,y,r)

});

}

 

{{out}}

<pre>Approximated area: 21.5616</pre>