Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

circular area in a coordinates grid (AoA)

by Discipulus (Abbot)
on Mar 19, 2019 at 21:34 UTC ( #1231454=perlquestion: print w/replies, xml ) Need Help??

Discipulus has asked for the wisdom of the Perl Monks concerning the following question:

Hello monks,

I have an array of arrays full of o and, given the coordinates of one element and a radius I want to change all elements around the center into x

My AoA can be eventually big so I do not want to process every element of the AoA.

The sub ( illuminate in the example below ) must not complain if a point is outside of the AoA (for example giving a corner as vertex).

A pure perl solution will be the best, but also using modules will be ok.

Sorry if I only have the below sketch but I'm very scarce in trig and until now I can only figure to hardcode series of coordinates relative to the vertex (that is silly..)

use strict; use warnings; my $max = 19; my @aoa = map { [ ( 'o' ) x ($max + 1) ] } 0..$max ; display( @aoa ); # @to_change will contain [row1,col1],[row2,col2]... my @to_change = illuminate( 5, 4, 6 ); sub illuminate{ my $center_row = shift; my $center_col = shift; my $radius = shift; ... } sub display{ foreach my $row ( @_ ){ foreach my $col ( @$row ){ print $col; } print "\n" } }

Thanks

L*

PS the above code displays the AoA before the change: I want to be able to select into @to_change the serie of elements falling inside the circle.

minor changes to explain better

UPDATE June 24 2019 see also 2d field of view, vision algorithm in grid (ray casting)

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.

Replies are listed 'Best First'.
Re: circular area in a coordinates grid (AoA) (updated)
by vr (Deacon) on Mar 19, 2019 at 22:27 UTC

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

    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>

    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.

Re: circular area in a coordinates grid (AoA)
by tybalt89 (Parson) on Mar 19, 2019 at 22:16 UTC

    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" } }
      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" } }

      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.

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

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

Re: circular area in a coordinates grid (AoA)
by Marshall (Abbot) on Mar 20, 2019 at 01:42 UTC
    Ok, here is some simple code with an idea. Draw an imaginary box around the circle using tangents. The circle will be within that box. This avoids having to look at the entire @aoa, just look at the lines and the indices within those lines that could possibly have an 'x'. Improvements are certainly possible, but this is a "pure perl" solution whose approach might work fast enough depending upon what you are actually doing.
    #!/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
    update: yes I see that there is some mess up between my printouts of index numbers and size of array (the dreaded off by one)..I leave it to others for future improvements. Ok, I see the problem, post updated: the value from -- was used later in code, my $max_xi = $max_x_grid-1;   #range 0..$max_xi is better.

    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 )

      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:

Re: circular area in a coordinates grid (AoA)
by LanX (Archbishop) on Mar 19, 2019 at 22:18 UTC
    I understand your problem as a classic fill circle with pixels problem.

    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.

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

Re: circular area in a coordinates grid (AoA)
by Marshall (Abbot) on Mar 19, 2019 at 21:48 UTC
    I am quite confused as to the desired output. Your code produces:
    oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo oooooooooooooooooooo
    I don't understand what that means? There is a Math::Trig module that can deal with rectangular and spherical coordinates or 2 dimensional versions (x,y and polar,magnitude and angle). Sorry that I'm being dense, but I don't understand the requirement yet.

    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!

Re: circular area in a coordinates grid (AoA)
by BrowserUk (Pope) on Mar 22, 2019 at 07:58 UTC

    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.


    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

      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

      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
Re: circular area in a coordinates grid (AoA)
by karlgoethebier (Monsignor) on Mar 20, 2019 at 20:37 UTC

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

    «The Crux of the Biscuit is the Apostrophe»

    perl -MCrypt::CBC -E 'say Crypt::CBC->new(-key=>'kgb',-cipher=>"Blowfish")->decrypt_hex($ENV{KARL});'Help

Re: circular area in a coordinates grid (AoA)
by hippo (Chancellor) on Mar 23, 2019 at 17:47 UTC

    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; }

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

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2019-10-16 00:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?