Total circles area: Difference between revisions
Added Algol 68
(Added a note: assuming no bugs in the proprietary Mathematica implementation.) |
(Added Algol 68) |
||
(73 intermediate revisions by 27 users not shown) | |||
Line 1:
[[Category:Geometry]]
{{task}}
[[File:total_circles_area_full.png|300px|thumb|right|Example circles]]
[[File:total_circles_area_filtered.png|300px|thumb|right|Example circles filtered]]
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.
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>
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
</pre>
The result is 21.56503660... .
;Related task:
* [[Circles of given radius through two points]].
;See also:
* http://www.reddit.com/r/dailyprogrammer/comments/zff9o/9062012_challenge_96_difficult_water_droplets/
* http://stackoverflow.com/a/1667789/10562
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T Circle
Float x, y, r
F (x, y, r)
.x = x
.y = y
.r = r
V circles = [
Circle(1.6417233788, 1.6121789534, 0.0848270516),
Circle(-1.4944608174, 1.2077959613, 1.1039549836),
Circle(0.6110294452, -0.6907087527, 0.9089162485),
Circle(0.3844862411, 0.2923344616, 0.2375743054),
Circle(-0.2495892950, -0.3832854473, 1.0845181219),
Circle(1.7813504266, 1.6178237031, 0.8162655711),
Circle(-0.1985249206, -0.8343333301, 0.0538864941),
Circle(-1.7011985145, -0.1263820964, 0.4776976918),
Circle(-0.4319462812, 1.4104420482, 0.7886291537),
Circle(0.2178372997, -0.9499557344, 0.0357871187),
Circle(-0.6294854565, -1.3078893852, 0.7653357688),
Circle(1.7952608455, 0.6281269104, 0.2727652452),
Circle(1.4168575317, 1.0683357171, 1.1016025378),
Circle(1.4637371396, 0.9463877418, 1.1846214562),
Circle(-0.5263668798, 1.7315156631, 1.4428514068),
Circle(-1.2197352481, 0.9144146579, 1.0727263474),
Circle(-0.1389358881, 0.1092805780, 0.7350208828),
Circle(1.5293954595, 0.0030278255, 1.2472867347),
Circle(-0.5258728625, 1.3782633069, 1.3495508831),
Circle(-0.1403562064, 0.2437382535, 1.3804956588),
Circle(0.8055826339, -0.0482092025, 0.3327165165),
Circle(-0.6311979224, 0.7184578971, 0.2491045282),
Circle(1.4685857879, -0.8347049536, 1.3670667538),
Circle(-0.6855727502, 1.6465021616, 1.0593087096),
Circle(0.0152957411, 0.0638919221, 0.9771215985)]
V x_min = min(circles.map(c -> c.x - c.r))
V x_max = max(circles.map(c -> c.x + c.r))
V y_min = min(circles.map(c -> c.y - c.r))
V y_max = max(circles.map(c -> c.y + c.r))
V box_side = 500
V dx = (x_max - x_min) / box_side
V dy = (y_max - y_min) / box_side
V count = 0
L(r) 0 .< box_side
V y = y_min + r * dy
L(c) 0 .< box_side
V x = x_min + c * dx
I any(circles.map(circle -> (@x - circle.x) ^ 2 + (@y - circle.y) ^ 2 <= (circle.r ^ 2)))
count++
print(‘Approximated area: ’(count * dx * dy))</syntaxhighlight>
{{out}}
<pre>
Approximated area: 21.561559772
</pre>
=={{header|ALGOL 68}}==
{{Trans|Nim|which is a translation of Python}}
<syntaxhighlight lang="algol68">
BEGIN # caclulate an approximation to the total of some overlapping circles #
# translated from the Nim sample #
MODE CIRCLE = STRUCT( REAL x, y, r );
[]CIRCLE circles = ( ( 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 )
);
OP SQR = ( REAL x )REAL: x * x;
PRIO MIN = 5;
OP MIN = ( []CIRCLE rc, PROC(CIRCLE)REAL f )REAL:
IF LWB rc > UPB rc
THEN 0
ELSE REAL result := f( rc[ LWB rc ] );
FOR c pos FROM LWB rc + 1 TO UPB rc DO
REAL v = f( rc[ c pos ] );
IF v < result THEN result := v FI
OD;
result
FI # MIN # ;
PRIO MAX = 5;
OP MAX = ( []CIRCLE rc, PROC(CIRCLE)REAL f )REAL:
IF LWB rc > UPB rc
THEN 0
ELSE REAL result := f( rc[ LWB rc ] );
FOR c pos FROM LWB rc + 1 TO UPB rc DO
REAL v = f( rc[ c pos ] );
IF v > result THEN result := v FI
OD;
result
FI # MAX # ;
REAL x min = circles MIN ( ( CIRCLE it )REAL: x OF it - r OF it );
REAL x max = circles MAX ( ( CIRCLE it )REAL: x OF it + r OF it );
REAL y min = circles MIN ( ( CIRCLE it )REAL: y OF it - r OF it );
REAL y max = circles MAX ( ( CIRCLE it )REAL: y OF it + r OF it );
INT box side = 500;
REAL dx = ( x max - x min ) / box side;
REAL dy = ( y max - y min ) / box side;
INT count := 0;
FOR r FROM 0 TO box side - 1 DO
REAL y = y min + ( r * dy );
FOR c FROM 0 TO box side - 1 DO
REAL x = x min + ( c * dx );
BOOL xy in circle := FALSE;
FOR c pos FROM LWB circles TO UPB circles WHILE NOT xy in circle DO
CIRCLE curr circle = circles[ c pos ];
IF SQR ( x - x OF curr circle ) + SQR ( y - y OF curr circle ) <= SQR r OF curr circle THEN
count +:= 1;
xy in circle := TRUE
FI
OD
OD
OD;
print( ( "Approximated area: ", fixed( count * dx * dy, -16, 14 ), newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
Approximated area: 21.5615597720033
</pre>
=={{header|Arturo}}==
{{trans|Python}}
<syntaxhighlight lang="rebol">circles: @[
@[ 1.6417233788 1.6121789534 0.0848270516]
@[neg 1.4944608174 1.2077959613 1.1039549836]
@[ 0.6110294452 neg 0.6907087527 0.9089162485]
@[ 0.3844862411 0.2923344616 0.2375743054]
@[neg 0.2495892950 neg 0.3832854473 1.0845181219]
@[ 1.7813504266 1.6178237031 0.8162655711]
@[neg 0.1985249206 neg 0.8343333301 0.0538864941]
@[neg 1.7011985145 neg 0.1263820964 0.4776976918]
@[neg 0.4319462812 1.4104420482 0.7886291537]
@[ 0.2178372997 neg 0.9499557344 0.0357871187]
@[neg 0.6294854565 neg 1.3078893852 0.7653357688]
@[ 1.7952608455 0.6281269104 0.2727652452]
@[ 1.4168575317 1.0683357171 1.1016025378]
@[ 1.4637371396 0.9463877418 1.1846214562]
@[neg 0.5263668798 1.7315156631 1.4428514068]
@[neg 1.2197352481 0.9144146579 1.0727263474]
@[neg 0.1389358881 0.1092805780 0.7350208828]
@[ 1.5293954595 0.0030278255 1.2472867347]
@[neg 0.5258728625 1.3782633069 1.3495508831]
@[neg 0.1403562064 0.2437382535 1.3804956588]
@[ 0.8055826339 neg 0.0482092025 0.3327165165]
@[neg 0.6311979224 0.7184578971 0.2491045282]
@[ 1.4685857879 neg 0.8347049536 1.3670667538]
@[neg 0.6855727502 1.6465021616 1.0593087096]
@[ 0.0152957411 0.0638919221 0.9771215985]
]
xMin: min map circles 'c -> c\0 - c\2
xMax: max map circles 'c -> c\0 + c\2
yMin: min map circles 'c -> c\1 - c\2
yMax: max map circles 'c -> c\1 + c\2
boxSide: 500
dx: (xMax - xMin) / boxSide
dy: (yMax - yMin) / boxSide
count: 0
loop 0..dec boxSide 'r [
y: yMin + r * dy
loop 0..dec boxSide 'c [
x: xMin + c * dx
loop circles 'circle [
if (add (x - first circle)*(x - first circle) (y - circle\1)*(y - circle\1)) =< (last circle)*(last circle) [
count: count + 1
break
]
]
]
]
print ["Approximated area: " count * dx * dy]</syntaxhighlight>
{{out}}
<pre>Approximated area: 21.56155977200332</pre>
=={{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>
Line 146 ⟶ 375:
return 0;
}</
{{out}}
<pre>21.4498 +/- 0.0370 (65536 samples)
Line 166 ⟶ 395:
===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>
Line 272 ⟶ 501:
return 0;
}</
{{out}}
area = 21.5650366037 at 5637290 scanlines
=={{header|C#}}==
===Scanline Method===
{{works with| .NET 8}}
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main(string[] args)
{
const double precision = 0.000001;
Console.WriteLine($"Approximate area = {AreaScan(precision):F8}");
}
private static double AreaScan(double precision)
{
List<double> valuesY = new List<double>();
foreach (var circle in circles)
{
valuesY.Add(circle.CentreY + circle.Radius);
valuesY.Add(circle.CentreY - circle.Radius);
}
double min = valuesY.Min();
double max = valuesY.Max();
long minY = (long)Math.Floor(min / precision);
long maxY = (long)Math.Ceiling(max / precision);
double totalArea = 0.0;
for (long i = minY; i <= maxY; i++)
{
double y = i * precision;
double right = double.NegativeInfinity;
List<PairX> pairsX = new List<PairX>();
foreach (var circle in circles)
{
if (Math.Abs(y - circle.CentreY) < circle.Radius)
{
pairsX.Add(HorizontalSection(circle, y));
}
}
pairsX.Sort((one, two) => one.X1.CompareTo(two.X1));
foreach (var pairX in pairsX)
{
if (pairX.X2 > right)
{
totalArea += pairX.X2 - Math.Max(pairX.X1, right);
right = pairX.X2;
}
}
}
return totalArea * precision;
}
private static PairX HorizontalSection(Circle circle, double y)
{
double value = Math.Pow(circle.Radius, 2) - Math.Pow(y - circle.CentreY, 2);
double deltaX = Math.Sqrt(value);
return new PairX(circle.CentreX - deltaX, circle.CentreX + deltaX);
}
private record PairX(double X1, double X2);
private record Circle(double CentreX, double CentreY, double Radius);
private static readonly List<Circle> circles = new List<Circle>
{
new Circle(1.6417233788, 1.6121789534, 0.0848270516),
new Circle(-1.4944608174, 1.2077959613, 1.1039549836),
new Circle(0.6110294452, -0.6907087527, 0.9089162485),
new Circle(0.3844862411, 0.2923344616, 0.2375743054),
new Circle(-0.2495892950, -0.3832854473, 1.0845181219),
new Circle(1.7813504266, 1.6178237031, 0.8162655711),
new Circle(-0.1985249206, -0.8343333301, 0.0538864941),
new Circle(-1.7011985145, -0.1263820964, 0.4776976918),
new Circle(-0.4319462812, 1.4104420482, 0.7886291537),
new Circle(0.2178372997, -0.9499557344, 0.0357871187),
new Circle(-0.6294854565, -1.3078893852, 0.7653357688),
new Circle(1.7952608455, 0.6281269104, 0.2727652452),
new Circle(1.4168575317, 1.0683357171, 1.1016025378),
new Circle(1.4637371396, 0.9463877418, 1.1846214562),
new Circle(-0.5263668798, 1.7315156631, 1.4428514068),
new Circle(-1.2197352481, 0.9144146579, 1.0727263474),
new Circle(-0.1389358881, 0.1092805780, 0.7350208828),
new Circle(1.5293954595, 0.0030278255, 1.2472867347),
new Circle(-0.5258728625, 1.3782633069, 1.3495508831),
new Circle(-0.1403562064, 0.2437382535, 1.3804956588),
new Circle(0.8055826339, -0.0482092025, 0.3327165165),
new Circle(-0.6311979224, 0.7184578971, 0.2491045282),
new Circle(1.4685857879, -0.8347049536, 1.3670667538),
new Circle(-0.6855727502, 1.6465021616, 1.0593087096),
new Circle(0.0152957411, 0.0638919221, 0.9771215985)
};
}
</syntaxhighlight>
{{out}}
<pre>
Approximate area = 21.56503660
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cfloat>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
struct Pair_X {
double x1;
double x2;
bool operator <(const Pair_X& pair_x) const {
return x1 < pair_x.x1;
}
};
struct Circle {
double centre_x;
double centre_y;
double radius;
};
const std::vector<Circle> circles = {
Circle( 1.6417233788, 1.6121789534, 0.0848270516),
Circle(-1.4944608174, 1.2077959613, 1.1039549836),
Circle( 0.6110294452, -0.6907087527, 0.9089162485),
Circle( 0.3844862411, 0.2923344616, 0.2375743054),
Circle(-0.2495892950, -0.3832854473, 1.0845181219),
Circle( 1.7813504266, 1.6178237031, 0.8162655711),
Circle(-0.1985249206, -0.8343333301, 0.0538864941),
Circle(-1.7011985145, -0.1263820964, 0.4776976918),
Circle(-0.4319462812, 1.4104420482, 0.7886291537),
Circle( 0.2178372997, -0.9499557344, 0.0357871187),
Circle(-0.6294854565, -1.3078893852, 0.7653357688),
Circle( 1.7952608455, 0.6281269104, 0.2727652452),
Circle( 1.4168575317, 1.0683357171, 1.1016025378),
Circle( 1.4637371396, 0.9463877418, 1.1846214562),
Circle(-0.5263668798, 1.7315156631, 1.4428514068),
Circle(-1.2197352481, 0.9144146579, 1.0727263474),
Circle(-0.1389358881, 0.1092805780, 0.7350208828),
Circle( 1.5293954595, 0.0030278255, 1.2472867347),
Circle(-0.5258728625, 1.3782633069, 1.3495508831),
Circle(-0.1403562064, 0.2437382535, 1.3804956588),
Circle( 0.8055826339, -0.0482092025, 0.3327165165),
Circle(-0.6311979224, 0.7184578971, 0.2491045282),
Circle( 1.4685857879, -0.8347049536, 1.3670667538),
Circle(-0.6855727502, 1.6465021616, 1.0593087096),
Circle( 0.0152957411, 0.0638919221, 0.9771215985)
};
Pair_X horizontal_section(const Circle& circle, const double& y) {
const double value = circle.radius * circle.radius - ( y - circle.centre_y ) * ( y - circle.centre_y );
double delta_x = std::sqrt(value);
return Pair_X(circle.centre_x - delta_x, circle.centre_x + delta_x);
}
double area_scan(const double& precision) {
std::vector<double> y_values;
for ( const Circle& circle : circles ) {
y_values.emplace_back(circle.centre_y + circle.radius);
}
for ( const Circle& circle : circles ) {
y_values.emplace_back(circle.centre_y - circle.radius);
}
const double min = *min_element(y_values.begin(), y_values.end());
const double max = *max_element(y_values.begin(), y_values.end());
const int64_t min_y = std::floor(min / precision);
const int64_t max_y = std::ceil(max / precision);
double total_area = 0.0;
for ( int64_t i = min_y; i <= max_y; ++i ) {
double y = i * precision;
double right = -DBL_MAX;
std::vector<Pair_X> pairs_x;
for ( const Circle& circle : circles ) {
if ( std::fabs(y - circle.centre_y) < circle.radius ) {
pairs_x.emplace_back(horizontal_section(circle, y));
}
}
std::sort(pairs_x.begin(), pairs_x.end());
for ( const Pair_X& pair_x : pairs_x ) {
if ( pair_x.x2 > right ) {
total_area += pair_x.x2 - std::max(pair_x.x1, right);
right = pair_x.x2;
}
}
}
return total_area * precision;
}
int main() {
const double precision = 0.00001;
std::cout << "Approximate area = " << std::setprecision(9) << area_scan(precision);
}
</syntaxhighlight>
{{ out }}
<pre>
Approximate area = 21.5650366
</pre>
=={{header|D}}==
Line 280 ⟶ 723:
===Scanline Method===
{{trans|C}}
<
alias Fp = real;
Line 393 ⟶ 836:
nSlicesX *= 2;
}
}</
{{out}}
<pre>Input Circles: 25
Line 404 ⟶ 847:
{{trans|Haskell}}
This version is not fully idiomatic D, it retains some of the style of the Haskell version.
<
struct Vec { double x, y; }
Line 571 ⟶ 1,014:
writefln("Area: %1.13f", circles.circlesArea);
}</
{{out}}
<pre>Area: 21.5650366038564</pre>
The run-time is minimal (0.03 seconds or less).
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
type TCircle = record
X,Y: double;
R: double;
end;
const Circles: array [0..24] of TCircle =(
(X: 1.6417233788; Y: 1.6121789534; R: 0.0848270516),
(X: -1.4944608174; Y: 1.2077959613; R: 1.1039549836),
(X: 0.6110294452; Y: -0.6907087527; R: 0.9089162485),
(X: 0.3844862411; Y: 0.2923344616; R: 0.2375743054),
(X: -0.2495892950; Y: -0.3832854473; R: 1.0845181219),
(X: 1.7813504266; Y: 1.6178237031; R: 0.8162655711),
(X: -0.1985249206; Y: -0.8343333301; R: 0.0538864941),
(X: -1.7011985145; Y: -0.1263820964; R: 0.4776976918),
(X: -0.4319462812; Y: 1.4104420482; R: 0.7886291537),
(X: 0.2178372997; Y: -0.9499557344; R: 0.0357871187),
(X: -0.6294854565; Y: -1.3078893852; R: 0.7653357688),
(X: 1.7952608455; Y: 0.6281269104; R: 0.2727652452),
(X: 1.4168575317; Y: 1.0683357171; R: 1.1016025378),
(X: 1.4637371396; Y: 0.9463877418; R: 1.1846214562),
(X: -0.5263668798; Y: 1.7315156631; R: 1.4428514068),
(X: -1.2197352481; Y: 0.9144146579; R: 1.0727263474),
(X: -0.1389358881; Y: 0.1092805780; R: 0.7350208828),
(X: 1.5293954595; Y: 0.0030278255; R: 1.2472867347),
(X: -0.5258728625; Y: 1.3782633069; R: 1.3495508831),
(X: -0.1403562064; Y: 0.2437382535; R: 1.3804956588),
(X: 0.8055826339; Y: -0.0482092025; R: 0.3327165165),
(X: -0.6311979224; Y: 0.7184578971; R: 0.2491045282),
(X: 1.4685857879; Y: -0.8347049536; R: 1.3670667538),
(X: -0.6855727502; Y: 1.6465021616; R: 1.0593087096),
(X: 0.0152957411; Y: 0.0638919221; R: 0.9771215985)
);
procedure CalculateCircleArea(Memo: TMemo; BoxPoints: integer = 500);
var MinX,MinY,MaxX,MaxY,Area: double;
var X,Y,BoxScaleX,BoxScaleY: double;
var I,Row,Col,Count: integer;
var Circle: TCircle;
begin
{Get minimum and maximum size of all the circles}
MinX:=MaxDouble; MinY:=MaxDouble;
MaxX:=MinDouble; MaxY:=MinDouble;
for I:=0 to High(Circles) do
begin
Circle:=Circles[I];
MinX:=min(MinX,Circle.X - Circle.R);
MaxX:=max(MaxX,Circle.X + Circle.R);
MinY:=min(MinY,Circle.Y - Circle.R);
MaxY:=max(MaxY,Circle.Y + Circle.R);
end;
{Calculate scaling factor for X/Y dimension of box}
BoxScaleX:=(MaxX - MinX) / BoxPoints;
BoxScaleY:=(MaxY - MinY) / BoxPoints;
Count:=0;
{Iterate through all X/Y BoxPoints}
for Row:=0 to BoxPoints-1 do
begin
{Get scaled and offset Y pos}
Y:=MinY + Row * BoxScaleY;
for Col:=0 to BoxPoints-1 do
begin
{Get scaled and offset X pos}
X:=MinX + Col * BoxScaleX;
for I:=0 to High(Circles) do
begin
Circle:=Circles[I];
{Check to see if point is in circle}
if (sqr(X - Circle.X) + sqr(Y - Circle.Y)) <= (Sqr(Circle.R)) then
begin
Inc(Count);
{Only count one circle}
break;
end;
end;
end;
end;
{Calculate area from the box scale}
Area:=Count * BoxScaleX * BoxScaleY;
{Display it}
Memo.Lines.Add(Format('Side: %5d Points: %9.0n Area: %3.18f',[BoxPoints,BoxPoints*BoxPoints+0.0,Area]));
end;
procedure TotalCirclesArea(Memo: TMemo);
begin
CalculateCircleArea(Memo, 500);
CalculateCircleArea(Memo, 1000);
CalculateCircleArea(Memo, 1500);
CalculateCircleArea(Memo, 5000);
end;
</syntaxhighlight>
{{out}}
<pre>
Side: 500 Points: 250,000 Area: 21.5615597720033172
Side: 1,000 Points: 1,000,000 Area: 21.5638384878351026
Side: 5,000 Points: 25,000,000 Area: 21.5649556428787861
Side: 15,000 Points: 225,000,000 Area: 21.5650079689460341
Elapsed Time: 01:23.134 min
</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=easylang>
# with Montecarlo sampling
repeat
s$ = input
until s$ = ""
c[][] &= number strsplit s$ " "
.
# mark inner circles
for i to len c[][]
for j to len c[][]
if i <> j
dx = abs (c[i][1] - c[j][1])
dy = abs (c[i][2] - c[j][2])
d = sqrt (dx * dx + dy * dy)
if d + c[j][3] < c[i][3]
c[j][3] = 0
.
.
.
.
# find bounding box and remove marked circles
i = len c[][]
while i >= 1
if 0 = 1 and c[i][3] = 0
swap c[i][] c[len c[][]][]
len c[][] -1
else
maxx = higher (c[i][1] + c[i][3]) maxx
minx = lower (c[i][1] - c[i][3]) minx
maxy = higher (c[i][2] + c[i][3]) maxy
miny = lower (c[i][2] - c[i][3]) miny
c[i][3] = c[i][3] * c[i][3]
.
i -= 1
.
ntry = 10000000
print ntry & " samples ..."
for try to ntry
px = (maxx - minx) * randomf + minx
py = (maxy - miny) * randomf + miny
for i to len c[][]
dx = px - c[i][1]
dy = py - c[i][2]
if dx * dx + dy * dy <= c[i][3]
inside += 1
break 1
.
.
.
numfmt 4 0
print inside / ntry * (maxx - minx) * (maxy - miny)
#
input_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
</syntaxhighlight>
=={{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.
<syntaxhighlight lang="scheme">
(lib 'math)
(define (make-circle x0 y0 r)
(vector x0 y0 r ))
(define-syntax-id _.radius (_ 2))
(define-syntax-id _.x0 (_ 0))
(define-syntax-id _.y0 (_ 1))
;; to sort circles
(define (cmp-circles a b) (> a.radius b.radius))
(define (included? circle: a circles)
(for/or ((b circles))
#:continue (equal? a b)
(disk-in-disk? a b)))
;; eliminates, and sort
(define (sort-circles circles)
(list-sort cmp-circles
(filter (lambda(c) (not (included? c circles))) circles)))
(define circles (sort-circles
(list (make-circle 1.6417233788 1.6121789534 0.0848270516)
(make-circle -1.4944608174 1.2077959613 1.1039549836)
(make-circle 0.6110294452 -0.6907087527 0.9089162485)
(make-circle 0.3844862411 0.2923344616 0.2375743054)
(make-circle -0.2495892950 -0.3832854473 1.0845181219)
(make-circle 1.7813504266 1.6178237031 0.8162655711)
(make-circle -0.1985249206 -0.8343333301 0.0538864941)
(make-circle -1.7011985145 -0.1263820964 0.4776976918)
(make-circle -0.4319462812 1.4104420482 0.7886291537)
(make-circle 0.2178372997 -0.9499557344 0.0357871187)
(make-circle -0.6294854565 -1.3078893852 0.7653357688)
(make-circle 1.7952608455 0.6281269104 0.2727652452)
(make-circle 1.4168575317 1.0683357171 1.1016025378)
(make-circle 1.4637371396 0.9463877418 1.1846214562)
(make-circle -0.5263668798 1.7315156631 1.4428514068)
(make-circle -1.2197352481 0.9144146579 1.0727263474)
(make-circle -0.1389358881 0.1092805780 0.7350208828)
(make-circle 1.5293954595 0.0030278255 1.2472867347)
(make-circle -0.5258728625 1.3782633069 1.3495508831)
(make-circle -0.1403562064 0.2437382535 1.3804956588)
(make-circle 0.8055826339 -0.0482092025 0.3327165165)
(make-circle -0.6311979224 0.7184578971 0.2491045282)
(make-circle 1.4685857879 -0.8347049536 1.3670667538)
(make-circle -0.6855727502 1.6465021616 1.0593087096)
(make-circle 0.0152957411 0.0638919221 0.9771215985))))
;; bounding box
(define (enclosing-rect circles)
(define xmin (for/min ((c circles)) (- c.x0 c.radius)))
(define xmax (for/max ((c circles)) (+ c.x0 c.radius)))
(define ymin (for/min ((c circles)) (- c.y0 c.radius)))
(define ymax (for/max ((c circles)) (+ c.y0 c.radius)))
(vector xmin ymin (- xmax xmin) (- ymax ymin)))
;; Compute surface of entirely overlapped tiles
;; and assign candidates circles to other tiles.
;; cands is a vector nsteps x nsteps of circles lists indexed by (i,j)
(define (S0 circles rect steps into: cands)
(define dx (// (rect 2) steps)) ;; width / steps
(define dy (// (rect 3) steps)) ;; height / steps
(define ds (* dx dy)) ;; tile surface
(define dr (vector (- rect.x0 dx) (- rect.y0 dy) dx dy))
(define ijdx 0)
(for/sum ((i steps))
(vector+= dr 0 dx)
(vector-set! dr 1 (- rect.y0 dy))
(for/sum ((j steps))
(vector+= dr 1 dy)
(set! ijdx (+ i (* j steps)))
(for/sum ((c circles))
#:break (rect-in-disk? dr c) ;; enclosed ? add ds
=> (begin (vector-set! cands ijdx null) ds)
#:continue (not (rect-disk-intersect? dr c))
;; intersects ? add circle to candidates for this tile
(vector-set! cands ijdx (cons c (cands ijdx )))
0)
)))
(define ct 0)
;; return sum of surfaces of tiles which are not entirely overlapped
(define (S circles rect steps cands)
(++ ct)
(define dx (// (rect 2) steps))
(define dy (// (rect 3) steps))
(define ds (* dx dy))
(define dr (vector (- rect.x0 dx) (- rect.y0 dy) dx dy))
(define ijdx 0)
(for/sum ((i steps))
(vector+= dr 0 dx)
(vector-set! dr 1 (- (rect 1) dy))
(for/sum ((j steps))
(vector+= dr 1 dy)
(when (!null? cands) (set! circles (cands (+ i (* j steps)))))
#:continue (null? circles)
;; add surface
(or
(for/or ((c circles)) ;; enclosed ? add ds
#:break (rect-in-disk? dr c) => ds
#f )
(if ;; not intersecting? add 0
(for/or ((c circles))
(rect-disk-intersect? dr c)) #f 0)
;; intersecting ? recurse until precision
(when (> dx s-precision) (S circles dr 2 null))
;; no hope - add ds/2
(// ds 2))
)))
</syntaxhighlight>
{{out}}
<pre>
(length circles) → 14
(enclosing-rect circles) → #( -2.598415801 -2.2017717074 5.4340683427 5.3761387773)
(define nsteps 800)
(define cands (make-vector (* nsteps nsteps) null))
(define rect (enclosing-rect circles))
(define starter (S0 circles rect nsteps cands))
→ 21.479635555704785
(vector-length cands) → 640000
;; number of remaining tiles
(for/sum ((c cands)) (if (null? c) 0 1)) → 3670
;; number of candidates circles
(for/sum ((c cands)) (if (null? c) 0 (length c))) → 3701
;; "The result is 21.565036603856399517.. . "
(define s-precision 0.0001)
(define delta (S null rect nsteps cands))
→ 0.08540009897433079 ;; 466_928 calls to S
(+ starter delta) ;; 5 decimals
→ 21.565035654679114
(define s-precision 0.00001)
(define delta (S null rect nsteps cands))
→ 0.08540100364929355 ;; 3_761_385 calls, time *= 10
(+ starter delta) ;; 6 decimals
→ 21.56503655935408
</pre>
=={{header|FreeBASIC}}==
Just a quick and dirty grid sampling method, with some convergence acceleration at the end.
<syntaxhighlight lang="freebasic">#define dx 0.0001
'read in the data; I reordered them in descending order of radius
'This maximises our chance of being able to break early, saving run time,
'and we needn't bother finding out which circles are entirely inside others
data -0.5263668798,1.7315156631,1.4428514068
data -0.1403562064,0.2437382535,1.3804956588
data 1.4685857879,-0.8347049536,1.3670667538
data -0.5258728625,1.3782633069,1.3495508831
data 1.5293954595,0.0030278255,1.2472867347
data 1.4637371396,0.9463877418,1.1846214562
data -1.4944608174,1.2077959613,1.1039549836
data 1.4168575317,1.0683357171,1.1016025378
data -0.249589295,-0.3832854473,1.0845181219
data -1.2197352481,0.9144146579,1.0727263474
data -0.6855727502,1.6465021616,1.0593087096
data 0.0152957411,0.0638919221,0.9771215985
data 0.6110294452,-0.6907087527,0.9089162485
data 1.7813504266,1.6178237031,0.8162655711
data -0.4319462812,1.4104420482,0.7886291537
data -0.6294854565,-1.3078893852,0.7653357688
data -0.1389358881,0.109280578,0.7350208828
data -1.7011985145,-0.1263820964,0.4776976918
data 0.8055826339,-0.0482092025,0.3327165165
data 1.7952608455,0.6281269104,0.2727652452
data -0.6311979224,0.7184578971,0.2491045282
data 0.3844862411,0.2923344616,0.2375743054
data 1.6417233788,1.6121789534,0.0848270516
data -0.1985249206,-0.8343333301,0.0538864941
data 0.2178372997,-0.9499557344,0.0357871187
function dist(x0 as double, y0 as double, x1 as double, y1 as double) as double
'distance between two points in 2d space
return sqr( (x1-x0)^2 + (y1-y0)^2 )
end function
dim as double x(1 to 25), y(1 to 25), r(1 to 25), gx, gy, A0, A1, A2, A
dim as integer i, cx, cy
for i = 1 to 25
read x(i), y(i), r(i)
next i
for gx = -2.6 to 2.9 step dx 'sample points on a grid
cx += 1
for gy = -2.3 to 3.2 step dx
cy += 1
for i = 1 to 25
if dist(gx, gy, x(i), y(i)) <= r(i) then
'if our grid point is in the circle
A2 += dx^2 'add the area of a grid square
if cx mod 2 = 0 and cy mod 2 = 0 then A1 += 4*dx^2
if cx mod 4 = 0 and cy mod 4 = 0 then A0 += 16*dx^2
'also keep track of coarser grid areas of twice and four times the size
'You'll see why in a moment
exit for
end if
next i
next gy
next gx
'use Shanks method to refine our estimate of the area
A = (A0*A2-A1^2) / (A0 + A2 - 2*A1)
print A0, A1, A2, A</syntaxhighlight>
{{out}}
Shows the area calculated by progressively finer grid sizes, and a refined estimate calculated form those.
<pre>21.56502992281657 21.56503478240848 21.56503694212367 21.56503866963273</pre>
=={{header|Go}}==
{{trans|
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 (
Line 810 ⟶ 1,676:
fmt.Printf("Area = %v±%v\n", avg, rng)
fmt.Printf("Area ≈ %.*f\n", 5, avg)
}</
{{out}}
<pre>Starting with 25 circles.
Line 822 ⟶ 1,688:
===Grid Sampling Version===
{{trans|Python}}
<
isInside :: Double -> Double -> Circle -> Bool
Line 874 ⟶ 1,740:
main = putStrLn $ "Approximated area: " ++
(show $ approximatedArea circles 5000)</
{{out}}
<pre>Approximated area: 21.564955642878786</pre>
Line 880 ⟶ 1,746:
===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)
Line 1,048 ⟶ 1,914:
Circle ( 0.0152957411) ( 0.0638919221) 0.9771215985]
main = print $ circlesArea circles</
{{out}}
21.5650366038564
Line 1,065 ⟶ 1,931:
===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.
<
Line 1,139 ⟶ 2,005:
FRACTION*AREA
NB. result is 21.5645</
=={{header|
Solution using recursive subdivision of space into rectangles. Base cases of recursion are
when the rectangle is fully inside some circle, is fully outside all circles, or the maximum
depth limit is reached.
<syntaxhighlight lang="java">
public class TotalCirclesArea {
/*
* Rectangles are given as 4-element arrays [tx, ty, w, h].
* Circles are given as 3-element arrays [cx, cy, r].
private static double distSq(double x1, double y1, double x2, double y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
private static boolean rectangleFullyInsideCircle(double[] rect, double[] circ) {
double r2 = circ[2] * circ[2];
// Every corner point of rectangle must be inside the circle.
return distSq(rect[0], rect[1], circ[0], circ[1]) <= r2 &&
distSq(rect[0] + rect[2], rect[1], circ[0], circ[1]) <= r2 &&
distSq(rect[0], rect[1] - rect[3], circ[0], circ[1]) <= r2 &&
distSq(rect[0] + rect[2], rect[1] - rect[3], circ[0], circ[1]) <= r2;
}
private static boolean rectangleSurelyOutsideCircle(double[] rect, double[] circ) {
// Circle center point inside rectangle?
if(rect[0] <= circ[0] && circ[0] <= rect[0] + rect[2] &&
rect[1] - rect[3] <= circ[1] && circ[1] <= rect[1]) { return false; }
// Otherwise, check that each corner is at least (r + Max(w, h)) away from circle center.
double r2 = circ[2] + Math.max(rect[2], rect[3]);
r2 = r2 * r2;
return distSq(rect[0], rect[1], circ[0], circ[1]) >= r2 &&
distSq(rect[0] + rect[2], rect[1], circ[0], circ[1]) >= r2 &&
distSq(rect[0], rect[1] - rect[3], circ[0], circ[1]) >= r2 &&
distSq(rect[0] + rect[2], rect[1] - rect[3], circ[0], circ[1]) >= r2;
}
private static boolean[] surelyOutside;
private static double totalArea(double[] rect, double[][] circs, int d) {
// Check if we can get a quick certain answer.
int surelyOutsideCount = 0;
for(int i = 0; i < circs.length; i++) {
if(rectangleFullyInsideCircle(rect, circs[i])) { return rect[2] * rect[3]; }
if(rectangleSurelyOutsideCircle(rect, circs[i])) {
surelyOutside[i] = true;
surelyOutsideCount++;
}
else { surelyOutside[i] = false; }
}
// Is this rectangle surely outside all circles?
if(surelyOutsideCount == circs.length) { return 0; }
// Are we deep enough in the recursion?
if(d < 1) {
return rect[2] * rect[3] / 3; // Best guess for overlapping portion
}
// Throw out all circles that are surely outside this rectangle.
if(surelyOutsideCount > 0) {
double[][] newCircs = new double[circs.length - surelyOutsideCount][3];
int loc = 0;
for(int i = 0; i < circs.length; i++) {
if(!surelyOutside[i]) { newCircs[loc++] = circs[i]; }
}
circs = newCircs;
}
// Subdivide this rectangle recursively and add up the recursively computed areas.
double w = rect[2] / 2; // New width
double h = rect[3] / 2; // New height
double[][] pieces = {
{ rect[0], rect[1], w, h }, // NW
{ rect[0] + w, rect[1], w, h }, // NE
{ rect[0], rect[1] - h, w, h }, // SW
{ rect[0] + w, rect[1] - h, w, h } // SE
};
double total = 0;
for(double[] piece: pieces) { total += totalArea(piece, circs, d - 1); }
return total;
}
public static double totalArea(double[][] circs, int d) {
double maxx = Double.NEGATIVE_INFINITY;
double minx = Double.POSITIVE_INFINITY;
double maxy = Double.NEGATIVE_INFINITY;
double miny = Double.POSITIVE_INFINITY;
// Find the extremes of x and y for this set of circles.
for(double[] circ: circs) {
if(circ[0] + circ[2] > maxx) { maxx = circ[0] + circ[2]; }
if(circ[0] - circ[2] < minx) { minx = circ[0] - circ[2]; }
if(circ[1] + circ[2] > maxy) { maxy = circ[1] + circ[2]; }
if(circ[1] - circ[2] < miny) { miny = circ[1] - circ[2]; }
}
double[] rect = { minx, maxy, maxx - minx, maxy - miny };
surelyOutside = new boolean[circs.length];
return totalArea(rect, circs, d);
}
public static void main(String[] args) {
double[][] circs = {
{ 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 }
};
double ans = totalArea(circs, 24);
System.out.println("Approx. area is " + ans);
System.out.println("Error is " + Math.abs(21.56503660 - ans));
}
}</syntaxhighlight>
===Scanline Method===
Alternative example using the Scanline method.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class TotalCirclesArea {
public static void main(String[] args) {
final double precision = 0.000_001;
System.out.println(String.format("%s%.8f", "Approximate area = ", areaScan(precision)));
}
private static double areaScan(double precision) {
List<Double> valuesY = new ArrayList<Double>();
for ( Circle circle : circles ) {
valuesY.add(circle.centreY + circle.radius);
}
for ( Circle circle : circles ) {
valuesY.add(circle.centreY - circle.radius);
}
final double min = valuesY.stream().min(Double::compare).get();
final double max = valuesY.stream().max(Double::compare).get();
final long minY = (long) Math.floor(min / precision);
final long maxY = (long) Math.ceil(max / precision);
double totalArea = 0.0;
for ( long i = minY; i <= maxY; i++ ) {
final double y = i * precision;
double right = Double.NEGATIVE_INFINITY;
List<PairX> pairsX = new ArrayList<PairX>();
for ( Circle circle : circles ) {
if ( Math.abs(y - circle.centreY) < circle.radius ) {
pairsX.add(horizontalSection(circle, y));
}
}
Collections.sort(pairsX, (one, two) -> Double.compare(one.x1, two.x1) );
for ( PairX pairX : pairsX ) {
if ( pairX.x2 > right ) {
totalArea += pairX.x2 - Math.max(pairX.x1, right);
right = pairX.x2;
}
}
}
return totalArea * precision;
}
private static PairX horizontalSection(Circle circle, double y) {
final double value = circle.radius * circle.radius - ( y - circle.centreY ) * ( y - circle.centreY );
final double deltaX = Math.sqrt(value);
return new PairX(circle.centreX - deltaX, circle.centreX + deltaX);
}
private static record PairX(double x1, double x2) {}
private static record Circle(double centreX, double centreY, double radius) {}
private static final List<Circle> circles = List.of(
new Circle( 1.6417233788, 1.6121789534, 0.0848270516),
new Circle(-1.4944608174, 1.2077959613, 1.1039549836),
new Circle( 0.6110294452, -0.6907087527, 0.9089162485),
new Circle( 0.3844862411, 0.2923344616, 0.2375743054),
new Circle(-0.2495892950, -0.3832854473, 1.0845181219),
new Circle( 1.7813504266, 1.6178237031, 0.8162655711),
new Circle(-0.1985249206, -0.8343333301, 0.0538864941),
new Circle(-1.7011985145, -0.1263820964, 0.4776976918),
new Circle(-0.4319462812, 1.4104420482, 0.7886291537),
new Circle( 0.2178372997, -0.9499557344, 0.0357871187),
new Circle(-0.6294854565, -1.3078893852, 0.7653357688),
new Circle( 1.7952608455, 0.6281269104, 0.2727652452),
new Circle( 1.4168575317, 1.0683357171, 1.1016025378),
new Circle( 1.4637371396, 0.9463877418, 1.1846214562),
new Circle(-0.5263668798, 1.7315156631, 1.4428514068),
new Circle(-1.2197352481, 0.9144146579, 1.0727263474),
new Circle(-0.1389358881, 0.1092805780, 0.7350208828),
new Circle( 1.5293954595, 0.0030278255, 1.2472867347),
new Circle(-0.5258728625, 1.3782633069, 1.3495508831),
new Circle(-0.1403562064, 0.2437382535, 1.3804956588),
new Circle( 0.8055826339, -0.0482092025, 0.3327165165),
new Circle(-0.6311979224, 0.7184578971, 0.2491045282),
new Circle( 1.4685857879, -0.8347049536, 1.3670667538),
new Circle(-0.6855727502, 1.6465021616, 1.0593087096),
new Circle( 0.0152957411, 0.0638919221, 0.9771215985)
);
}
</syntaxhighlight>
{{ out }}
<pre>
Approximate area = 21.56503660
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
'''Adapted from [[#Wren|Wren]]'''
This entry uses the "scanline" method after winnowing based on containment.
To compute the common area, horizontal strips are used in the manner of Cavalieri.
<syntaxhighlight lang="jq">
def Segment($x; $y): {$x, $y};
def Circle($x; $y; $r) : {$x, $y, $r};
def sq: . * .;
def distance($x; $y):
(($x.x - $y.x)|sq) + (($x.y - $y.y)|sq) | sqrt;
# Is the circle $c1 contained within the circle $c2?
def le($c1; $c2):
$c1 | distance(.;$c2) + .r <= $c2.r;
# Input: an array of circles, sorted by radius length.
# Output: the same array but pruned of any circle contained within another.
def winnow:
if length <= 1 then .
else .[0] as $circle
| .[1:] as $rest
| if any( $rest[]; le($circle; .) )
then $rest | winnow
else [$circle] + ($rest | winnow)
end
end;
# Input: an array of Circles
# Output: the area covered by all the circles
# Method: Cavalieri, horizontally
def areaScan(precision):
def segment($c; $y):
( (($c.r|sq) - (($y - $c.y)|sq) ) | sqrt) as $dr
| Segment($c.x - $dr; $c.x + $dr);
(sort_by(.r) | winnow) as $circles
| (map( .y + .r ) + map(.y - .r )) as $ys
| ((($ys | min) / precision)|floor) as $miny
| ((($ys | max) / precision)|ceil ) as $maxy
| reduce range($miny; 1 + $maxy) as $x ({total: 0};
($x * precision) as $y
| .right = - infinite
| ($circles
| map( select( (($y - .y)|length) < .r)) # length computes abs
| map( segment(.; $y)) ) as $segments
| reduce ($segments | sort_by(.x))[] as $p (.;
if $p.y > .right
then .total += $p.y - ([$p.x, .right]|max)
| .right = $p.y
else .
end ) )
| .total * precision ;
# The Task
def circles: [
Circle( 1.6417233788; 1.6121789534; 0.0848270516),
Circle(-1.4944608174; 1.2077959613; 1.1039549836),
Circle( 0.6110294452; -0.6907087527; 0.9089162485),
Circle( 0.3844862411; 0.2923344616; 0.2375743054),
Circle(-0.2495892950; -0.3832854473; 1.0845181219),
Circle( 1.7813504266; 1.6178237031; 0.8162655711),
Circle(-0.1985249206; -0.8343333301; 0.0538864941),
Circle(-1.7011985145; -0.1263820964; 0.4776976918),
Circle(-0.4319462812; 1.4104420482; 0.7886291537),
Circle( 0.2178372997; -0.9499557344; 0.0357871187),
Circle(-0.6294854565; -1.3078893852; 0.7653357688),
Circle( 1.7952608455; 0.6281269104; 0.2727652452),
Circle( 1.4168575317; 1.0683357171; 1.1016025378),
Circle( 1.4637371396; 0.9463877418; 1.1846214562),
Circle(-0.5263668798; 1.7315156631; 1.4428514068),
Circle(-1.2197352481; 0.9144146579; 1.0727263474),
Circle(-0.1389358881; 0.1092805780; 0.7350208828),
Circle( 1.5293954595; 0.0030278255; 1.2472867347),
Circle(-0.5258728625; 1.3782633069; 1.3495508831),
Circle(-0.1403562064; 0.2437382535; 1.3804956588),
Circle( 0.8055826339; -0.0482092025; 0.3327165165),
Circle(-0.6311979224; 0.7184578971; 0.2491045282),
Circle( 1.4685857879; -0.8347049536; 1.3670667538),
Circle(-0.6855727502; 1.6465021616; 1.0593087096),
Circle( 0.0152957411; 0.0638919221; 0.9771215985)
];
"Approximate area = \(circles | areaScan(1e-5))"
</syntaxhighlight>
{{output}}
<pre>
Approximate area = 21.565036588498263
</pre>
=={{header|Julia}}==
Simple grid algorithm. Borrows the xmin/xmax idea from the Python version. This algorithm is fairly slow.
<syntaxhighlight lang="julia">using Printf
# Total circles area: https://rosettacode.org/wiki/Total_circles_area
xc = [1.6417233788, -1.4944608174, 0.6110294452, 0.3844862411, -0.2495892950, 1.7813504266,
-0.1985249206, -1.7011985145, -0.4319462812, 0.2178372997, -0.6294854565, 1.7952608455,
1.4168575317, 1.4637371396, -0.5263668798, -1.2197352481, -0.1389358881, 1.5293954595,
-0.5258728625, -0.1403562064, 0.8055826339, -0.6311979224, 1.4685857879, -0.6855727502,
0.0152957411]
yc = [1.6121789534, 1.2077959613, -0.6907087527, 0.2923344616, -0.3832854473, 1.6178237031,
-0.8343333301, -0.1263820964, 1.4104420482, -0.9499557344, -1.3078893852, 0.6281269104,
1.0683357171, 0.9463877418, 1.7315156631, 0.9144146579, 0.1092805780, 0.0030278255,
1.3782633069, 0.2437382535, -0.0482092025, 0.7184578971, -0.8347049536, 1.6465021616,
0.0638919221]
r = [0.0848270516, 1.1039549836, 0.9089162485, 0.2375743054, 1.0845181219, 0.8162655711,
0.0538864941, 0.4776976918, 0.7886291537, 0.0357871187, 0.7653357688, 0.2727652452,
1.1016025378, 1.1846214562, 1.4428514068, 1.0727263474, 0.7350208828, 1.2472867347,
1.3495508831, 1.3804956588, 0.3327165165, 0.2491045282, 1.3670667538, 1.0593087096,
0.9771215985]
# Size of my grid -- higher values => higher accuracy.
function main(xc::Vector{<:Real}, yc::Vector{<:Real}, r::Vector{<:Real}, ngrid::Integer=10000)
r2 = r .* r
ncircles = length(xc)
# Compute the bounding box of the circles.
xmin = minimum(xc .- r)
xmax = maximum(xc .+ r)
ymin = minimum(yc .- r)
ymax = maximum(yc .+ r)
# Keep a counter.
inside = 0
# For every point in my grid.
for x in LinRange(xmin, xmax, ngrid), y = LinRange(ymin, ymax, ngrid)
inside += any(r2 .> (x .- xc) .^ 2 + (y .- yc) .^ 2)
end
boxarea = (xmax - xmin) * (ymax - ymin)
return boxarea * inside / ngrid ^ 2
end
println(@time main(xc, yc, r, 1000))</syntaxhighlight>
=={{header|Kotlin}}==
===Grid Sampling Version===
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.2
class Circle(val x: Double, val y: Double, val r: Double)
val circles = arrayOf(
Circle( 1.6417233788, 1.6121789534, 0.0848270516),
Circle(-1.4944608174, 1.2077959613, 1.1039549836),
Circle( 0.6110294452, -0.6907087527, 0.9089162485),
Circle( 0.3844862411, 0.2923344616, 0.2375743054),
Circle(-0.2495892950, -0.3832854473, 1.0845181219),
Circle( 1.7813504266, 1.6178237031, 0.8162655711),
Circle(-0.1985249206, -0.8343333301, 0.0538864941),
Circle(-1.7011985145, -0.1263820964, 0.4776976918),
Circle(-0.4319462812, 1.4104420482, 0.7886291537),
Circle( 0.2178372997, -0.9499557344, 0.0357871187),
Circle(-0.6294854565, -1.3078893852, 0.7653357688),
Circle( 1.7952608455, 0.6281269104, 0.2727652452),
Circle( 1.4168575317, 1.0683357171, 1.1016025378),
Circle( 1.4637371396, 0.9463877418, 1.1846214562),
Circle(-0.5263668798, 1.7315156631, 1.4428514068),
Circle(-1.2197352481, 0.9144146579, 1.0727263474),
Circle(-0.1389358881, 0.1092805780, 0.7350208828),
Circle( 1.5293954595, 0.0030278255, 1.2472867347),
Circle(-0.5258728625, 1.3782633069, 1.3495508831),
Circle(-0.1403562064, 0.2437382535, 1.3804956588),
Circle( 0.8055826339, -0.0482092025, 0.3327165165),
Circle(-0.6311979224, 0.7184578971, 0.2491045282),
Circle( 1.4685857879, -0.8347049536, 1.3670667538),
Circle(-0.6855727502, 1.6465021616, 1.0593087096),
Circle( 0.0152957411, 0.0638919221, 0.9771215985)
)
fun Double.sq() = this * this
fun main(args: Array<String>) {
val xMin = circles.map { it.x - it.r }.min()!!
val xMax = circles.map { it.x + it.r }.max()!!
val yMin = circles.map { it.y - it.r }.min()!!
val yMax = circles.map { it.y + it.r }.max()!!
val boxSide = 5000
val dx = (xMax - xMin) / boxSide
val dy = (yMax - yMin) / boxSide
var count = 0
for (r in 0 until boxSide) {
val y = yMin + r * dy
for (c in 0 until boxSide) {
val x = xMin + c * dx
val b = circles.any { (x - it.x).sq() + (y - it.y).sq() <= it.r.sq() }
if (b) count++
}
}
println("Approximate area = ${count * dx * dy}")
}
</syntaxhighlight>
{{out}}
<pre>
Approximate area = 21.564955642878786
</pre>
===Scanline Version===
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.2
class Point(val x: Double, val y: Double)
class Circle(val x: Double, val y: Double, val r: Double)
val circles = arrayOf(
Circle( 1.6417233788, 1.6121789534, 0.0848270516),
Circle(-1.4944608174, 1.2077959613, 1.1039549836),
Circle( 0.6110294452, -0.6907087527, 0.9089162485),
Circle( 0.3844862411, 0.2923344616, 0.2375743054),
Circle(-0.2495892950, -0.3832854473, 1.0845181219),
Circle( 1.7813504266, 1.6178237031, 0.8162655711),
Circle(-0.1985249206, -0.8343333301, 0.0538864941),
Circle(-1.7011985145, -0.1263820964, 0.4776976918),
Circle(-0.4319462812, 1.4104420482, 0.7886291537),
Circle( 0.2178372997, -0.9499557344, 0.0357871187),
Circle(-0.6294854565, -1.3078893852, 0.7653357688),
Circle( 1.7952608455, 0.6281269104, 0.2727652452),
Circle( 1.4168575317, 1.0683357171, 1.1016025378),
Circle( 1.4637371396, 0.9463877418, 1.1846214562),
Circle(-0.5263668798, 1.7315156631, 1.4428514068),
Circle(-1.2197352481, 0.9144146579, 1.0727263474),
Circle(-0.1389358881, 0.1092805780, 0.7350208828),
Circle( 1.5293954595, 0.0030278255, 1.2472867347),
Circle(-0.5258728625, 1.3782633069, 1.3495508831),
Circle(-0.1403562064, 0.2437382535, 1.3804956588),
Circle( 0.8055826339, -0.0482092025, 0.3327165165),
Circle(-0.6311979224, 0.7184578971, 0.2491045282),
Circle( 1.4685857879, -0.8347049536, 1.3670667538),
Circle(-0.6855727502, 1.6465021616, 1.0593087096),
Circle( 0.0152957411, 0.0638919221, 0.9771215985)
)
fun Double.sq() = this * this
fun areaScan(precision: Double): Double {
fun sect(c: Circle, y: Double): Point {
val dr = Math.sqrt(c.r.sq() - (y - c.y).sq())
return Point(c.x - dr, c.x + dr)
}
val ys = circles.map { it.y + it.r } + circles.map { it.y - it.r }
val mins = Math.floor(ys.min()!! / precision).toInt()
val maxs = Math.ceil(ys.max()!! / precision).toInt()
var total = 0.0
for (x in mins..maxs) {
val y = x * precision
var right = Double.NEGATIVE_INFINITY
val points = circles.filter { Math.abs(y - it.y) < it.r }
.map { sect(it, y) }
.sortedBy { it.x }
for (p in points) {
if (p.y <= right) continue
total += p.y - maxOf(p.x, right)
right = p.y
}
}
return total * precision
}
fun main(args: Array<String>) {
val p = 1e-6
println("Approximate area = ${areaScan(p)}")
}</syntaxhighlight>
{{out}}
<pre>
Approximate area = 21.565036604050903
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Simple solution needs Mathematica 10:
<syntaxhighlight lang="mathematica">data = ImportString[" 1.6417233788 1.6121789534 0.0848270516
-1.4944608174 1.2077959613 1.1039549836
0.6110294452 -0.6907087527 0.9089162485
Line 1,219 ⟶ 2,539:
toDisk[{x_, y_, r_}] := Disk[{x, y}, r];
RegionMeasure[RegionUnion[toDisk /@ data]]</
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).
Line 1,231 ⟶ 2,551:
Simple grid algorithm. Borrows the xmin/xmax idea from the Python version. This algorithm is fairly slow.
<
tic
Line 1,275 ⟶ 2,595:
toc
end</
=={{header|
===Grid Sampling Version===
{{trans|Python}}
<
type Circle = tuple[x, y, r: float]
Line 1,311 ⟶ 2,631:
( 0.0152957411, 0.0638919221, 0.9771215985)]
template sqr(x: SomeNumber): SomeNumber = x * x
let
let
let yMin = min circles.mapIt(it.y - it.r)
let yMax = max circles.mapIt(it.y + it.r)
const boxSide = 500
Line 1,323 ⟶ 2,645:
var count = 0
for r in 0 ..
let y = yMin + float(r) * dy
for c in 0 ..
let x = xMin + float(c) * dx
for circle in circles:
if sqr(x -
inc count
break
echo "Approximated area: ", float(count) * dx * dy</
{{out}}
<pre>Approximated area: 21.56155977200332</pre>
=={{header|Perl}}==
{{trans|Python}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use List::AllUtils <min max>;
my @circles = (
[ 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],
);
my $x_min = min map { $_->[0] - $_->[2] } @circles;
my $x_max = max map { $_->[0] + $_->[2] } @circles;
my $y_min = min map { $_->[1] - $_->[2] } @circles;
my $y_max = max map { $_->[1] + $_->[2] } @circles;
my $box_side = 500;
my $dx = ($x_max - $x_min) / $box_side;
my $dy = ($y_max - $y_min) / $box_side;
my $count = 0;
for my $r (0..$box_side) {
for my $c (0..$box_side) {
my $x = $x_min + $c * $dx;
for my $c (@circles) {
$count++ and last if ($x - $$c[0])**2 + ($y - $$c[1])**2 <= $$c[2]**2
}
}
printf "Approximated area: %.9f\n", $count * $dx * $dy;</syntaxhighlight>
{{out}}
<pre>Approximated area: 21.561559772</pre>
=={{header|Phix}}==
{{trans|Python}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">circles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">1.6417233788</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.6121789534</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.0848270516</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1.4944608174</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.2077959613</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.1039549836</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0.6110294452</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.6907087527</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.9089162485</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0.3844862411</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2923344616</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2375743054</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.2495892950</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.3832854473</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.0845181219</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.7813504266</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.6178237031</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.8162655711</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.1985249206</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.8343333301</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.0538864941</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1.7011985145</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.1263820964</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.4776976918</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.4319462812</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.4104420482</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.7886291537</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0.2178372997</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.9499557344</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.0357871187</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.6294854565</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1.3078893852</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.7653357688</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.7952608455</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.6281269104</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2727652452</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.4168575317</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.0683357171</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.1016025378</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.4637371396</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.9463877418</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.1846214562</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.5263668798</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.7315156631</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.4428514068</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1.2197352481</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.9144146579</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.0727263474</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.1389358881</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.1092805780</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.7350208828</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.5293954595</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.0030278255</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.2472867347</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.5258728625</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.3782633069</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.3495508831</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.1403562064</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2437382535</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.3804956588</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0.8055826339</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.0482092025</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.3327165165</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.6311979224</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.7184578971</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.2491045282</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">1.4685857879</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.8347049536</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.3670667538</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.6855727502</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.6465021616</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1.0593087096</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0.0152957411</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.0638919221</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.9771215985</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">(</span><span style="color: #000000;">circles</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">xMin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">xMax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">yMin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">yMax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">boxSide</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">xMax</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">xMin</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">boxSide</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">yMax</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">yMin</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">boxSide</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cxs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">boxSide</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">py</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">yMin</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">dy</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cy</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">py</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">boxSide</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">px</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xMin</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">dx</span>
<span style="color: #000000;">cxs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cxs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sq_power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cxs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">circles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">cx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]<=</span><span style="color: #000000;">r2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">+=</span><span style="color: #000000;">1</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Approximate area = %.9f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">dx</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">dy</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Approximate area = 21.561559772
</pre>
=={{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")
Line 1,593 ⟶ 2,839:
print "Approximated area:", count * dx * dy
main()</
{{out}}
<pre>Approximated area: 21.561559772</pre>
===Scanline Conversion===
<
def area_scan(prec, circs):
Line 1,654 ⟶ 2,900:
print "@stepsize", p, "area = %.4f" % area_scan(p, circles)
main()</
===2D Van der Corput sequence===
[[File:Van_der_Corput_2D.png|200px|thumb|right]]
Line 1,664 ⟶ 2,910:
* Wholly obscured circles removed,
* And the square of the radius computed outside the main loops.
<
from math import sqrt
from itertools import count
Line 1,769 ⟶ 3,015:
if __name__ == '__main__':
main(circles)</
The above is tested to work with Python v.2.7, Python3 and PyPy.
{{out}}
Line 1,793 ⟶ 3,039:
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
Line 1,950 ⟶ 3,196:
print "Total Area:", circles_area(circles)
main()</
{{out}}
<pre>Total Area: 21.56503660385639895908422492887814801839</pre>
Line 1,957 ⟶ 3,203:
See: [[Example:Total_circles_area/Racket]]
=={{header|Raku}}==
(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.
<syntaxhighlight lang="raku" line>class Point {
has Real $.x;
has Real $.y;
has Int $!cbits; # bitmap of circle membership
method cbits { $!cbits //= set_cbits(self) }
method gist { $!x ~ "\t" ~ $!y }
}
multi infix:<to>(Point $p1, Point $p2) {
sqrt ($p1.x - $p2.x) ** 2 + ($p1.y - $p2.y) ** 2;
}
multi infix:<mid>(Point $p1, Point $p2) {
Point.new(x => ($p1.x + $p2.x) / 2, y => ($p1.y + $p2.y) / 2);
}
class Circle {
has Point $.center;
has Real $.radius;
has Point $.north = Point.new(x => $!center.x, y => $!center.y + $!radius);
has Point $.west = Point.new(x => $!center.x - $!radius, y => $!center.y);
has Point $.south = Point.new(x => $!center.x, y => $!center.y - $!radius);
has Point $.east = Point.new(x => $!center.x + $!radius, y => $!center.y);
multi method contains(Circle $c) { $!center to $c.center <= $!radius - $c.radius }
multi method contains(Point $p) { $!center to $p <= $!radius }
method gist { $!center.gist ~ "\t" ~ $.radius }
}
class Rect {
has Point $.nw;
has Point $.ne;
has Point $.sw;
has Point $.se;
method diag { $!ne to $!se }
method area { ($!ne.x - $!nw.x) * ($!nw.y - $!sw.y) }
method contains(Point $p) {
$!nw.x < $p.x < $!ne.x and
$!sw.y < $p.y < $!nw.y;
}
}
my @rawcircles = sort -*.radius,
map -> $x, $y, $radius { Circle.new(:center(Point.new(:$x, :$y)), :$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
>».Num;
# remove redundant circles
my @circles;
while @rawcircles {
my $c = @rawcircles.shift;
next if @circles.any.contains($c);
push @circles, $c;
}
sub set_cbits(Point $p) {
my $cbits = 0;
for @circles Z (1,2,4...*) -> ($c, $b) {
$cbits += $b if $c.contains($p);
}
$cbits;
}
my $xmin = min @circles.map: { .center.x - .radius }
my $xmax = max @circles.map: { .center.x + .radius }
my $ymin = min @circles.map: { .center.y - .radius }
my $ymax = max @circles.map: { .center.y + .radius }
my $min-radius = @circles[*-1].radius;
my $outer-rect = Rect.new:
nw => Point.new(x => $xmin, y => $ymax),
ne => Point.new(x => $xmax, y => $ymax),
sw => Point.new(x => $xmin, y => $ymin),
se => Point.new(x => $xmax, y => $ymin);
my $outer-area = $outer-rect.area;
my @unknowns = $outer-rect;
my $known-dry = 0e0;
my $known-wet = 0e0;
my $div = 1;
# divide current rects each into four rects, analyze each
sub divide(@old) {
$div *= 2;
# rects too small to hold circle?
my $smallish = @old[0].diag < $min-radius;
my @unk;
for @old {
my $center = .nw mid .se;
my $north = .nw mid .ne;
my $south = .sw mid .se;
my $west = .nw mid .sw;
my $east = .ne mid .se;
for Rect.new(nw => .nw, ne => $north, sw => $west, se => $center),
Rect.new(nw => $north, ne => .ne, sw => $center, se => $east),
Rect.new(nw => $west, ne => $center, sw => .sw, se => $south),
Rect.new(nw => $center, ne => $east, sw => $south, se => .se)
{
my @bits = .nw.cbits, .ne.cbits, .sw.cbits, .se.cbits;
# if all 4 points wet by same circle, guaranteed wet
if [+&] @bits {
$known-wet += .area;
next;
}
# if all 4 corners are dry, must check further
if not [+|] @bits and $smallish {
# check that no circle bulges into this rect
my $ok = True;
for @circles -> $c {
if .contains($c.east) or .contains($c.west) or
.contains($c.north) or .contains($c.south)
{
$ok = False;
last;
}
}
if $ok {
$known-dry += .area;
next;
}
}
push @unk, $_; # dunno yet
}
}
@unk;
}
my $delta = 0.001;
repeat until my $diff < $delta {
@unknowns = divide(@unknowns);
$diff = $outer-area - $known-dry - $known-wet;
say 'div: ', $div.fmt('%-5d'),
' unk: ', (+@unknowns).fmt('%-6d'),
' est: ', ($known-wet + $diff/2).fmt('%9.6f'),
' wet: ', $known-wet.fmt('%9.6f'),
' dry: ', ($outer-area - $known-dry).fmt('%9.6f'),
' diff: ', $diff.fmt('%9.6f'),
' error: ', ($diff - @unknowns * @unknowns[0].area).fmt('%e');
}</syntaxhighlight>
{{out}}
<pre>div: 2 unk: 4 est: 14.607153 wet: 0.000000 dry: 29.214306 diff: 29.214306 error: 0.000000e+000
div: 4 unk: 15 est: 15.520100 wet: 1.825894 dry: 29.214306 diff: 27.388411 error: 0.000000e+000
div: 8 unk: 39 est: 20.313072 wet: 11.411838 dry: 29.214306 diff: 17.802467 error: 7.105427e-015
div: 16 unk: 107 est: 23.108972 wet: 17.003639 dry: 29.214306 diff: 12.210667 error: -1.065814e-014
div: 32 unk: 142 est: 21.368667 wet: 19.343066 dry: 23.394268 diff: 4.051203 error: 8.881784e-014
div: 64 unk: 290 est: 21.504182 wet: 20.469985 dry: 22.538380 diff: 2.068396 error: 1.771916e-013
div: 128 unk: 582 est: 21.534495 wet: 21.015613 dry: 22.053377 diff: 1.037764 error: -3.175238e-013
div: 256 unk: 1169 est: 21.557898 wet: 21.297343 dry: 21.818454 diff: 0.521111 error: -2.501332e-013
div: 512 unk: 2347 est: 21.563415 wet: 21.432636 dry: 21.694194 diff: 0.261558 error: -1.046996e-012
div: 1024 unk: 4700 est: 21.564111 wet: 21.498638 dry: 21.629584 diff: 0.130946 error: 1.481315e-013
div: 2048 unk: 9407 est: 21.564804 wet: 21.532043 dry: 21.597565 diff: 0.065522 error: 1.781700e-012
div: 4096 unk: 18818 est: 21.564876 wet: 21.548492 dry: 21.581260 diff: 0.032768 error: 1.098372e-011
div: 8192 unk: 37648 est: 21.564992 wet: 21.556797 dry: 21.573187 diff: 0.016389 error: -1.413968e-011
div: 16384 unk: 75301 est: 21.565017 wet: 21.560920 dry: 21.569115 diff: 0.008195 error: -7.683898e-011
div: 32768 unk: 150599 est: 21.565031 wet: 21.562982 dry: 21.567080 diff: 0.004097 error: -1.247991e-010
div: 65536 unk: 301203 est: 21.565035 wet: 21.564010 dry: 21.566059 diff: 0.002049 error: -2.830591e-010
div: 131072 unk: 602411 est: 21.565036 wet: 21.564524 dry: 21.565548 diff: 0.001024 error: -1.607121e-010</pre>
Here the "diff" is calculated by subtracting the known wet and dry areas from the total area, and the "error" is the difference between that and the sum of the areas of the unknown blocks, to give a rough idea of how much floating point roundoff error we've accumulated.
=={{header|REXX}}==
These REXX programs use the grid sampling method.
===using all circles===
<
parse arg box dig . /*obtain
if box=='' | box==',' then box= 500
numeric digits dig
data = '
' 0.
'
'
'-
'-
'
' 1.
' 1.
'
'-
'-
'
'-0.
'
circles= words(data) % 3 /* ══x══ ══y══ ══radius══ */
parse var data minX minY . 1 maxX maxY .
do j=1 for circles; _= j * 3 - 2 /*assign some circles with datum. */
minY= min(minY, @y.j - @r.j); maxY= max(maxY, @y.j + @r.j)
end /*j*/
dx= (maxX-minX) / box
dy= (maxY-minY) / box
#= 0 /*count of sample points
do row=0 to box; y= minY + row*dy /*process each of the grid rows.
do col=0 to box; x= minX + col*dx /*
do k=1 for circles /*now process each new circle. */
if (x - @x.k)**2 + (y - @y.k)**2 <= @rr.k then do; #= # + 1; leave; end
end /*k*/
end /*col*/
end /*row*/
/*stick a fork in it, we're done. */
say '
say 'the approximate area is: ' # * dx * dy</syntaxhighlight>
{{out|output|text= when using the internal default input:}}
<pre>
the approximate area is: 21.5615597720
</pre>
===optimized===
This REXX version elides any circle that is completely contained in another circle.
Also, another optimization is the sorting of the circles by (descending) radii,
<br>this reduces the computation time (for overlapping circles) by around 25%.
This, with other optimizations, makes this 2<sup>nd</sup> REXX version about twice as fast as the 1<sup>st</sup> REXX version.
This version also has additional information displayed.
<
parse arg box dig . /*obtain
if box=='' | box==',' then box= -500
numeric digits
/* ══════x══════ ══════y══════ ═══radius═══ ══════x══════ ══════y══════ ═══radius═══*/
$=' 1.6417233788 1.6121789534 0.0848270516
' 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
'-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 ' /*define circles with X, Y, and R.*/
circles= words($) % 3
if verbose then say 'There are' circles "circles." /*display the number of circles. */
parse var $ minX minY . 1 maxX maxY . /*assign minimum & maximum
@r.j=word($, _ + 2) / 1; @rr.j= @r.j **2
minX= min(minX, @x.j - @r.j); maxX= max(maxX, @x.j + @r.j)
minY= min(minY, @y.j - @r.j); maxY= max(maxY, @y.j + @r.j)
end /*j*/
do m=1 for circles /*sort the circles by their radii.*/
do n=m+1 to circles /* [↓] sort by descending radii.*/
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 /*n*/ /* [↑] Is it
end /*m*/
dx= (maxX-minX) / box; dy= (maxY-minY) / box /*compute the DX and DY values*/
do z=0 for boxen; rowDY.z= z * dy; colDX.z= z * dx
w= length(circles) /*W: used for aligning output. */
#in= 0 /*#in ◄───fully contained circles.*/
do j=1 for circles /*traipse through all the circles.*/
do k=1 for circles; if k==j | @r.j==0 then iterate /*skip oneself. */
if @y.j+@r.j > @y.k+@r.k | @x.j-@r.j < @x.k-@r.k |, /*is J inside K? */
@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)
@r.j= 0; #in= #in + 1 /*elide this circle; and bump #in.*/
end /*k*/
end /*j*/ /* [↑] elided overlapping circle.*/
if #in==0 then #in= 'no'
if verbose then do; say; say #in " circles are fully contained within other circles.";end
nC= 0
#= 0
do k=1 for nC /*now process each new circle. */
end /*k*/
end /*col*/
end /*row*/
say /*stick a fork in it, we're done. */
say 'Using ' box " boxes (which have " box**2 ' points) and ' dig " decimal digits,"
say 'the approximate area is: ' # * dx * dy</syntaxhighlight>
{{out|output|text= when using various number of boxes:}}
[Output shown is a combination of several runs.]
<pre>
There are 25 circles.
Circle
Circle
Circle
Circle
Circle
Circle
Circle
Circle
Circle
Circle 24 is contained in circle
Circle 25 is contained in circle
11 circles are fully contained within other circles.
Using 125 boxes (which have 15625 points) and 12 decimal digits,
the approximate area is: 21.5353837543
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 250 boxes (which have 62500 points) and 12 decimal digits,
the approximate area is: 21.5536134809
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 500 boxes (which have 250000 points) and 12 decimal digits,
the approximate area is: 21.5615597720
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 1000 boxes (which have 1000000 points) and 12 decimal digits,
the approximate area is: 21.5638384878
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 2000 boxes (which have 4000000 points) and 12 decimal digits,
the approximate area is: 21.5646564884
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 4000 boxes (which have 16000000 points) and 12 decimal digits,
the approximate area is: 21.5649121136
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 8000 boxes (which have 64000000 points) and 12 decimal digits,
the approximate area is: 21.5650301120
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 8000 boxes (which have 64000000 points) and 20 decimal digits,
the approximate area is: 21.565000669427195997
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
Using 16000 boxes (which have 256000000 points) and 12 decimal digits,
the approximate area is: 21.5650301120
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
the approximate area is: 21.565030111969493682
</pre>
=={{header|Ruby}}==
Common code
<
[ 1.6417233788, 1.6121789534, 0.0848270516],
[-1.4944608174, 1.2077959613, 1.1039549836],
Line 2,192 ⟶ 3,663:
circles.values_at(*select)
end
circles = select_circle(circles)</
===Grid Sampling===
{{trans|Python}}
<
# compute the bounding box of the circles
xmin, xmax, ymin, ymax = minmax_circle(circles)
Line 2,225 ⟶ 3,696:
n *= 2
puts "#{Time.now - t0} sec"
end</
{{out}}
Line 2,238 ⟶ 3,709:
===Scanline Method===
{{trans|Python}}
<
sect = ->(y) do
circles.select{|cx,cy,r| (y - cy).abs < r}.map do |cx,cy,r|
Line 2,268 ⟶ 3,739:
puts "%8.6f : %12.9f, %p sec" % [prec, area_scan(prec, circles), Time.now-t0]
prec /= 10
end</
{{out}}
Line 2,280 ⟶ 3,751:
=={{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
Line 2,389 ⟶ 3,860:
puts [format "estimated area (grid): %.4f" [sampleGrid $circles 500]]
puts [format "estimated area (monte carlo): %.2f" [sampleMC $circles 1000000]]
puts [format "estimated area (perturbed sample): %.4f" [samplePerturb $circles 500 5]]</
{{out}}
<pre>
Line 2,397 ⟶ 3,868:
</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|Uiua}}==
{{works with|Uiua|0.10.0}}
Developed mainly to play with Uiua's image handling. Getting a very rough area figure is a bonus.
<syntaxhighlight lang="Uiua">
Cs ← [[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.249589295 ¯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.109280578 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]]
# Scale total range to (0-Dim,0-Dim), save MaxXorY for later.
Dim ← 500
MinXY ← /↧≡(-⊃(⊢|↘1)↻¯1) Cs
Zcs ← ≡(⬚0-MinXY) Cs
MaxXorY ← /↥/↥≡(+⊃(⊢|↘1)↻¯1) Zcs
Scs ← ⁅×Dim÷ MaxXorY Zcs
# For each r generate a 2r.2r grid and set cells that are within circle.
InCircle ← <ⁿ2⟜(⊞(/+≡ⁿ2⊟).+⇡⊃(×2|¯))
# Fade this circle out, then add to accumulator, offset appropriately.
Filler ← ⍜(↻|⬚0+)⊙: ⊃(+¯|×0.1InCircle) ⊃(⊢|↘1) ↻¯1
# Fold over all circles, accumulating into a blank grid.
⍜now(∧Filler Scs ↯Dim_Dim 0)
&p &pf "Runtime (s): "
×ⁿ2 ÷Dim MaxXorY (⧻⊚≠0) ♭.
&p &pf "*Very* approximate area: "
# Uncomment to save image.
# &ime "png"
# &fwa "UiuaOverlappingCircles.png"
</syntaxhighlight>
{{out}}
<pre>
stdout:
Runtime (s): 3.7929999999978463
*Very* approximate area: 21.56451023743893
</pre>
[[File:UiuaOverlappingCircles.png|300px|thumbnail|center|Overlapping translucent circles]]
<p></p>
=={{header|VBA}}==
Analytical solution adapted from Haskell/Python.
<syntaxhighlight lang="vb">Public c As Variant
Public pi As Double
Dim arclists() As Variant
Public Enum circles_
xc = 0
yc
rc
End Enum
Public Enum arclists_
rho
x_
y_
i_
End Enum
Public Enum shoelace_axis
u = 0
v
End Enum
Private Sub give_a_list_of_circles()
c = Array(Array(1.6417233788, 1.6121789534, 0.0848270516), _
Array(-1.4944608174, 1.2077959613, 1.1039549836), _
Array(0.6110294452, -0.6907087527, 0.9089162485), _
Array(0.3844862411, 0.2923344616, 0.2375743054), _
Array(-0.249589295, -0.3832854473, 1.0845181219), _
Array(1.7813504266, 1.6178237031, 0.8162655711), _
Array(-0.1985249206, -0.8343333301, 0.0538864941), _
Array(-1.7011985145, -0.1263820964, 0.4776976918), _
Array(-0.4319462812, 1.4104420482, 0.7886291537), _
Array(0.2178372997, -0.9499557344, 0.0357871187), _
Array(-0.6294854565, -1.3078893852, 0.7653357688), _
Array(1.7952608455, 0.6281269104, 0.2727652452), _
Array(1.4168575317, 1.0683357171, 1.1016025378), _
Array(1.4637371396, 0.9463877418, 1.1846214562), _
Array(-0.5263668798, 1.7315156631, 1.4428514068), _
Array(-1.2197352481, 0.9144146579, 1.0727263474), _
Array(-0.1389358881, 0.109280578, 0.7350208828), _
Array(1.5293954595, 0.0030278255, 1.2472867347), _
Array(-0.5258728625, 1.3782633069, 1.3495508831), _
Array(-0.1403562064, 0.2437382535, 1.3804956588), _
Array(0.8055826339, -0.0482092025, 0.3327165165), _
Array(-0.6311979224, 0.7184578971, 0.2491045282), _
Array(1.4685857879, -0.8347049536, 1.3670667538), _
Array(-0.6855727502, 1.6465021616, 1.0593087096), _
Array(0.0152957411, 0.0638919221, 0.9771215985))
pi = WorksheetFunction.pi()
End Sub
Private Function shoelace(s As Collection) As Double
's is a collection of coordinate pairs (x, y),
'in clockwise order for positive result.
'The last pair is identical to the first pair.
'These pairs map a polygonal area.
'The area is computed with the shoelace algoritm.
'see the Rosetta Code task.
Dim t As Double
If s.Count > 2 Then
s.Add s(1)
For i = 1 To s.Count - 1
t = t + s(i + 1)(u) * s(i)(v) - s(i)(u) * s(i + 1)(v)
Next i
End If
shoelace = t / 2
End Function
Private Sub arc_sub(acol As Collection, f0 As Double, u0 As Double, v0 As Double, _
f1 As Double, u1 As Double, v1 As Double, this As Integer, j As Integer)
'subtract the arc from f0 to f1 from the arclist acol
'complicated to deal with edge cases
If acol.Count = 0 Then Exit Sub 'nothing to subtract from
Debug.Assert acol.Count Mod 2 = 0
Debug.Assert f0 <> f1
If f1 = pi Or f1 + pi < 5E-16 Then f1 = -f1
If f0 = pi Or f0 + pi < 5E-16 Then f0 = -f0
If f0 < f1 Then
'the arc does not pass the negative x-axis
'find a such that acol(a)(0)<f0<acol(a+1)(0)
' and b such that acol(b)(0)<f1<acol(b+1)(0)
If f1 < acol(1)(rho) Or f0 > acol(acol.Count)(rho) Then Exit Sub 'nothing to subtract
i = acol.Count + 1
start = 1
Do
i = i - 1
Loop Until f1 > acol(i)(rho)
If i Mod 2 = start Then
acol.Add Array(f1, u1, v1, j), after:=i
End If
i = 0
Do
i = i + 1
Loop Until f0 < acol(i)(rho)
If i Mod 2 = 1 - start Then
acol.Add Array(f0, u0, v0, j), before:=i
i = i + 1
End If
Do While acol(i)(rho) < f1
acol.Remove i
If i > acol.Count Then Exit Do
Loop
Else
start = 1
If f0 > acol(1)(rho) Then
i = acol.Count + 1
Do
i = i - 1
Loop While f0 < acol(i)(0)
If f0 = pi Then
acol.Add Array(f0, u0, v0, j), before:=i
Else
If i Mod 2 = start Then
acol.Add Array(f0, u0, v0, j), after:=i
End If
End If
End If
If f1 <= acol(acol.Count)(rho) Then
i = 0
Do
i = i + 1
Loop While f1 > acol(i)(rho)
If f1 + pi < 5E-16 Then
acol.Add Array(f1, u1, v1, j), after:=i
Else
If i Mod 2 = 1 - start Then
acol.Add Array(f1, u1, v1, j), before:=i
End If
End If
End If
Do While acol(acol.Count)(rho) > f0 Or acol(acol.Count)(i_) = -1
acol.Remove acol.Count
If acol.Count = 0 Then Exit Do
Loop
If acol.Count > 0 Then
Do While acol(1)(rho) < f1 Or (f1 = -pi And acol(1)(i_) = this)
acol.Remove 1
If acol.Count = 0 Then Exit Do
Loop
End If
End If
End Sub
Private Sub circle_cross()
ReDim arclists(LBound(c) To UBound(c))
Dim alpha As Double, beta As Double
Dim x3 As Double, x4 As Double, y3 As Double, y4 As Double
Dim i As Integer, j As Integer
For i = LBound(c) To UBound(c)
Dim arccol As New Collection
'arccol is a collection or surviving arcs of circle i.
'It starts with the full circle. The collection
'alternates between start and ending angles of the arcs.
'This winds counter clockwise.
'Noted are angle, x coordinate, y coordinate and
'index number of circles with which circle i
'intersects at that angle and -1 marks visited. This defines
'ultimately a double linked list. So winding
'clockwise in the end is easy.
arccol.Add Array(-pi, c(i)(xc) - c(i)(r), c(i)(yc), i)
arccol.Add Array(pi, c(i)(xc) - c(i)(r), c(i)(yc), -1)
For j = LBound(c) To UBound(c)
If i <> j Then
x0 = c(i)(xc)
y0 = c(i)(yc)
r0 = c(i)(rc)
x1 = c(j)(xc)
y1 = c(j)(yc)
r1 = c(j)(rc)
d = Sqr((x0 - x1) ^ 2 + (y0 - y1) ^ 2)
'Ignore 0 and 1, we need only the 2 case.
If d >= r0 + r1 Or d <= Abs(r0 - r1) Then
'no intersections
Else
a = (r0 ^ 2 - r1 ^ 2 + d ^ 2) / (2 * d)
h = Sqr(r0 ^ 2 - a ^ 2)
x2 = x0 + a * (x1 - x0) / d
y2 = y0 + a * (y1 - y0) / d
x3 = x2 + h * (y1 - y0) / d
y3 = y2 - h * (x1 - x0) / d
alpha = WorksheetFunction.Atan2(x3 - x0, y3 - y0)
x4 = x2 - h * (y1 - y0) / d
y4 = y2 + h * (x1 - x0) / d
beta = WorksheetFunction.Atan2(x4 - x0, y4 - y0)
'alpha is counterclockwise positioned w.r.t beta
'so the arc from beta to alpha (ccw) has to be
'subtracted from the list of surviving arcs as
'this arc lies fully in circle j
arc_sub arccol, alpha, x3, y3, beta, x4, y4, i, j
End If
End If
Next j
Set arclists(i) = arccol
Set arccol = Nothing
Next i
End Sub
Private Sub make_path()
Dim pathcol As New Collection, arcsum As Double
i0 = UBound(arclists)
finished = False
Do While True
arcsum = 0
Do While arclists(i0).Count = 0
i0 = i0 - 1
Loop
j0 = arclists(i0).Count
next_i = i0
next_j = j0
Do While True
x = arclists(next_i)(next_j)(x_)
y = arclists(next_i)(next_j)(y_)
pathcol.Add Array(x, y)
prev_i = next_i
prev_j = next_j
If arclists(next_i)(next_j - 1)(i_) = next_i Then
'skip the join point at the negative x-axis
next_j = arclists(next_i).Count - 1
If next_j = 1 Then Exit Do 'loose full circle arc
Else
next_j = next_j - 1
End If
'------------------------------
r = c(next_i)(rc)
a1 = arclists(next_i)(prev_j)(rho)
a2 = arclists(next_i)(next_j)(rho)
If a1 > a2 Then
alpha = a1 - a2
Else
alpha = 2 * pi - a2 + a1
End If
arcsum = arcsum + r * r * (alpha - Sin(alpha)) / 2
'------------------------------
next_i = arclists(next_i)(next_j)(i_)
next_j = arclists(next_i).Count
If next_j = 0 Then Exit Do 'skip loose arcs
Do While arclists(next_i)(next_j)(i_) <> prev_i
'find the matching item
next_j = next_j - 1
Loop
If next_i = i0 And next_j = j0 Then
finished = True
Exit Do
End If
Loop
If finished Then Exit Do
i0 = i0 - 1
Set pathcol = Nothing
Loop
Debug.Print shoelace(pathcol) + arcsum
End Sub
Public Sub total_circles()
give_a_list_of_circles
circle_cross
make_path
End Sub</syntaxhighlight>{{out}}
<pre> 21,5650366038564 </pre>
=={{header|Wren}}==
===Grid Sampling version===
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-math}}
Limited to 3000 boxes to finish in a reasonable time (about 25 seconds) with reasonable precision.
<syntaxhighlight lang="wren">import "./dynamic" for Tuple
import "./math" for Nums
var Circle = Tuple.create("Circle", ["x", "y", "r"])
var circles = [
Circle.new( 1.6417233788, 1.6121789534, 0.0848270516),
Circle.new(-1.4944608174, 1.2077959613, 1.1039549836),
Circle.new( 0.6110294452, -0.6907087527, 0.9089162485),
Circle.new( 0.3844862411, 0.2923344616, 0.2375743054),
Circle.new(-0.2495892950, -0.3832854473, 1.0845181219),
Circle.new( 1.7813504266, 1.6178237031, 0.8162655711),
Circle.new(-0.1985249206, -0.8343333301, 0.0538864941),
Circle.new(-1.7011985145, -0.1263820964, 0.4776976918),
Circle.new(-0.4319462812, 1.4104420482, 0.7886291537),
Circle.new( 0.2178372997, -0.9499557344, 0.0357871187),
Circle.new(-0.6294854565, -1.3078893852, 0.7653357688),
Circle.new( 1.7952608455, 0.6281269104, 0.2727652452),
Circle.new( 1.4168575317, 1.0683357171, 1.1016025378),
Circle.new( 1.4637371396, 0.9463877418, 1.1846214562),
Circle.new(-0.5263668798, 1.7315156631, 1.4428514068),
Circle.new(-1.2197352481, 0.9144146579, 1.0727263474),
Circle.new(-0.1389358881, 0.1092805780, 0.7350208828),
Circle.new( 1.5293954595, 0.0030278255, 1.2472867347),
Circle.new(-0.5258728625, 1.3782633069, 1.3495508831),
Circle.new(-0.1403562064, 0.2437382535, 1.3804956588),
Circle.new( 0.8055826339, -0.0482092025, 0.3327165165),
Circle.new(-0.6311979224, 0.7184578971, 0.2491045282),
Circle.new( 1.4685857879, -0.8347049536, 1.3670667538),
Circle.new(-0.6855727502, 1.6465021616, 1.0593087096),
Circle.new( 0.0152957411, 0.0638919221, 0.9771215985)
]
var sq = Fn.new { |v| v * v }
var xMin = Nums.min(circles.map { |c| c.x - c.r })
var xMax = Nums.max(circles.map { |c| c.x + c.r })
var yMin = Nums.min(circles.map { |c| c.y - c.r })
var yMax = Nums.max(circles.map { |c| c.y + c.r })
var boxSide = 3000
var dx = (xMax - xMin) / boxSide
var dy = (yMax - yMin) / boxSide
var count = 0
for (r in 0...boxSide) {
var y = yMin + r * dy
for (c in 0...boxSide) {
var x = xMin + c * dx
var b = circles.any { |c| sq.call(x-c.x) + sq.call(y-c.y) <= sq.call(c.r) }
if (b) count = count + 1
}
}
System.print("Approximate area = %(count * dx * dy)")</syntaxhighlight>
{{out}}
<pre>
Approximate area = 21.564890202834
</pre>
===Scanline version===
{{trans|Kotlin}}
{{libheader|Wren-sort}}
Quicker (about 4.7 seconds) and more precise (limited to 5 d.p. but achieves 7) than the above version.
<syntaxhighlight lang="wren">import "./dynamic" for Tuple
import "./math" for Nums
import "./sort" for Sort
var Point = Tuple.create("Point", ["x", "y"])
var Circle = Tuple.create("Circle", ["x", "y", "r"])
var circles = [
Circle.new( 1.6417233788, 1.6121789534, 0.0848270516),
Circle.new(-1.4944608174, 1.2077959613, 1.1039549836),
Circle.new( 0.6110294452, -0.6907087527, 0.9089162485),
Circle.new( 0.3844862411, 0.2923344616, 0.2375743054),
Circle.new(-0.2495892950, -0.3832854473, 1.0845181219),
Circle.new( 1.7813504266, 1.6178237031, 0.8162655711),
Circle.new(-0.1985249206, -0.8343333301, 0.0538864941),
Circle.new(-1.7011985145, -0.1263820964, 0.4776976918),
Circle.new(-0.4319462812, 1.4104420482, 0.7886291537),
Circle.new( 0.2178372997, -0.9499557344, 0.0357871187),
Circle.new(-0.6294854565, -1.3078893852, 0.7653357688),
Circle.new( 1.7952608455, 0.6281269104, 0.2727652452),
Circle.new( 1.4168575317, 1.0683357171, 1.1016025378),
Circle.new( 1.4637371396, 0.9463877418, 1.1846214562),
Circle.new(-0.5263668798, 1.7315156631, 1.4428514068),
Circle.new(-1.2197352481, 0.9144146579, 1.0727263474),
Circle.new(-0.1389358881, 0.1092805780, 0.7350208828),
Circle.new( 1.5293954595, 0.0030278255, 1.2472867347),
Circle.new(-0.5258728625, 1.3782633069, 1.3495508831),
Circle.new(-0.1403562064, 0.2437382535, 1.3804956588),
Circle.new( 0.8055826339, -0.0482092025, 0.3327165165),
Circle.new(-0.6311979224, 0.7184578971, 0.2491045282),
Circle.new( 1.4685857879, -0.8347049536, 1.3670667538),
Circle.new(-0.6855727502, 1.6465021616, 1.0593087096),
Circle.new( 0.0152957411, 0.0638919221, 0.9771215985)
]
var sq = Fn.new { |v| v * v }
var areaScan = Fn.new { |precision|
var sect = Fn.new { |c, y|
var dr = (sq.call(c.r) - sq.call(y-c.y)).sqrt
return Point.new(c.x - dr, c.x + dr)
}
var ys = circles.map { |c| c.y + c.r }.toList + circles.map { |c| c.y - c.r }.toList
var mins = (Nums.min(ys)/precision).floor
var maxs = (Nums.max(ys)/precision).ceil
var total = 0
for (x in mins..maxs) {
var y = x * precision
var right = -1/0
var points = circles.where { |c| (y - c.y).abs < c.r }.map { |c| sect.call(c, y) }.toList
var cmp = Fn.new { |p1, p2| (p1.x - p2.x).sign }
Sort.insertion(points, cmp)
for (p in points) {
if (p.y > right) {
total = total + p.y - p.x.max(right)
right = p.y
}
}
}
return total * precision
}
var p = 1e-5
System.print("Approximate area = %(areaScan.call(p))")</syntaxhighlight>
{{out}}
<pre>
Approximate area = 21.565036588498
</pre>
=={{header|XPL0}}==
Gird sampling. Takes 27 seconds on Pi4.
<syntaxhighlight lang="xpl0">real Circles, MinX, MaxX, MinY, MaxY, Temp, X, Y, DX, DY, Area;
int N, Cnt1, Cnt2;
def Del = 0.0005;
def Inf = float(-1>>1);
[\ X Y R
Circles:= [
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];
MinX:= +Inf; MaxX:= -Inf;
MinY:= +Inf; MaxY:= -Inf;
for N:= 0 to 25*3-1 do
[Temp:= Circles(N+0);
if Temp < 0.0 then Temp:= Temp - Circles(N+2)
else Temp:= Temp + Circles(N+2);
if Temp < MinX then MinX:= Temp;
if Temp > MaxX then MaxX:= Temp;
Temp:= Circles(N+1);
if Temp < 0.0 then Temp:= Temp - Circles(N+2)
else Temp:= Temp + Circles(N+2);
if Temp < MinY then MinY:= Temp;
if Temp > MaxY then MaxY:= Temp;
Circles(N+2):= sq(Circles(N+2)); \square for speed
N:= N+2;
];
Cnt1:= 0; Cnt2:= 0;
Y:= MinY;
repeat X:= MinX;
repeat
loop [for N:= 0 to 25*3-1 do
[DX:= X - Circles(N+0);
DY:= Y - Circles(N+1);
if DX*DX + DY*DY <= Circles(N+2) then
[Cnt1:= Cnt1+1; quit];
N:= N+2;
];
quit;
];
Cnt2:= Cnt2+1;
X:= X + Del;
until X >= MaxX;
Y:= Y + Del;
until Y >= MaxY;
Area:= (MaxX-MinX) * (MaxY-MinY); \of bounding box
Area:= float(Cnt1)/float(Cnt2) * Area; \of circles
RlOut(0, Area);
]</syntaxhighlight>
{{out}}
<pre>
21.56188
</pre>
=={{header|zkl}}==
The circle data is stored in a file, just a copy/paste of the task data.
{{trans|Python}}
<syntaxhighlight lang="zkl">circles:=File("circles.txt").pump(List,'wrap(line){
line.split().apply("toFloat") // L(x,y,r)
});
# compute the bounding box of the circles
x_min:=(0.0).min(circles.apply(fcn([(x,y,r)]){ x - r })); // (0) not used, just the list of numbers
x_max:=(0.0).max(circles.apply(fcn([(x,y,r)]){ x + r }));
y_min:=(0.0).min(circles.apply(fcn([(x,y,r)]){ y - r }));
y_max:=(0.0).max(circles.apply(fcn([(x,y,r)]){ y + r }));
box_side:=500;
dx:=(x_max - x_min)/box_side;
dy:=(y_max - y_min)/box_side;
count:=0;
foreach r in (box_side){
y:=y_min + dy*r;
foreach c in (box_side){
x:=x_min + dx*c;
count+=circles.filter1('wrap([(cx,cy,cr)]){
x-=cx; y-=cy;
x*x + y*y <= cr*cr
}).toBool(); // -->False|L(x,y,z), L(x,y,r).toBool()-->True,
}
}
println("Approximated area: ", dx*dy*count);</syntaxhighlight>
{{out}}
<pre>Approximated area: 21.5616</pre>
|