in reply to Creating a circle in a data structure

Instead of going round the circle, it may be easier to iterate over all values in one direction, i.e. something like:

foreach $ydist ( 0..$radius ) {
  # using the formula:
  # xdist*xdist + ydist*ydist = radius*radius
  $xdist = int(sqrt( $radius*$radius - $ydist*$ydist));

  # Take advantage of symmetry to plot 4 points at once
  # (for circle outline)
  $circle{$x_center-$xdist}{$y_center-$ydist}++;
  $circle{$x_center+$xdist}{$y_center-$ydist}++;
  $circle{$x_center-$xdist}{$y_center+$ydist}++;
  $circle{$x_center+$xdist}{$y_center+$ydist}++;

  # Or to fill up the whole disc...
  foreach $x ( $x_center-$xdist .. $x_center+$xdist ) {
    $circle{$x}{$y_center-$ydist}++;
    $circle{$x}{$y_center+$ydist}++;
  }
}

[download]

Of course this assumes you're dealing with a grid of integers. Right now it also counts every point on the axis twice but that's easy enough to fix.

Replies are listed 'Best First'.
Re^2: Creating a circle in a data structure
by Skeeve (Parson) on May 28, 2007 at 08:08 UTC
    You can omit the square root if you compare to the square of the radius. I think one will get a big speed improvement from this.
    s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%
    +.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e
[reply]
[d/l]
[select]
Re^2: Creating a circle in a data structure
by AK108 (Friar) on May 28, 2007 at 20:17 UTC
    When using the whole disc, it works nicely. The individual points do not work, unfortunately.

    I can use the whole disc method, but I need to be able to calculate the distance from the center of the circle. I've tried many formulas, and some look close (working for x values or y values), but nothing actually works.

[reply]

      Yes you're right. To complete the outline you have to connect each point to the previous point. Something like this:

      $prevdist = 0;

foreach $ydist ( 0..$radius ) {
  # using the formula:
  # xdist*xdist + ydist*ydist = radius*radius
  $newxdist = int(sqrt( $radius*$radius - $ydist*$ydist));

  # Take advantage of symmetry to plot 4 lines at once
  # (for circle outline, draw a line from the previous
  # point to the new one)
  foreach $xdist ($prevdist..$newxdist) {
    $circle{$x_center-$xdist}{$y_center-$ydist}++;
    $circle{$x_center+$xdist}{$y_center-$ydist}++;
    $circle{$x_center-$xdist}{$y_center+$ydist}++;
    $circle{$x_center+$xdist}{$y_center+$ydist}++;
  }

  $prevdist = $newxdist;
}

      [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom