Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Check if line is straight

by Anonymous Monk
on May 15, 2011 at 23:54 UTC ( #905002=perlquestion: print w/replies, xml ) Need Help??

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

Respectable Monks, Given 2 points for co-ordinates x and y , I need a function to check if a line is straight ( with some variance), I have the following code which works fine if there is a slope in the line, but if the slope is 0 then I am not sure how to check if the new points are a straight line, here is the code I have , What am I missing here
sub isCorrectPath () { my ($x1, $y1, $x2, $y2) = @_ my $difx = ($x2 - $x1) ; my $slope = ($difx == 0) ? 0 : ($y2 - $y1) / $difx; return sub { my ($x, $y) = @_; my $xmin = ($x - $x1); if ( $slope == 0 ) {# if line is straight if ($difx == 0 ) {# how to make sure +the path is correct and in correct direction return (($x - $x1) < 3 ) && ( +(($y - $y1) > 0) || (($y - $y1) > 0)); } else { return (($y - $y1) < 3 ) && ( +($x - $x1) > 0) || (($x1 - $x) > 0) ; } } else { return abs(($slope * ($x - $x1)) - ($y - $ +y1)) <= 30; } } ; }

Replies are listed 'Best First'.
Re: Check if line is straight
by pajout (Curate) on May 16, 2011 at 06:36 UTC
    If you really want to check colinearity of three points, you can just multiply vectors:
    sub isCorrectPath () { my ($x1, $y1, $x2, $y2, $x, $y) = @_; return !(($x2-$x1)*($y-$y1)-($x-$x1)*($y2-$y1)); }
      This is pretty neat, saves a lot of code. What is the best way to add tolerance to this? any suggestions ? Thanks
        return abs(($x2-$x1)*($y-$y1)-($x-$x1)*($y2-$y1)) < $tolerance;

        Update added abs()

        It depends if you mean tolerance necessary for dealing floats - lidden suggested it already. But if you mean real tolerance, for instance "path is correct if the angle between two vectors is less than 1 degree", you should really compute that value.
Re: Check if line is straight
by LanX (Saint) on May 16, 2011 at 00:17 UTC
    I'm confused, every line thru 2 points is straight.

    Actually you are calculating with 3 points P, P1 and P2 with P=($x,$y)

    Is your intention to check if the path P1-P2 and P-P1 are on the same straight line or what?

    One approach:

    A path is "straight" iff the two vectors are identical after normalization (i.e. shortened to length 1 and with same orientation)

    To normalize them divide each component by the length of the vector.

    In 2 dimensional space you get the length simply by applying Pythagoras...in higher dimension use the scalar product.

    Another (easier)approach:

    Calculate the normal vector n of P1-P2 (a normalized vector orthogonal to the line).

    The scalar product (aka dot product) of n (P-P1) == 0 iff P,P1 and P2 are collinear.

    Don't wanna go deeper into details thats all school stuff...

    Cheers Rolf

      proof of concept second approach, normalization of orthogonal not necessary for dot product to become 0.

      UPDATE: Nota bene: only additions no divisions, which makes the code fast and secure from division by 0 problems.

      ($p1,$p2,$p3)=([2,2],[3,4],[4,6]); sub vector { my ($x1,$y1) = @{$_[0]}; my ($x2,$y2) = @{$_[1]}; my @v=( $x2-$x1, $y2-$y1 ); my @o=( -$v[1] , $v[0] ); return [@v],[@o]; } sub dot { my ($x1,$y1) = @{$_[0]}; my ($x2,$y2) = @{$_[1]}; return $x1*$x2 + $y1*$y2; } my ($v12,$o12)= vector($p1,$p2); # the test my ($v)= vector($p1,$p3); print dot ($o12,$v); # 0 because p3 is collinear with p1 ,p2

      Cheers Rolf

        Sorry for not being clear, I assumed that looking at the code will make it obvious which is clearly not the case, The problem i am trying to solve is that it is basically a join the dots application, There are fixed points say point 1 and point 2, when the mouse is moved from point 1 to point 2 i want to make sure the path is correct so I take the start x,y (point1) and end x, y(point2) and take the current position of the mouse (x,y) and make sure that the path is correct. my code works fine if there is a slope but if the points are vertical or horizontal (slope 0) then I was not sure how to make sure that the direction and path is correct( a slight deviation is ok). Hope this clears up the question
Re: Check if line is straight
by GrandFather (Saint) on May 16, 2011 at 00:57 UTC

    Maybe you want something like this:

    #!/usr/bin/perl use strict; use warnings; my $match45 = isCorrectPath (0, 0, 10, 10); for my $pair ([0, 0], [-1, 0], [-4, 0], [5, 5], [1, 5]) { if ($match45->(@$pair)) { print "Match 45 for @$pair\n"; } else { print "Fail 45 for @$pair\n"; } } my $match0 = isCorrectPath (0, 0, 10, 0); for my $pair ([0, 0], [0, -1], [0, -4], [5, 5], [100, 2]) { if ($match0->(@$pair)) { print "Match 0 for @$pair\n"; } else { print "Fail 0 for @$pair\n"; } } my $match90 = isCorrectPath (0, 0, 0, 10); for my $pair ([0, 0], [-1, -0], [-4, 0], [5, 5], [2, 100]) { if ($match90->(@$pair)) { print "Match 90 for @$pair\n"; } else { print "Fail 90 for @$pair\n"; } } sub isCorrectPath { my ($x1, $y1, $x2, $y2) = @_; my $difx = ($x2 - $x1); my $slope = $difx ? ($y2 - $y1) / $difx : undef; return sub { my ($x, $y) = @_; my $xmin = ($x - $x1); return abs($x - $x1) < 3 # Vertical line: allow 3 units eit +her side if !defined $slope; return abs($y - $y1) < 3 # Horizontal line: allow 3 units e +ither side if !$slope; return abs(($slope * ($x - $x1)) - ($y - $y1)) < 3; }; }

    Prints:

    Match 45 for 0 0 Match 45 for -1 0 Fail 45 for -4 0 Match 45 for 5 5 Fail 45 for 1 5 Match 0 for 0 0 Match 0 for 0 -1 Fail 0 for 0 -4 Fail 0 for 5 5 Match 0 for 100 2 Match 90 for 0 0 Match 90 for -1 0 Fail 90 for -4 0 Fail 90 for 5 5 Match 90 for 2 100
    True laziness is hard work
Re: Check if line is straight
by roboticus (Chancellor) on May 16, 2011 at 00:06 UTC

    Your question isn't very clear. A line is always "straight", so you're not asking about that, and you have only two points, and two points are always collinear. If you had three points, we could tell if they were all on the same straight line. So please refine your question a bit, and we can to help.

    Update: I just saw LanX's response, prompting me to read the code. In fact, you have three points, so I suspect you're asking whether the points are all collinear. If so, his reply gives the solution...

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

Re: Check if line is straight
by JavaFan (Canon) on May 16, 2011 at 10:56 UTC
    If the slope is 0 (horizontal line, but vertical in your code), the x-coordinate of all the points on the line is the same. So, for the third point, just check whether the x-coordinate is the same as for one of the other points.

      In the original code, the slope is 0 for both horizontal and vertical lines, so you would have to first check for zero slope, then check for a stationary abscissa :-) to differentiate between horizontal and vertical. Personally, I would have made the slope undef for a vertical line, but it wouldn't make much difference in amount of coding effort.

      I like the approach of LanX taking this out of the Cartesian setting and into vector notation; it generalizes all line orientations so that you don't have to specially handle edge cases. pajout has given the algebraic statement of the reasoning Re^2: Check if line is straight, which is good enough to answer what (we think) is the question, but it's good to keep the vector approach in mind.

      As an erstwhile scientific programmer I still feel the need to point out that with floating point comparisons it might be a good idea to use a tolerance calculation somewhere....

        > As an erstwhile scientific programmer I still feel the need to point out that with floating point comparisons it might be a good idea to use a tolerance calculation somewhere....

        sure ... but I'm waiting pedagogically for the OP to come back before explaining how to get the correct angle out of the dot-product ;)

        Cheers Rolf

Re: Check if line is straight
by anonymized user 468275 (Curate) on May 16, 2011 at 12:50 UTC
    You only need to eliminate vertical lines where x = c. So if the first two points have the same x value, you only have to check that all subsequent points have the same x-value. Otherwise, havijng eliminated the exceptional case, you can process each pair of points (in any order! i.e. iterate the 2nd thru last comparing with iterator - 1) to ensure they produce consistent (throughout the loop) values for m and c in the simultaneous equation y1=m*x1+c and y2=m*x2+c.

    BUT, if this is experimental data, you need to calculate the standard deviation from the line of regression instead, e.g. using Statistics::LineFit.

    Update: I'd refer to zentara's Solving Simultaneous Equations with Matrices (use PM Supersearch) for the second part of the algorithm). And even if the data were not experimental, personally I'd go the Stats Line Fit route anyway because it is a tolerant solution to rounding errors.

    One world, one people

Re: Check if line is straight
by Anonymous Monk on May 17, 2011 at 14:30 UTC
    Of your 3 points, find the 2 extreme points. Look to see if delta_X for the extreme points is larger than delta_Y. If so, your problem is mostly horizontal, otherwise it is mostly vertical. A person probably should convert the problem to either purely horizontal or purely vertical (by pivoting on the left/bottom point). First, subtract the (X,Y) coordinates of that left/bottom point from all the points, leaving that left/bottom point at the origin. Then rotate the other points so that the other extreme point either has an X of 0 (vertical problem) or a Y of 0 (horizontal problem). If the Y coordinate of the middle point (horizontal problem) is within the tolerance of 0, the triplet appears to be co-linear. The problem is left as to how to choose a tolerance. In general, that middle point will almost never have a Y coordinate of 0. The same as true of the other extreme point. Theoretically we can rotate it to make the coordinate equal to 0, but finite precision floating point arithmetic will usually not allow it to become 0. It should be closer to 0 than the middle point.
Re: Check if line is straight
by wind (Priest) on May 20, 2011 at 00:55 UTC

    I'm a little late to the party on this one, but wanted to share my solution anyway since it covers all cases.

    The only trick to this problem is realizing that you need the following three equations:

    • Formula for a line: y = m x + b
    • Perpendicular line: Y = M x + B where M = -1 / m
    • Dist between 2 points: dist = sqrt(dX ^ 2 + dY ^ 2)

    Assuming you want a third point to be within a specified uncertainty that is either constant or relative to the segment length, than the following would work:

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2023-12-10 07:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What's your preferred 'use VERSION' for new CPAN modules in 2023?











    Results (39 votes). Check out past polls.

    Notices?