/* (p) Jan-Mark Wams
** Squaring The Circle
**
** This is not truely a solution to squaring the circle, but a
** calculation of howmany steps it takes to fill a circle with
** rectangles if the rectangles are confined within a bigger circle.
**
** This algorithm is te result of five minutes of thinking and ten
** minutes of hacking. I don't think it gives an optimal solution for
** minimizing the number of rectangles, I am no KochaĆski. I just
** needed to see if it is feasable to write a round loop function with
** a simple set of rectangles. In my best ASCI art:
** ,,,,,,,,,,,,,
** ,,, ______O______ ,,,
** ,,, | ''''''' A| ,,,
** ,,, ____|'' ''|____,,,
** ,, | '''| |'''B| ,,
** , __|' | | '|__ ,
** , | '| | | |'C| ,
** , |' | | | | '| ,
** ' , | | | | , '
** ' |, | | | | ,| '
** ' | ,| | | |, | '
** ' --|, | | ,|-- '
** '' | ,, | | ,, | ''
** ''' ----|,, ,,|---- '''
** ''' | ,,,,,,, | '''
** ''' ------------- '''
** '''''''''''''
** Squint and you will see two concentric circles and five
** rectangles. Think and you will see three (largely overlapping
** rectangles). Since covering the inner circle with rectangles this
** way is higly point semetric calculating a 45 degree segment would
** suffice. However since we have to round the program calculates a 90
** degree angle.
**
** The algorith starts at point O and calculates A, B, C, ...
**
** Note that a real good program would actually take antialiassing
** into account which might lower the number of rectangles.
**
** If you see an easy way to do that or any other improvement, go for
** it!
*/
#include
#include
int calc_print_n(int print, int border, int outer_r)
{
int inner_r = outer_r - border;
int x = 0;
int y;
int new_x;
int n_rectangles = 0;
while (x < inner_r) {
/* Calc y to touch of just peek through the inner circle. */
y = ceil(sqrt((inner_r * inner_r) - (x * x)));
/* Calc new new_x to just within or on the outer circle. */
new_x = floor(sqrt((outer_r * outer_r) - (y * y)));
/* Print the square. */
n_rectangles += 1;
if (print)
printf("[%d,%d],", new_x * 2, y * 2);
x = new_x;
}
return n_rectangles;
}
int main(int ac, char **av)
{
int border;
int min, r, max; /* Max always leads to n > 10. */
int n;
/* For borders 3 to 6 calc the maximum (outer) radius reachable with
** ten (overlapping) rectangles.
*/
for (border = 2; border < 12; border++) {
r = min = border * 15;
max = min * 2;
for(;;) {
n = calc_print_n(0, border, r);
if (max == r + 1 && n == 10) break;
if (n <= 10) { min = r; r = (r + max) / 2; }
else if (n > 10) { max = r; r = (r + min) / 2; }
}
printf("\nBorder %d, radius %d (ratio %f)\n[\n ",
border, r, (float)r/border);
(void)calc_print_n(1, border, r);
printf("\n]\n");
}
return 0;
}