Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Code refactoring: simple trig, but it's been so long.

by revdiablo (Prior)
on Dec 30, 2004 at 00:12 UTC ( #418142=perlquestion: print w/ replies, xml ) Need Help??
revdiablo has asked for the wisdom of the Perl Monks concerning the following question:

I am playing around with Imager, attempting to make "fat lines." In other words, I want to draw a straight line, but be able to make it more than 1 pixel thick. I did not see any way to set a thickness for the primitive line() method, so I thought about drawing a rectangle instead, rotated and scaled appropriately. But I could not find a way to rotate the box() once I had it drawn.

So I fell back to the hammer of polygon(). My algorithm is thus: determine the angle of the line to be drawn. Rotate that angle by 90 degrees and project a point from each of the line's endpoints, in either direction. Connect the four projected points together as a polygon, and voila, a fat line. I made a simple diagram to demonstrate the idea. [The fat line is a filled polygon, of course; this diagram just shows the outline.]

Now, an algorithm is one thing, but actual code is another. It has been a long time since I've worked with trigonometry in any significant way, so I was fumbling around quite a bit. I've got something that works, but it doesn't strike me as particularly elegant. Here's the subroutine I came up with:

use Math::Trig qw(atan deg2rad rad2deg); sub _thick_line { my ($image, $thickness, $color, $x1, $y1, $x2, $y2) = @_; my $angle = _angle($x1, $y1, $x2, $y2); my $mirror1 = $angle + 90; my $mirror2 = $angle - 90; my $m1c = $thickness*cos(deg2rad $mirror1)/2; my $m1s = $thickness*sin(deg2rad $mirror1)/2; my $m2c = $thickness*cos(deg2rad $mirror2)/2; my $m2s = $thickness*sin(deg2rad $mirror2)/2; my $x1a = $x1 + $m1c; # bottom left my $y1a = $y1 + $m1s; my $x1b = $x1 + $m2c; # top left my $y1b = $y1 + $m2s; my $x2a = $x2 + $m1c; # bottom right my $y2a = $y2 + $m1s; my $x2b = $x2 + $m2c; # top right my $y2b = $y2 + $m2s; $image->polygon( aa => 1, color => $color, points => [ [$x1a, $y1a], [$x2a, $y2a], [$x2b, $y2b], [$x1b, $y1b], ], ); } sub _angle { my ($x1, $y1, $x2, $y2) = @_; my $x = $x2 - $x1; my $y = $y2 - $y1; # short circuit the extreme cases return 0 if $x > 0 and $y == 0; return 180 if $x < 0 and $y == 0; return 90 if $x == 0 and $y > 0; return 270 if $x == 0 and $y < 0; # calculate the rest return rad2deg atan($y/$x); }

Any ideas or suggestions? Any way I can make this code easier to follow, in any way? I'm looking mainly for refactoring advice, but algorithmic suggestions would be welcome, too.

Update: here's the updated version, taking everyone's advice into consideration. I think it's quite a bit nicer. Many thanks.

sub _thick_line { my ($image, $thickness, $color, $x1, $y1, $x2, $y2) = @_; my $angle = atan2 $x2-$x1, $y2-$y1; my $mirror = atan2 $y1-$y2, $x2-$x1; # perpendicular angle my $dx = $thickness*sin($mirror)/2; my $dy = $thickness*cos($mirror)/2; $image->polygon( aa => 1, color => $color, points => [ [$x1 + $dx, $y1 + $dy], # top left [$x2 + $dx, $y2 + $dy], # top right [$x2 - $dx, $y2 - $dy], # bottom right [$x1 - $dx, $y1 - $dy], # bottom left ], ); }

Comment on Code refactoring: simple trig, but it's been so long.
Select or Download Code
Re: Code refactoring: simple trig, but it's been so long.
by borisz (Canon) on Dec 30, 2004 at 01:56 UTC
    Your code looks very clean to me. However, I prefer to write _thick_line a little more compact.
    sub _thick_line { my ( $image, $thickness, $color, $x1, $y1, $x2, $y2 ) = @_; my $angle = _angle( $x1, $y1, $x2, $y2 ); my $mirror1 = $angle + 90; my $mirror2 = $angle - 90; my $m1c = $thickness * cos( deg2rad $mirror1 ) / 2; my $m1s = $thickness * sin( deg2rad $mirror1 ) / 2; my $m2c = $thickness * cos( deg2rad $mirror2 ) / 2; my $m2s = $thickness * sin( deg2rad $mirror2 ) / 2; $image->polygon( aa => 1, color => $color, points => [ [ $x1 + $m1c, $y1 + $m1s ], # bottom left [ $x2 + $m1c, $y2 + $m1s ], # bottom right [ $x2 + $m2c, $y2 + $m2s ], # top right [ $x1 + $m2c, $y1 + $m2s ], # top left ], ); }
    Boris

      Nice idea. The series of variables that you eliminated were one of the main things I didn't like about my code. This looks much cleaner. Thanks!

Re: Code refactoring: simple trig, but it's been so long.
by Zaxo (Archbishop) on Dec 30, 2004 at 02:02 UTC

    You can save some messing around with,     my $angle = atan2 $x2-$x1, $y2-$y1;
    I think that short-circuiting that is premature optimization, and may be an actual pessimization since FPU's do atan2 atomicly. Atan2 knows what quadrant the angle is in from the signs of its arguments, so you can save checking all those cases. Also, stick with radian measure except possibly for printed display.

    Those together remove the need for Math::Trig.

    After Compline,
    Zaxo

      Excellent. I didn't really like falling back to Math::Trig, and its dire performance warnings kind of worried me. This is a much simpler way to calculate the angle.

Re: Code refactoring: simple trig, but it's been so long.
by tachyon (Chancellor) on Dec 30, 2004 at 02:08 UTC

    Evidently you feel more comfortable using degrees rather than radians but the conversion to and from radians<->degrees serves no real purpose. Just define:

    my $ninety_degrees = atan(1)*2;

    You will get a division by zero crash in the case where $x and $y = 0 as it will fall through your 'extreme cases'. You can remove the dependency on a module by using radians and using a function for atan() like:

    sub atan { return 0 if $_[0]==0; return $_[0] > 0 ? atan2(sqrt(1+$_[0]*$_[0]),sqrt(1+1/($_[0]*$_[0]))) : -atan2(sqrt(1+$_[0]*$_[0]),sqrt(1+1/($_[0]*$_[0]))); }

    cheers

    tachyon

      Evidently you feel more comfortable using degrees rather than radians but the conversion to and from radians<->degrees serves no real purpose.

      Yeah, that was just out of habit. I noticed that the conversion between radians and degrees was pointless before I posted, but never got around to changing it to only radians.

      You will get a division by zero crash in the case where $x and $y = 0 as it will fall through your 'extreme cases'.

      Ah, I hadn't noticed that. Using Zaxo's code will eliminate that problem, though. Many thanks.

Re: Code refactoring: simple trig, but it's been so long.
by johnnywang (Priest) on Dec 30, 2004 at 03:48 UTC
    It will be easier if you use vector notation in figuring out the formulae. Call your two end points P, Q, you only need to find one displacement vector, say from P to top right corner, call that vector v, then the four corners are given by:
    P + v, P - v, Q + v, Q - v
    Note that the tangent of an angle is just the slope of the line(i.e., (y2-y1)/(x2-x1)), and when two lines are perpendicular, their slopes are negative reciprocal of each other. Using these facts, you won't really need to use sine/cosine, just tangent.
      you only need to find one displacement vector

      Ah yes, this is true. Nice idea. I'll use this as well, thanks.

      you won't really need to use sine/cosine, just tangent

      But there's no builtin tangent function, which means I'll either have to use Math::Trig, or roll my own tan, in terms of sin and cos anyway, right? Or is there something I'm missing?

        tan is just the slope:
        tan = (y2-y1)/(x2-x1)

      Just tangent?? I don't need no stinking tangent!

      Since you beat me to the subject of vector algebra I'll skip much of my introduction about how trigonometry sucks for this. Why would anyone want to approximate a bunch of transcendental functions just to approximate another bunch of transcendental functions that are their inverses? Plus you have to special-case horizontal (or vertical, depending) lines.

      With vector algebra you only need to do a few simple subtractions, multiplications, additions, exactly one division (where the denominator is never 0), and take exactly one square root.

      I'll call our points A and B. Let's let V = ( xv, yv ) be the vector from A to B. Then -V = ( -xv, -yv ) points the other direction. But ( -yv, xv ) and ( yv, -xv ) point perpendicular. So scale these to be the right length and add them to A and B and you get the 4 points of your box that defines your "think line".

      And you can do that without having to repeat yourself much if you let the code do the repeating for you:

      #!/usr/bin/perl -w use strict; # This takes two 2-dimensional points (A and B) # and a width, and returns 4 points that are the # counter-clockwise perimeter of a "thick line" # (box) of the specified width around the line. sub line2box { my $w= pop @_; die 'Usage: line2box($ax,$ay,$bx,$by,$width)' if $w <= 0 || 4 != @_; # We just keep our 4 coordinates in a single array # so we don't have to repeat ourselves much below. $w /= 2; # Length of offset vector is $width/2 my @d; # Differences between X and Y coord.s my $l= 0; for( 0, 1 ) { my $d= $_[$_] - $_[2+$_]; $l += $d*$d; push @d, $d; } # Now $l is length**2, so we want to scale our # perpendicular vectors by $width / $length so: $l= sqrt( $w*$w / $l ); $_ *= $l for @d; my @box; my @s= ( -1, 1 ); # Sign to apply (- or +) for my $s ( 0, 1 ) { # Index into @s # $p==0 for A, $p==1 for B for my $p ( $s, !$s ) { # Which point for my $c ( 0, 1 ) { # Which coordinate # Push the selected coordinate push @box, $_[2*$p+$c] + $s[$s^$c]*$d[!$c]; } } } return @box; } while( <DATA> ) { last if !/\S/; my @line= split ' '; $line[-1] **= 0.5; my @box= line2box( @line ); printf qq[A line from A( %5.1f, %5.1f )$/] . qq[ to B( %5.1f, %5.1f )$/] . qq[of width sqrt( %5.1f )$/] . qq[is a box, counter-clock-wise:$/] . qq[ W( %5.1f, %5.1f )$/] . qq[ X( %5.1f, %5.1f )$/] . qq[ Y( %5.1f, %5.1f )$/] . qq[ Z( %5.1f, %5.1f )$/] . $/ , @line[0..3], $line[4]**2, , @box; }

      And here is some sample input, sample output, and some ASCII-art drawings thrown in to make sense of the numbers.

      __END__ 1 0 1 5 4 1 1 6 1 16 -1 -2 2 1 8 A line from A( 1.0, 0.0 ) to B( 1.0, 5.0 ) of width sqrt( 4.0 ) is a box, counter-clock-wise: W( 2.0, 0.0 ) X( 2.0, 5.0 ) Y( 0.0, 5.0 ) Z( 0.0, 0.0 ) w=2 |<--->| | (Y)(B)(X) | # 4+ # | # 3+ # | # 2+ # | # 1+ # | # --+--+-(Z)(A)(W)-+-- -2 -1 0 1 2 A line from A( 1.0, 1.0 ) to B( 6.0, 1.0 ) of width sqrt( 16.0 ) is a box, counter-clock-wise: W( 1.0, -1.0 ) X( 6.0, -1.0 ) Y( 6.0, 3.0 ) Z( 1.0, 3.0 ) | 4+ | 3+ (Z) (Y) --- | ^ 2+ | | | 1+ (A)############(B) w=4 | | --+--+--+--+--+--+--+--+--+- | -1 0 1 2 3 4 5 6 7 v -1+ (W) (X) --- | -2+ | A line from A( -1.0, -2.0 ) to B( 2.0, 1.0 ) of width sqrt( 8.0 ) is a box, counter-clock-wise: W( 0.0, -3.0 ) X( 3.0, 0.0 ) Y( 1.0, 2.0 ) Z( -2.0, -1.0 ) | 3+ / | \ 2+ (Y) w=2*(2**.5) | \ 1+ (B) / | // --+--+--+--+--+--+-(X)-+-- -3 -2 -1 0//1 2 3 4 (Z) -1+ //| (A) -2 | -3(W) | -4+ |

      Note that the line:

      for my $p ( $s, !$s ) { # Which point

      is a tricky way of saying "the first time through (using a negative sign) do A first then B; the second time through (using a positive sign) do B first then A". This gives us the dots in a perimeter order (so you could just connect them if you wanted the outline of the thick line).

      And I didn't have to memorize any rules about cos() vs. sin() or even worry about which coordinate was x or y. I just do all of the combinations and I get all of the points needed.

      - tye        

        I know I'm dense, but this seems like a lot more work than memorizing (or looking up, or figuring out by experimentation) a few rules about cos() and sin(). Perhaps you can explain it to me in a way that makes sense? If using vector algebra truly is better/simpler/etc, I'd at least be curious to understand why...

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://418142]
Approved by Old_Gray_Bear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (11)
As of 2014-12-26 02:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (164 votes), past polls