Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Creating a circle in a data structure

by AK108 (Friar)
on May 28, 2007 at 05:15 UTC ( [id://617793]=perlquestion: print w/replies, xml ) Need Help??

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:
  1. 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.
  2. 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).

Replies are listed 'Best First'.
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.

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

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

        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; }
Re: Creating a circle in a data structure
by BrowserUk (Patriarch) on May 28, 2007 at 11:49 UTC
      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.

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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://617793]
Front-paged by naikonta
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2024-03-28 23:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found