A one-liner with PDL's rvals:

pdl> p rvals(19,19,{Centre=>[5,4]}) <= 6

[
 [0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
 [0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
]
[download]

Edit: I know what you are thinking: what a dumb one-liner. What if frame-buffer is 1000x1000 px, but illuminated area just 10x10? Why calculate a million distances when clearly we can limit calculations to a small viewport (bounding box)? Ok, then:

pdl> $frame = zeroes 19,19
pdl> ($x,$y,$r,$xmax,$ymax) = (5,4,6,dims $frame)
pdl>
pdl> use List::Util
pdl> *min_ = \*List::Util::min
pdl> *max_ = \*List::Util::max
pdl>
pdl> ($llx,$lly,$urx,$ury,$cx,$cy) = (
>     max_(0,$x-$r),
>     max_(0,$y-$r),
>     min_($xmax,$x+$r),
>     min_($ymax,$y+$r),
>     min_($r,$x),
>     min_($r,$y))
pdl>
pdl> $viewport = $frame($llx:$urx, $lly:$ury)
pdl>
pdl> $viewport .= $viewport-> rvals({
>     Center  => [$cx,$cy],
>     Squared => 1
> }) <= $r*$r
pdl>
pdl> p $frame

[
 [0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
 [0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
]

pdl>
[download]

Note two different kinds of assignment, for data-flow to work in PDL. This nice exercise reminded me when taking a square root multiple times was a no-no (was that so for /[2-4]87/? I think nowadays it's single CPU cycle anyway, no need to optimize (-?)), hence I used the rvals's option (but it's there for a reason, isn't it). I hope I didn't mess anything this time of night and it works for border cases, too.

You, my friend, are a steely-eyed missile monk!

Keep that PDL train steaming along (seems like I can only upvote you _once_, pfft)

Ea

Sometimes I can think of 6 impossible LDAP attributes before breakfast.

Mojoconf was great!

Great minds think alike! I was just about to look into using PDL, but you beat me to it.

Try this (some slight changes to see a better circle)

#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw( max min );

my $max = 40;

my @aoa = map { [ ( 'o' ) x ($max + 1) ] } 0..$max  ;

display( @aoa );

# @to_change will contain [y1,x1],[y2,x2]...
#my @to_change = illuminate( 5, 4, 6 );
my @to_change = illuminate( $max >> 1, $max >> 1, $max - 2 >> 1 );

print "\n";
$aoa[$_->[0]][$_->[1]] = 'x' for @to_change;
display( @aoa );

sub illuminate
  {
  my @to_change;
  my $center_r = shift;
  my $center_c = shift;
  my $radius     = shift;
  #...
  for my $row ( 0 .. $#aoa )
    {
    my $delta_x = eval { int sqrt $radius ** 2 - ($center_r - $row) **
+ 2 };
    if( defined $delta_x )
      {
      my $low = max 0, $center_c - $delta_x;
      my $high = min $#{ $aoa[$row] }, $center_c + $delta_x;
      push @to_change, map [ $row, $_ ], $low .. $high;
      }
    }
  return @to_change;
  }

sub display
  {
  foreach my $row ( @_ )
    {
    foreach my $col ( @$row )
      {
      print $col;
      }
    print "\n"
    }
  }
[download]

Fantastic!

I suppose i can optimize it using for my $row ( $center_r - $radius .. $center_r + $radius ) instead of processing the whole AoA

I never seen >> before: seems a int( $_ / 2) operator.. thanks for this too!

L*

update

I adapted to return a hash instead. I feel happy with it. Thanks again

#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( max min );

my $max = 19;                                       #from OP  
my @aoa = map { [ ( 'o' ) x ($max + 1) ] } 0..$max; #from OP


my %illu = illuminate( 0,0,12 );
display(@aoa);

%illu = illuminate( 0,10,4 );
display(@aoa);

%illu = illuminate( 10,10,6 );
display(@aoa);

%illu = illuminate( 10,0,5.5 );
display(@aoa);

sub illuminate{    
    my $center_r = shift;
    my $center_c = shift;
    my $radius     = shift;
    my %ret;
    
    foreach my $row ( $center_r - $radius .. $center_r + $radius ){
        my $delta_x = $radius ** 2 - ($center_r - $row) ** 2;
        if( $delta_x >= 0 ){
                
                $delta_x = int sqrt $delta_x;            
                my $low = max 0, $center_c - $delta_x;
                my $high = min $#{ $aoa[$row] }, $center_c + $delta_x;
                map { $ret{ $row.'_'.$_ }++ } $low .. $high;
          }
    }
       return %ret;
}

sub display{
    print "\n";
    foreach my $row ( 0..$#aoa ){        
        foreach my $col ( 0..$#{$aoa[$row]} ){
            print  $illu{$row.'_'.$col} ? ' ' : $aoa[$row][$col] ;    
+        
        }
    print "\n"
    }
}
[download]

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

> I never seen >> before

Bitwise shift see perlop#Shift-Operators

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

Cool! But that eval poked my eye.

The following can potentially save on some sqrt's too:

    my $delta_x = $radius ** 2 - ($center_r - $row) ** 2;
    if( $delta_x >= 0 ){
       $delta_x = int sqrt $delta_x;
       ...
[download]

bw, bliako

you can also get rid of both squares

x˛ = r˛-y˛

now increment y2=y+1

x2˛ = r˛-(y+1)˛

x2˛ = r˛-y˛ - 2y - 1

x2˛ = x˛ - 2y -1

I'm too tired to get rid of the sqrt too now :)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

Just having some fun :)

Nothing wrong with having a little fun in a "proof-of-concept" example, is there?
It's not like it's production code :)

In computer graphics in the age before specialized graphic processors they used very fast algorithms giving you the edges of a circle for each line and filled that line between the edges.

Since the second level array in your AoA you just need the indices of left and right border. And an array slice will fill it effectively.

@line[$left..$right] = ('x') X ($right-$left)

You'll also need a max and min against the start of the borders of your array.

I don't think a highly optimized algorithm to calculate the border is necessary, basic sinus and cosinus should be fast enough here.

HTH! :)

Edit

After thinking it through you don't even need sinus. Pythagoras should do already.

#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/floor/;

my $max = 19;                                       #from OP  
my @aoa = map { [ ( 'o' ) x ($max + 1) ] } 0..$max; #from OP

my $max_x_grid = @{$aoa[0]};
my $max_xi = $max_x_grid-1;   #range 0..$max_xi
my $max_y_grid = @aoa;
my $max_yi = $max_y_grid-1;   #range 0..$max_yi

print "grid size is $max_x_grid x $max_y_grid\n";
print "max x index is $max_xi, max y index is $max_yi (zero based indi
+cies)\n";

# Choice of coordinate system:
#   Lower left hand corner of grid is (0,0)
#   This could be upper left hand corner or other point
#   But with this choice:
#          no negative x or y indicies are allowed

my ($circle_x, $circle_y) =(8,9);   #Center of Circle
print "Circle Center = ($circle_x, $circle_y)\n";
my $circle_radius = 5.6;
print "Circle radius in fractions: $circle_radius\n";
my $max_radius_on_axis = floor($circle_radius); #"round down" is part 
+of spec


my $top_y_index    = $circle_y + $max_radius_on_axis;
my $bottom_y_index = $circle_y - $max_radius_on_axis;
my $left_x_index   = $circle_x - $max_radius_on_axis;
my $right_x_index  = $circle_x + $max_radius_on_axis;

print "imagine a box containing the circle using tangential lines:\n";
print "coordinates top of box:    ($left_x_index,$top_y_index) to ($ri
+ght_x_index,$top_y_index)\n";
print "coordinates bottom of box:($left_x_index,$bottom_y_index) to ($
+right_x_index,$bottom_y_index)\n";
print "the circle is contained within the above box!\n";

# Circle in cartesian coordinates
#(x - a)**2 + (y - b)**2 = r**2 where a and b are the coordinates of t
+he center (a, b) and r is the radius.

for (my $y=$top_y_index; $y >= $bottom_y_index; $y--)
{
   for (my $x=$left_x_index; $x <= $right_x_index; $x++)
   {
      $aoa[$x][$y] = 'X' if ( (($x-$circle_x)**2 + ($y-$circle_y)**2 <
+= ($circle_radius**2) )
                            and $x >=0 and $y >=0)
   }
}

foreach my $row_ref ( @aoa)
{
    print "@$row_ref\n";   
}
    
__END__
grid size is 20 x 20
max x index is 19, max y index is 19 (zero based indicies)
Circle Center = (8, 9)
Circle radius in fractions: 5.6
imagine a box containing the circle using tangential lines:
coordinates top of box:    (3,14) to (13,14)
coordinates bottom of box:(3,4) to (13,4)
the circle is contained within the above box!
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o X X X X X o o o o o o o o
o o o o o o X X X X X X X o o o o o o o
o o o o o X X X X X X X X X o o o o o o
o o o o X X X X X X X X X X X o o o o o
o o o o X X X X X X X X X X X o o o o o
o o o o X X X X X X X X X X X o o o o o
o o o o X X X X X X X X X X X o o o o o
o o o o X X X X X X X X X X X o o o o o
o o o o o X X X X X X X X X o o o o o o
o o o o o o X X X X X X X o o o o o o o
o o o o o o o X X X X X o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o
[download]

more points, calling sqrt() is going to be expensive. Something like x**2 is a lot cheaper and may or may not be more expensive than x*x. This may blow you away (it did me), but now a integer multiplication like x*1234 is basically the same performance in integer situations like x+124. Most of the transistors in the typical CPU (like Intel) go for math. Math, especially floating point math is not nearly as expensive as it used to be. Fixed point math is very fast now.

very nice, thanks for the code and for the patience Marshall,

I noticed your code get some Use of uninitialized value in join or string if the circle goes outside of the AoA for high values of row.

I fixed it with a condition more in the nested for loop:

$aoa[$x][$y] = 'x' if ( (($x-$circle_x)**2 + ($y-$circle_y)**2 <= ($ci
+rcle_radius**2) )
                             # and $x >=0 and $y >=0 )                
+            
                               and $x >=0 and $y >=0 and $x <= $max  )
[download]

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Thanks for the correction! I guess there is a similar problem in the y direction. I like seeing bug reports like this because it means that somebody actually ran the code! I guess some adjustment of the loop conditional is also possible to not even consider points outside of the input array.

I very seldom use $array[][] syntax because Perl is so cool at working with references to rows. I suppose some tricky splice() statement could be used, but my brain started hurting and I went for something straightforward. Glad to have been of help.

Update: Here is modified version without extraneous prints and better control over loop condition:

Read more... (4 kB)

oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
oooooooooooooooooooo
[download]

Update: Just as a wild thought, maybe this is a graphical representation of a target grid? You are going to drop a bomb at a particular coordinate in this grid with a blast radius of X. All of the affected "o's" should turn into "x's". Is that analogy right?

> All of the affected "o's" should turn into "x's". Is that analogy right?

Yes! The analogy is a bit crude but describes well what I intended.

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Ok, "crude" works for me as long as it is descriptive!

In cartesian coordinates, The equation of the points on a circle is (x − a)**2 + (y − b)**2 = r**2 where a and b are the coordinates of the center (a, b) and r is the radius. Points within the circle are solutions where x,y result in <= r**2. So this question is given a grid of Horizontal x Vertical discrete points, an x,y "bomb target point" and a radius. The idea is to "color", i.e. fill-in the circle or change all elements to x that are within the circle. The resulting "picture" will look more and more like a smooth circle as the number of elements in the grid increases.

This sort of thing has to happen all the time in video games and I'm sure there are very good algorithms for this. To write my own code, I need to think some more. But, thanks for making the requirement more clear!

Ok, "crude" works for me as long as it is descriptive!

In cartesian coordinates, The equation of the points on a circle is (x -a)**2 + (y -b)**2 = r**2 where a and b are the coordinates of the center (a, b) and r is the radius. Points within the circle are solutions where x,y result in <= r**2. So this question is given a grid of Horizontal x Vertical discrete points, an x,y "bomb target point" and a radius. The idea is to "color", i.e. fill-in the circle or change all elements to x that are within the circle. The resulting "picture" will look more and more like a smooth circle as the number of elements in the grid increases.

This sort of thing has to happen all the time in video games and I'm sure there are very good algorithms for this. To write my own code, I need to think some more. But, thanks for making the requirement more clear!

This is one time I'd advocate not re-inventing the wheel. (Depends on how you are using your results.)

Graphics packages are contain very optimised fast circle drawing algorithms coded in C. So, define your "array" as a 2-color (BW) image and then have it draw the circles.

GD for example, can draw thousands of circles per second.

As requested offline, an example drawing 150,000 random size circles at random positions in just over 1 second (in simple Perl):

#! perl -slw
use strict;
use GD;
use Time::HiRes qw[ time ];

sub rgb2n{ unpack 'N', pack 'CCCC', 0, @_ }


my $im = GD::Image->new( 1920, 1080, 1 );

my $start =  time;
for( 1 .. 150000 ) {
    $im->filledEllipse( rand( 1920 ), rand( 1080 ), (10+rand(2)) x 2, 
+rgb2n( (255) x 3 ));
}

printf "Took %.9f seconds\n", time() - $start;

open PNG, '>:raw', 'junk.png' or die $!;
printf PNG "%s", $im->png;
close PNG;

system 1, 'junk.png';

__END__
C:\test>junk71
Took 1.036067009 seconds
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

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". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit

Probably this is good for further inspiration. See also. Best regards, Karl

Just for fun, here's a 2-step method that fills the inner square first and then conditionally computes a quadrant outside that but inside the outer square (and copies this to the other quadrants as it goes along). The inner square is the largest square that fits entirely inside the circle whereas the outer square is the smallest square that entirely encompasses the circle. It's not very Perlish and it doesn't do bounds checking which is why you can see part of the circle on the opposite side if you display the results.

sub illuminate{
    my $centre_row = shift;
    my $centre_col = shift;
    my $radius     = shift;
    my $insq       = int ($radius / sqrt (2));
    my @ans;

    # inner square
    for my $i ($centre_row - $insq .. $centre_row + $insq) {
        for my $j ($centre_col - $insq .. $centre_col + $insq) {
            push @ans, [$i, $j];
        }
    }

    # outer square
    my $r2 = $radius * $radius;
    for my $i (0 .. $radius) {
        for my $j (0 .. $radius) {
            # Skip already-done inner square
            next if $i < $insq and $j < $insq;
            if ($i * $i + $j * $j < $r2) {
                push @ans,
                    [$centre_row + $i, $centre_col + $j],
                    [$centre_row - $i, $centre_col + $j],
                    [$centre_row + $i, $centre_col - $j],
                    [$centre_row - $i, $centre_col - $j];
            }
        }
    }
    return @ans;
}
[download]

(I changed the spelling of your variables since as a native speaker of British English it is almost impossible for me to type "center" consistently.)