Total circles area: Difference between revisions
Added Algol 68
(New post using the scanline method, in addition to an existing post using the recursive subdivision of space method.) |
(Added Algol 68) |
||
| (13 intermediate revisions by 6 users not shown) | |||
Line 113:
<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>
Line 408 ⟶ 504:
{{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++">
Line 927 ⟶ 1,131:
</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}}==
Line 1,729 ⟶ 2,014:
<syntaxhighlight lang="java">
public class
/*
Line 1,854 ⟶ 2,139:
}
}</syntaxhighlight>
===Scanline Method===
Alternative example using the Scanline method.
<syntaxhighlight lang="java">
Line 1,860 ⟶ 2,146:
import java.util.List;
public final class
public static void main(String[] args) {
Line 2,079 ⟶ 2,365:
inside = 0
# For every point in my grid.
for x in
inside += any(r2 .> (x .- xc) .^ 2 + (y .- yc) .^ 2)
end
boxarea = (xmax - xmin) * (ymax - ymin)
Line 3,582 ⟶ 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}}==
Line 3,841 ⟶ 4,188:
{{libheader|Wren-math}}
Limited to 3000 boxes to finish in a reasonable time (about 25 seconds) with reasonable precision.
<syntaxhighlight lang="
import "./math" for Nums
var Circle = Tuple.create("Circle", ["x", "y", "r"])
Line 3,903 ⟶ 4,250:
{{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="
import "./math" for Nums
import "./sort" for Sort
var Point = Tuple.create("Point", ["x", "y"])
| |||