AK108 has asked for the
wisdom of the Perl Monks concerning the following question:
I am working on an online game. Within this game, almost every action will need to generate a circle to see what is within that area. Some actions will need to modify a circular area on the map.
The problem I'm having is generating the circle in the Perl data structure. Not only does it miss certain points on larger circles, my code is fairly slow.
My basic algorithm for drawing a "ring" of a circle is this:
for my $i (0 .. $radius ** 2) { # See "1" below
# Rounded values, see "2" below
my $x_val = int($radius * cos($i) + $center_x + 0.5);
my $y_val = int($radius * sin($i) + $center_y + 0.5);
$circle{$x_val} = {};
$curpass{$x_val} = {};
$circle{$x_val}{$y_val} = 0;
$curpass{$x_val}{$y_val} = 0;
unless($curpass{$x_val}{$y_val}) {
$circle{$x_val}{$y_val}++;
$curpass{$x_val}{$y_val}++;
}
}
A few notes about this:
 If I change the $radius ** 2, I can trade speed for accuracy. I thought something like ($radius + 1) ** 2 would catch every possible point, but not even close.
 If I remove the rounding, I miss fewer points within the circle. However, the circle becomes lopsided.
I wrote a CGI script to visualize this which makes the flaws very visible.
#!/usr/bin/perl
use strict;
use warnings;
use CGI ();
my $q = CGI>new;
# use CGI::Carp 'fatalsToBrowser';
my %circle;
my $prev_data;
# Read the previous circles
my @prev_circles;
{
my @x_vals = $q>param('x');
my @y_vals = $q>param('y');
my @r_vals = $q>param('r');
for(my $i = 0; $i < @r_vals; $i++) {
foreach ($r_vals[$i], $x_vals[$i], $y_vals[$i]) {die "All valu
+es must be positive integers!\n" if /[^\d\.]/}
push(@prev_circles, {
r => $r_vals[$i],
x => $x_vals[$i],
y => $y_vals[$i],
});
}
}
# 'Draw' the circle in the hash.
foreach my $circle (@prev_circles) {
my $rmax = $circle>{'r'};
my $center_x = $circle>{'x'};
my $center_y = $circle>{'y'};
$prev_data .= qq~<input type="hidden" name="r" value="$rmax" /><in
+put type="hidden" name="x" value="$center_x" /><input type="hidden" n
+ame="y" value="$center_y" />\n~;
my %curpass;
for my $radius (0 .. $rmax) {
for my $i (0 .. $radius ** 2) {
# Rounded values
my $x_val = int($radius * cos($i) + $center_x + 0.5);
my $y_val = int($radius * sin($i) + $center_y + 0.5);
$circle{$x_val} = {};
$curpass{$x_val} = {};
$circle{$x_val}{$y_val} = 0;
$curpass{$x_val}{$y_val} = 0;
unless($curpass{$x_val}{$y_val}) {
$circle{$x_val}{$y_val}++;
$curpass{$x_val}{$y_val}++;
}
}
}
}
my $output = q~<html>
<head>
<title>A circle as a table</title>
<style type="text/css">
body {background: #888;}
.c1 {background: #000;}
.c2 {background: #008;}
.c3 {background: #00f;}
.c4 {background: #08f;}
.c5 {background: #0ff;}
.c6 {background: #8ff;}
.c7 {background: #fff;}
</style>
</head>
<body>
<table>
~;
foreach my $rowid (0 .. max(keys %circle)) {
my $row = $circle{$rowid};
$output .= "<tr>";
foreach my $columnid (0 .. max(keys %{$row})) {
my $column = $row>{$columnid};
my $class = '';
$column = 7 if $column > 7;
$class = qq~ class="c$column"~ if $column;
$output .= qq~<td$class></td>~;
}
$output .= "</tr>\n";
}
$output .= qq~</table>
<br />
<br />
<form method="post" >
$prev_data
<br />New circle's radius: <input type="text" size="10" name="r" value
+="20" />
<br />New circle's center: (<input type="text" size="10" name="x" valu
+e="50" />, <input type="text" size="10" name="y" value="50" />)
<br /><input type="submit" />
</form>
</body>
</html>~;
print $q>header, $output;
sub max {
my $max = 0;
foreach (@_) {$max = $_ if $_ > $max}
return $max;
}
When running this, circles with a radius larger than 100 show the flaws very well. The circle is more ovular in Internet Explorer. Also note that this generates a large amount of HTML which can make a browser unstable. I won't be using the HTML generating portion; it's just a nice way to visualize how this would affect a data structure. I intentionally cut off any negative coordinates, and the coordinates aren't real graph coordinates. But that's not relevant to my problem.
I would greatly appreciate any ideas on how to improve this algorithm, or any other ways to approach this. I need to be able to modify any coordinate within the circle, since any other circle could overlap it (as this example shows if you overlap two circles).
Re: Creating a circle in a data structure
by chromatic (Archbishop) on May 28, 2007 at 06:33 UTC

If you have a list of potentially interesting items, you can compare their distance from the center of the circle to the radius of the circle to see if they're in the circle.
If you have a clever list of potentially interesting items, you can probably cull that further by removing objects that are obviously too far away.
 [reply] 
Re: Creating a circle in a data structure
by toma (Vicar) on May 28, 2007 at 07:30 UTC

To learn about the 'clever list' that chromatic refers to, check 'binary space partitioning' on Wikipedia.
If you intend to draw circles and you get ovals, check to make sure that your pixels are square, and that the X and Y axes of your graphics system have the same scale factors. To check this, draw a square first. That way you won't have trigonometric problems or rounding problems while you verify your graphical coordinate system.
It should work perfectly the first time!  toma
 [reply] 

 [reply] 
Re: Creating a circle in a data structure
by Crackers2 (Parson) on May 28, 2007 at 07:21 UTC

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}++;
}
}
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.
 [reply] [d/l] 

 [reply] [d/l] [select] 

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] 

$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;
}
 [reply] [d/l] 
Re: Creating a circle in a data structure
by BrowserUk (Pope) on May 28, 2007 at 11:49 UTC

 [reply] 

I'll check this out soon, but I need to fight through converting it to Perl from C. This seems similar to Crackers2's method; hopefully it won't have the flaws.
 [reply] 

Try this. I'm not certain it's exactly equivalent to your original as I had some trouble understanding your 'drawing' code, but it's not far off. Your use of %curpass confused me as it seems unnecessary.
You should be able to relate the sub genEndPoints() to the code at the end of the page I linked above. Rather than generating all the points on the circumference for all integer radii upto max radius, it generates only the endpoints (8 at a time using symmetry), of the raster lines required to 'fill' the circle and then draws those lines. Let me know if anything is unclear.
#!/usr/bin/perl
use strict;
use warnings;
use CGI ();
my $q = CGI>new;
# use CGI::Carp 'fatalsToBrowser';
my %circle;
my $prev_data;
# Read the previous circles
my @prev_circles;
{
my @x_vals = $q>param('x');
my @y_vals = $q>param('y');
my @r_vals = $q>param('r');
for(my $i = 0; $i < @r_vals; $i++) {
foreach ($r_vals[$i], $x_vals[$i], $y_vals[$i]) {
die "All values must be positive integers!\n" if /[^\d\.]/
}
push(@prev_circles, {
r => $r_vals[$i],
x => $x_vals[$i],
y => $y_vals[$i],
});
}
}
sub genEndPoints {
my( $radius, $xCenter, $yCenter ) = @_;
my %endPoints;
my( $x, $y, $p ) = ( 0, $radius, 1  $radius );
$endPoints{ $yCenter } = [ $xCenter  $radius, $xCenter + $radius
+ ];
while( $x < $y ) {
$x++;
if( $p < 0 ) {
$p += 2 * $x + 1;
} else {
$y;
$p += 2 * ( $x  $y + 1 );
}
$endPoints{ $yCenter  $y } = [ $xCenter  $x, $xCenter + $x
+];
$endPoints{ $yCenter + $y } = [ $xCenter  $x, $xCenter + $x
+];
$endPoints{ $yCenter  $x } = [ $xCenter  $y, $xCenter + $y
+];
$endPoints{ $yCenter + $x } = [ $xCenter  $y, $xCenter + $y
+];
}
return \%endPoints;
}
# 'Draw' the circle in the hash.
foreach my $circle (@prev_circles) {
my $rmax = $circle>{'r'};
my $center_x = $circle>{'x'};
my $center_y = $circle>{'y'};
$prev_data .= qq~
<input type="hidden" name="r" value="$rmax" />
<input type="hidden" name="x" value="$center_x" />
<input type="hidden" name="y" value="$center_y" />\n
~;
my $endPoints = genEndPoints( $rmax, $center_x, $center_y );
for my $y ( keys %{ $endPoints } ) {
my( $startX, $endX ) = @{ $endPoints>{ $y } };
for my $x ( $startX .. $endX ) {
$circle{ $y }{ $x }++;
}
}
}
my $output = q~<html>
<head>
<title>A circle as a table</title>
<style type="text/css">
body {background: #888;}
.c1 {background: #000;}
.c2 {background: #008;}
.c3 {background: #00f;}
.c4 {background: #08f;}
.c5 {background: #0ff;}
.c6 {background: #8ff;}
.c7 {background: #fff;}
</style>
</head>
<body>
<table>
~;
foreach my $rowid (0 .. max(keys %circle)) {
my $row = $circle{$rowid};
$output .= "<tr>";
foreach my $columnid (0 .. max(keys %{$row})) {
my $column = $row>{$columnid};
my $class = '';
$column = 7 if $column > 7;
$class = qq~ class="c$column"~ if $column;
$output .= qq~<td$class></td>~;
}
$output .= "</tr>\n";
}
$output .= qq~
</table>
<br />
<br />
<form method="post" >
$prev_data
<br />New circle's radius: <input type="text" size="10" name="r" value
+="20" />
<br />New circle's center: (<input type="text" size="10" name="x" valu
+e="50" />,
<input type="text" size="10" name="y" value="50" />)
<br /><input type="submit" />
</form>
</body>
</html>
~;
print $q>header, $output;
sub max {
my $max = 0;
foreach (@_) { $max = $_ if $_ > $max; }
return $max;
}
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
 [reply] [d/l] [select] 



Re: Creating a circle in a data structure
by lyklev (Pilgrim) on May 29, 2007 at 16:08 UTC

The first problem I see here is with the $radius ** 2; you probably meant 2 * pi * $radius, which scales linearly with the radius. You will miss more points, but there is no guarantee that you can fix it using a square (that is for the area of the circle).
 [reply] 

