perlquestion
AK108
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.
<p>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.</p>
<p>My basic algorithm for drawing a "ring" of a circle is this:</p>
<code> 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}++;
}
}</code>
A few notes about this:
<ol><li>If I change the <c>$radius ** 2</c>, I can trade speed for accuracy. I thought something like <c>($radius + 1) ** 2</c> would catch every possible point, but not even close.</li>
<li>If I remove the rounding, I miss fewer points within the circle. However, the circle becomes lopsided.</li></ol>
<p>I wrote a CGI script to visualize this which makes the flaws very visible.</p>
<readmore><code>#!/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],
});
}
}
# '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 %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" value="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;
}</code>
<p>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.</p></readmore>
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).