Need help about point and line

This is a discussion on Need help about point and line within the Game Programming forums, part of the General Programming Boards category; Anyone know how to detect if a Point(x, y) is in a Line(x1, y1, x2, y2) or not? Quiet not ...

  1. #1
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Talking [SOLVED] Need help about point and line

    Anyone know how to detect if a Point(x, y) is in a Line(x1, y1, x2, y2) or not?

    Quiet not good at math please...
    Last edited by audinue; 01-01-2009 at 11:04 AM.
    Just GET it OFF out my mind!!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If the slope from (x1,y1) to (x,y) is the same as the slope from (x1,y1) to (x2,y2). Breaking out the formula for slope gives (x-x1)*(y2-y1) == (x2-x1)*(y-y1).

  3. #3
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Talking

    Quote Originally Posted by tabstop View Post
    If the slope from (x1,y1) to (x,y) is the same as the slope from (x1,y1) to (x2,y2). Breaking out the formula for slope gives (x-x1)*(y2-y1) == (x2-x1)*(y-y1).
    Works like a charm, thanks~! You are smart tabstob! Thanks!

    http://audinue.navhost.com/LineTest.html

    Code:
    var line = {x1:10, y1:10, x2:100, y2:100};
    _root.lineStyle(1);
    _root.moveTo(line.x1, line.y1);
    _root.lineTo(line.x2, line.y2);
    onEnterFrame = function () {
        var point = {x:_root._xmouse, y:_root._ymouse};
        hit_mc._visible = (point.x-line.x1)*(line.y2-line.y1) == (line.x2-line.x1)*(point.y-line.y1);
    };
    Last edited by audinue; 01-01-2009 at 11:16 AM.
    Just GET it OFF out my mind!!

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    You also need to check that x >= x1 && x <= x2 to make sure it is on the line.
    The slope extends to +/- infinity, so you need to test for more than just being on the slope.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Quote Originally Posted by Salem View Post
    You also need to check that x >= x1 && x <= x2 to make sure it is on the line.
    The slope extends to +/- infinity, so you need to test for more than just being on the slope.
    What do you mean? I don't get it.
    Any example please?
    Just GET it OFF out my mind!!

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Salem's point is that if you want if you want the point to be on the line segment strictly between (x1, y1) and (x2, y2) [as opposed to the line between the points that goes forever], then you need to check that x is between x1 and x2 (i.e., that (x1-x)*(x2-x) < 0).

  7. #7
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Code:
    boolean i s H i t (Point point, Line line) {
        return ((point.getX() >= line.getX1()) && (point.getX() <= line.getX2()) && (point.getY() >= line.getY1()) && (point.getY() <= line.getY2())) 
                && ((point.getX() - line.getX1()) * (line.getY2() - line.getY1()) == (line.getX2() - line.getX1()) * (point.getY() - line.getY1()));
      }
    What the...
    Just GET it OFF out my mind!!

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by audinue View Post
    Code:
    boolean i s H i t (Point point, Line line) {
        return ((point.getX() >= line.getX1()) && (point.getX() <= line.getX2()) && (point.getY() >= line.getY1()) && (point.getY() <= line.getY2())) 
                && ((point.getX() - line.getX1()) * (line.getY2() - line.getY1()) == (line.getX2() - line.getX1()) * (point.getY() - line.getY1()));
      }
    What the...
    I'm sure that can be written a bit more readable by storing the results of the getters in a set of suitably named variables. Calling the getter functions several times over is hardly meaningful.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Heres a version I came up with:
    Code:
    int PointIsOnLine(int x1, int y1, int x2, int y2, int x3, int y3)
    {
        if(x1 == x2 && y1 == y2) //Not a line
            return(x1 == x3 && y1 == y3);
        if(x1 == x2)    //No gradient
            return (y3 == y1);
        if(y1 == y2)    //Infinite gradient
            return (x3 == x1);
            
        float gradient = (float)(y2 - y1) / (float)(x2 - x1);
        int x01 = x1 - ((float)y1 / gradient +0.5);
        int x02 = x3 - ((float)y3 / gradient +0.5);
        return (!(x02-x01));
    }
    
    int PointIsInLine(int x1, int y1, int x2, int y2, int x3, int y3)
    {
        if(! PointIsOnLine(x1, y1, x2, y2, x3, y3)) return 0;
        if(x3 > MAX(x1, x2)  || x3 < MIN(x1, x2)) return 0;
        return 1;
    }

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,158
    Hrm. So if your line is from (0, 0) to (100, 1)... There are absolutely no points which are on that line which have integer coordinates, except for the endpoints.

    So using this sort of algorithm, you'd decide that nothing at all ever intersects that line, even though it's over 100 units long. Using integer coordinates isn't really the best choice for this sort of thing I think
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah, the co-ords get rounded:
    Code:
        int x01 = x1 - ((float)y1 / gradient +0.5);
        int x02 = x3 - ((float)y3 / gradient +0.5);
    I was using integer maths for this as I was checking pixel values in 2D to see if they sat on a line. I guess generally it would be better to do everything in floating point - that would very simple modification.

    Edit: although actually it looks as if its rounding the wrong way, lol. Perhaps it should have been:
    Code:
        int x01 = x1 - ((float)y1 / gradient) +0.5;
        int x02 = x3 - ((float)y3 / gradient) +0.5;
    this might fix an old bug I never worked out...
    Last edited by mike_g; 01-02-2009 at 05:04 PM.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    But if you do it with floating point, you'll want to do a delta comparison, since floating points rarely compare exactly equal, even when they should.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah, thats one of the reasons I have an irrational fear of using floats, lol.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Printing Length of Input and the Limited Input
    By dnguyen1022 in forum C Programming
    Replies: 33
    Last Post: 11-29-2008, 03:13 PM
  2. Need a fast way to check if a point is within a line.
    By mike_g in forum Game Programming
    Replies: 5
    Last Post: 08-05-2008, 12:24 PM
  3. 6 measly errors
    By beene in forum Game Programming
    Replies: 11
    Last Post: 11-14-2006, 10:06 AM
  4. Length of line..in polygon
    By zap_hax in forum C++ Programming
    Replies: 5
    Last Post: 03-29-2006, 07:49 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21