Total circles area: Difference between revisions
Content added Content deleted
m (→{{header|C}}: reduce unnecessary comparisons) |
(→{{header|C}}: reduce globals; speed; cropped data list) |
||
Line 166: | Line 166: | ||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <math.h> |
#include <math.h> |
||
#include <stdlib.h> |
|||
typedef double F; |
typedef double F; |
||
typedef struct { F x, y, r, r2, y0, y1; } circle; |
typedef struct { F x, y, r, r2, y0, y1; } circle; |
||
circle circles[] = { |
circle circles[] = { |
||
{ 1.6417233788, 1.6121789534, 0.0848270516}, |
{ 1.6417233788, 1.6121789534, 0.0848270516},... |
||
/* data snipped for space, copy from previous example */ |
|||
{-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 min(F a, F b) { return a < b ? a : b; } |
||
Line 202: | Line 181: | ||
typedef struct { F x0, x1; } sect_t; |
typedef struct { F x0, x1; } sect_t; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
F spans(circle *c, int n_circs, F ymin, F step, F ymax) |
F spans(circle *c, int n_circs, F ymin, F step, F ymax) |
||
{ |
{ |
||
F y, total = 0; |
F y, total = 0; |
||
int i, j, n, row = 1 + ceil((ymax - ymin) / step); |
int i, j, n, row = 1 + ceil((ymax - ymin) / step); |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
inline void swap_c(int i, int j) { |
inline void swap_c(int i, int j) { |
||
Line 217: | Line 196: | ||
cc = c[i], c[i] = c[j], c[j] = cc; |
cc = c[i], c[i] = c[j], c[j] = cc; |
||
} |
} |
||
for (i = 0; i < n_circs; i++) |
|||
for (j = i + 1; j < n_circs; j++) |
|||
if (c[i].y1 < c[j].y1) swap_c(i, j); |
|||
while (row--) { |
while (row--) { |
||
Line 222: | Line 205: | ||
for (n = n_circs, i = 0; i < n; ) { |
for (n = n_circs, i = 0; i < n; ) { |
||
if (y >= c[i].y1) |
if (y >= c[i].y1) n = i; |
||
else if (y <= c[i].y0) { |
else if (y <= c[i].y0) { |
||
circle cc = c[i]; |
|||
for (j = i + 1; j < n_circs; j++) c[j-1] = c[j]; |
|||
c[--n_circs] = cc; |
|||
--n; |
--n; |
||
} else { |
} else { |
||
Line 255: | Line 240: | ||
} |
} |
||
} |
} |
||
free(sect); |
|||
return total; |
return total; |
||
} |
} |
||
Line 282: | Line 268: | ||
int s = 1 << 20; // Definitely overkill. Definitely. |
int s = 1 << 20; // Definitely overkill. Definitely. |
||
printf("area = %.10f at\t%d scanlines\n", |
printf("area = %.10f at\t%d scanlines\n", |
||
spans(circles, n_circs, floor(miny * s) / s, 1./s, maxy) / s, |
spans(circles, n_circs, floor(miny * s) / s, 1./s, maxy) / s, |
||
(int)((maxy - floor(miny * s) / s) * s)); |
(int)((maxy - floor(miny * s) / s) * s)); |