Re: circular area in a coordinates grid (AoA) (updated)
by vr (Curate) on Mar 19, 2019 at 22:27 UTC
|
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.
| [reply] [d/l] [select] |
|
| [reply] |
|
| [reply] |
Re: circular area in a coordinates grid (AoA)
by tybalt89 (Monsignor) on Mar 19, 2019 at 22:16 UTC
|
#!/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"
}
}
| [reply] [d/l] |
|
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.
| [reply] [d/l] [select] |
|
| [reply] |
|
my $delta_x = $radius ** 2 - ($center_r - $row) ** 2;
if( $delta_x >= 0 ){
$delta_x = int sqrt $delta_x;
...
bw, bliako | [reply] [d/l] [select] |
|
| [reply] [d/l] [select] |
|
| [reply] |
|
Re: circular area in a coordinates grid (AoA)
by LanX (Saint) 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.
| [reply] [d/l] |
Re: circular area in a coordinates grid (AoA)
by Marshall (Canon) 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. | [reply] [d/l] [select] |
|
$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.
| [reply] [d/l] [select] |
|
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:
| [reply] [d/l] [select] |
Re: circular area in a coordinates grid (AoA)
by Marshall (Canon) 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? | [reply] [d/l] |
|
| [reply] |
|
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!
| [reply] |
|
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!
| [reply] |
Re: circular area in a coordinates grid (AoA)
by BrowserUk (Patriarch) 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.
In the absence of evidence, opinion is indistinguishable from prejudice.
Suck that fhit
| [reply] |
|
#! 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.
In the absence of evidence, opinion is indistinguishable from prejudice.
Suck that fhit
| [reply] [d/l] |
Re: circular area in a coordinates grid (AoA)
by karlgoethebier (Abbot) 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
| [reply] [d/l] |
Re: circular area in a coordinates grid (AoA)
by hippo (Bishop) 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.) | [reply] [d/l] |