Total circles area: Difference between revisions

{{trans|Python}}

 

Float x, y, r

F (x, y, r)

count++

 

 

{{out}}

<pre>

Approximated area: 21.561559772

</pre>

 

{{trans|Python}}

 

@[ 1.6417233788 1.6121789534 0.0848270516]

@[neg 1.4944608174 1.2077959613 1.1039549836]

]

 

 

{{out}}

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

{{trans|Raku}} (more "based on" than a direct translation)

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

}

 

=={{header|Julia}}==

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

 

# Total circles area: https://rosettacode.org/wiki/Total_circles_area

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]

break

 

 

{{out}}

=={{header|Perl}}==

{{trans|Python}}

use warnings;

use feature 'say';

}

 

{{out}}

<pre>Approximated area: 21.561559772</pre>

=={{header|Phix}}==

{{trans|Python}}

{{out}}

<pre>

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

(formerly Perl 6)

This subdivides the outer rectangle repeatedly into subrectangles, and classifies them into wet, dry, or unknown. The knowns are summed to provide an inner bound and an outer bound, while the unknowns are further subdivided. The estimate is the average of the outer bound and the inner bound. Not the simplest algorithm, but converges fairly rapidly because it can treat large areas sparsely, saving the fine subdivisions for the circle boundaries. The number of unknown rectangles roughly doubles each pass, but the area of those unknowns is about half.

has Real $.x;

has Real $.y;

' diff: ', $diff.fmt('%9.6f'),

' error: ', ($diff - @unknowns * @unknowns[0].area).fmt('%e');

{{out}}

<pre>div: 2 unk: 4 est: 14.607153 wet: 0.000000 dry: 29.214306 diff: 29.214306 error: 0.000000e+000

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>

 

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.*/

say /*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 various number of boxes:}}

 

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

Analytical solution adapted from Haskell/Python.

Public pi As Double

Dim arclists() As Variant

circle_cross

make_path

<pre> 21,5650366038564 </pre>

 

{{libheader|Wren-math}}

Limited to 3000 boxes to finish in a reasonable time (about 25 seconds) with reasonable precision.

 

var Circle = Tuple.create("Circle", ["x", "y", "r"])

}

}

 

{{out}}

{{libheader|Wren-sort}}

Quicker (about 4.7 seconds) and more precise (limited to 5 d.p. but achieves 7) than the above version.

 

var Point = Tuple.create("Point", ["x", "y"])

for (p in points) {

if (p.y > right) {

right = p.y

}

var p = 1e-5

 

{{out}}

<pre>

Approximate area = 21.565036588498

</pre>

 

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>