Anonymous user
Total circles area: Difference between revisions
→{{header|C}}: fast scanline method
(Undone part of the changes in the Haskell analytical solution (because it didn't compile)) |
(→{{header|C}}: fast scanline method) |
||
Line 162:
21.5637 +/- 0.0004 (536870912 samples)
21.5637 +/- 0.0003 (1073741824 samples)</pre>
Scanline method. Does 5 million-ish scanlines in about a second, result should be accurate to maybe 10 decimal points.
<lang c>#include <stdio.h>
#include <math.h>
typedef double F;
typedef struct { F x, y, r, r2, y0, y1; } circle;
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}};
inline F min(F a, F b) { return a < b ? a : b; }
inline F max(F a, F b) { return a > b ? a : b; }
inline F sq(F x) { return x * x; }
inline F dist(F x, F y, F x1, F y1) { return sqrt(sq(x - x1) + sq(y - y1)); }
typedef struct { F x0, x1; } sect_t;
sect_t sect[sizeof(circles) / sizeof(circle)];
F spans(circle *c, int n_circs, F ymin, F step, F ymax)
{
F y, total = 0;
int i, j, n, row = 1 + ceil((ymax - ymin) / step);
circle cc;
sect_t ss;
while (row--) {
y = ymin + step * row; // could probably do "y -= step"; not sure
for (n = n_circs, i = 0; i < n; ) {
if (y <= c[i].y0 || y >= c[i].y1)
cc = c[i], c[i] = c[--n], c[n] = cc;
else {
F dx = sqrt(c[i].r2 - sq(y - c[i].y));
sect[i].x0 = c[i].x - dx;
sect[i].x1 = c[i].x + dx;
i++;
}
}
if (!n) continue;
for (i = n; i--; ) { // Bubble sort. Important.
int swapped = 0;
for (j = 0; j < i; j++)
if (sect[j].x0 > sect[j+1].x0) {
ss = sect[j], sect[j] = sect[j+1], sect[j+1] = ss;
cc = c[j], c[j] = c[j+1], c[j+1] = cc;
swapped = 1;
}
if (!swapped) break;
}
sect_t *cur = sect;
total += cur->x1 - cur->x0;
for (i = 1; i < n; i++) {
if (sect[i].x1 <= cur->x1) continue;
total += sect[i].x1 - max(sect[i].x0, cur->x1);
cur = sect + i;
}
}
return total;
}
int main(void)
{
int i, n_circs = sizeof(circles) / sizeof(circle);
F miny = INFINITY, maxy = -INFINITY;
for (i = 0; i < n_circs; i++) {
miny = min(circles[i].y0, miny);
maxy = max(circles[i].y1, maxy);
circles[i].r2 = sq(circles[i].r);
circles[i].y0 = circles[i].y - circles[i].r;
circles[i].y1 = circles[i].y + circles[i].r;
}
circle *c1, *c2;
for (c1 = circles + n_circs; c1-- > circles; )
for (c2 = circles + n_circs; c2-- > circles; )
// Remove c1 if it's inside c2. Helps, not important.
if (c1 != c2 && dist(c1->x, c1->y, c2->x, c2->y) + c1->r <= c2->r) {
*c1 = circles[--n_circs];
break;
}
int s = 1 << 20; // Definitely overkill. Definitely.
printf("area = %.10f at\t%d scanlines\n",
spans(circles, n_circs, floor(miny * s) / s, 1./s, maxy) / s,
(int)((maxy - floor(miny * s) / s) * s));
return 0;
}</lang>
{{out}}
area = 21.5650366037 at 5637290 scanlines
=={{header|D}}==
| |||