Creating a circle in a data structure

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}++;
            }
        }
[download]

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;
}
[download]

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).

Back to Seekers of Perl Wisdom