Line intersection detection....

Discussion in 'Java' started by SPG, Feb 19, 2005.

  1. SPG

    SPG Guest

    Hi All,

    I have a bit of a problem that you may be able to solve for me.
    I need to draw a line on a canvas, using the awt.graphics class only.

    Let me stress from the start I have to support MS JVM here..... Hence I
    cannot use and of the 2d functionality (Suckola)

    Anyhow, The drawing part is easy, and I have done this. But.. I need to
    detect a mouse click on any part of the line itself, so I can allow the user
    to move it.

    The code posted works, but it only detects intersection inside the rectangle
    that is startx, start.y, end.x, end.y
    I need to actually refine this so I only get the intersection where the x,y
    coords are physically on the line..

    Some one out there knows the math on how to do this... Please help!!!
    Assume a mouseClick event will fire a call into the intersects(x,y) method..

    Cheers,

    Steve

    import java.awt.*;

    public class TrendLine {
    private Point _start;
    private Point _end;

    public TrendLine() {
    _start = new Point(0,0);
    _end = new Point(0,0);
    }

    public void setStart(Point _start) {
    this._start = _start;
    }

    public Point getStart() {
    return _start;
    }

    public void setEnd(Point _end) {
    this._end = _end;
    }

    public Point getEnd() {
    return _end;
    }

    public boolean intersects(int x, int y){
    if( (x >= _start.x && x <= _end.x)
    || (x <= _start.x && x >= _end.x)){
    if( ( y >= _start.y && y <= _end.y)
    || (y <= _start.y && y >= _end.y)){
    return true;
    }
    }
    return false;
    }

    public void draw(Graphics g){
    //Draw Line
    g.drawLine(getStart().x, getStart().y, getEnd().x, getEnd().y);
    g.setColor(c);
    }
    }
     
    SPG, Feb 19, 2005
    #1
    1. Advertising

  2. SPG

    Chris Uppal Guest

    SPG wrote:

    > I need to actually refine this so I only get the intersection where the
    > x,y coords are physically on the line..


    I doubt if you want to force the user to click /on/ the line -- far too fiddly.
    You need to detect the distance /to/ the line and consider it "picked" if the
    distance is less than some threshold.

    Since I've seen no other replies, I dug out a bit of /very old/ 'C' code for
    computing the distance to a line segment (actually the square of the distance,
    to avoid messing around tacking square roots all the time). Translating to
    Java (or indeed to a modern dialect of 'C') is left as an exercise for the
    reader... (You could probably use a long instead of a double for the
    intermediate result.)

    I could probably re-create the maths that justify the calculation, but not on a
    Sunday afternoon ;-)

    -- chris

    /*
    * return the square of the distance from pos to the
    * line segment from-to
    */
    static int
    dist_to_line(from, to, pos)
    POINT from, to, pos;
    {
    register int x_ft, y_ft, x_fp, y_fp;
    register int t, d_ft;
    register double r;

    x_ft = from.x - to.x; y_ft = from.y - to.y;
    x_fp = from.x - pos.x; y_fp = from.y - pos.y;
    t = x_ft*x_fp + y_ft*y_fp;

    /* "below" from on segment ? */
    if (t <= 0)
    return dist_sq(from, pos);

    /* "above" to on segment ? */
    d_ft = dist_sq(from, to);
    if (t >= d_ft)
    return dist_sq(to, pos);

    /* else we have to calculate the distance to the line */
    r = x_ft*y_fp - x_fp*y_ft;
    r *= r; /* this is why r is double -- int would overflow */
    r /= d_ft;
    return (int)r;
    }
     
    Chris Uppal, Feb 20, 2005
    #2
    1. Advertising

  3. SPG

    SPG Guest

    Perfect!
    I was fiddling aroung with a ploygon hich was a few pixels wder thatn th
    eline itself, but thi smakes the code simplet to use..

    cheers..
    "Chris Uppal" <-THIS.org> wrote in message
    news:42188cc8$1$38039$...
    > SPG wrote:
    >
    >> I need to actually refine this so I only get the intersection where the
    >> x,y coords are physically on the line..

    >
    > I doubt if you want to force the user to click /on/ the line -- far too
    > fiddly.
    > You need to detect the distance /to/ the line and consider it "picked" if
    > the
    > distance is less than some threshold.
    >
    > Since I've seen no other replies, I dug out a bit of /very old/ 'C' code
    > for
    > computing the distance to a line segment (actually the square of the
    > distance,
    > to avoid messing around tacking square roots all the time). Translating
    > to
    > Java (or indeed to a modern dialect of 'C') is left as an exercise for the
    > reader... (You could probably use a long instead of a double for the
    > intermediate result.)
    >
    > I could probably re-create the maths that justify the calculation, but not
    > on a
    > Sunday afternoon ;-)
    >
    > -- chris
    >
    > /*
    > * return the square of the distance from pos to the
    > * line segment from-to
    > */
    > static int
    > dist_to_line(from, to, pos)
    > POINT from, to, pos;
    > {
    > register int x_ft, y_ft, x_fp, y_fp;
    > register int t, d_ft;
    > register double r;
    >
    > x_ft = from.x - to.x; y_ft = from.y - to.y;
    > x_fp = from.x - pos.x; y_fp = from.y - pos.y;
    > t = x_ft*x_fp + y_ft*y_fp;
    >
    > /* "below" from on segment ? */
    > if (t <= 0)
    > return dist_sq(from, pos);
    >
    > /* "above" to on segment ? */
    > d_ft = dist_sq(from, to);
    > if (t >= d_ft)
    > return dist_sq(to, pos);
    >
    > /* else we have to calculate the distance to the line */
    > r = x_ft*y_fp - x_fp*y_ft;
    > r *= r; /* this is why r is double -- int would overflow */
    > r /= d_ft;
    > return (int)r;
    > }
    >
    >
    >
     
    SPG, Feb 20, 2005
    #3
  4. SPG

    SPG Guest

    Hi Chris,

    I implemented your method, but I am not sure if this does what I need.
    When I put my mouse right over the middle of the line, I get quite a large
    distance value, because this appears to calculate the distance between the
    start or end points.

    I need to work out if theline is being crossed.
    My current solution is to create a polygon which is a couple of points wider
    than the actual line, then call Polygon.contains().
    This works but is quite slow..

    Any thoughts?

    Steve

    "Chris Uppal" <-THIS.org> wrote in message
    news:42188cc8$1$38039$...
    > SPG wrote:
    >
    >> I need to actually refine this so I only get the intersection where the
    >> x,y coords are physically on the line..

    >
    > I doubt if you want to force the user to click /on/ the line -- far too
    > fiddly.
    > You need to detect the distance /to/ the line and consider it "picked" if
    > the
    > distance is less than some threshold.
    >
    > Since I've seen no other replies, I dug out a bit of /very old/ 'C' code
    > for
    > computing the distance to a line segment (actually the square of the
    > distance,
    > to avoid messing around tacking square roots all the time). Translating
    > to
    > Java (or indeed to a modern dialect of 'C') is left as an exercise for the
    > reader... (You could probably use a long instead of a double for the
    > intermediate result.)
    >
    > I could probably re-create the maths that justify the calculation, but not
    > on a
    > Sunday afternoon ;-)
    >
    > -- chris
    >
    > /*
    > * return the square of the distance from pos to the
    > * line segment from-to
    > */
    > static int
    > dist_to_line(from, to, pos)
    > POINT from, to, pos;
    > {
    > register int x_ft, y_ft, x_fp, y_fp;
    > register int t, d_ft;
    > register double r;
    >
    > x_ft = from.x - to.x; y_ft = from.y - to.y;
    > x_fp = from.x - pos.x; y_fp = from.y - pos.y;
    > t = x_ft*x_fp + y_ft*y_fp;
    >
    > /* "below" from on segment ? */
    > if (t <= 0)
    > return dist_sq(from, pos);
    >
    > /* "above" to on segment ? */
    > d_ft = dist_sq(from, to);
    > if (t >= d_ft)
    > return dist_sq(to, pos);
    >
    > /* else we have to calculate the distance to the line */
    > r = x_ft*y_fp - x_fp*y_ft;
    > r *= r; /* this is why r is double -- int would overflow */
    > r /= d_ft;
    > return (int)r;
    > }
    >
    >
    >
     
    SPG, Feb 24, 2005
    #4
  5. SPG

    Jacob Guest

    SPG wrote:

    > I implemented your method, but I am not sure if this does what I need.
    > When I put my mouse right over the middle of the line, I get quite a large
    > distance value, because this appears to calculate the distance between the
    > start or end points.
    >
    > I need to work out if theline is being crossed.
    > My current solution is to create a polygon which is a couple of points wider
    > than the actual line, then call Polygon.contains().
    > This works but is quite slow..


    The common approach is to create a small rectangle based
    on your mouse location and check if the line intersects
    this rectangle.

    You may look at the isLineIntersectingRectangle() method of

    http://geosoft.no/software/geometry/Geometry.java.html

    where this problem is solved.

    --
    Jacob Dreyer
    G - Free 2D Graphics Library for Java - http://geosoft.no/graphics
    Free Java Software - http://geosoft.no/software
     
    Jacob, Feb 24, 2005
    #5
  6. SPG

    Steve Bosman Guest

    If you want to go with the method of calculating the distance of your
    point
    from the line this page gives the maths:
    http://thesaurus.maths.org/mmkb/entry.html?action=entryByConcept&id=3454&langcode=en
    This site requires MathML

    Since you say you're not too happy with the maths I won't assume
    anything.

    All straight lines can be represented by:
    a*x+b*y+c=0

    Basically a (non-vertical) line can be represented
    g*x-y+c = 0

    where g is the gradient which with two known points (xStart, yStart)
    and (xEnd, yEnd) is easily obtained
    (1) gradient = (yEnd-yStart)/(xEnd-xStart)

    and c is the value of y at x=0 which should be:
    (2) yAtZero = (yEnd - gradient * xEnd)

    And this means for a point (xPoint, yPoint) the square of the distance
    from the line is

    (3) distanceSquared = (gradient*xPoint-yPoint+yAtZero )^2 / (gradient
    ^2+1)

    This has been done on the fly with minimal checking so I could be
    wrong, but
    after some quick sanity checking I'm fairly happy that plugging your
    values
    into (1)-(3) should work for you.

    Steve
     
    Steve Bosman, Feb 24, 2005
    #6
  7. SPG

    Chris Uppal Guest

    Steve Bosman wrote:

    I think there are a couple of problems with this.


    > where g is the gradient which with two known points (xStart, yStart)
    > and (xEnd, yEnd) is easily obtained
    > (1) gradient = (yEnd-yStart)/(xEnd-xStart)


    This will zero-divide if the line is vertical.


    > And this means for a point (xPoint, yPoint) the square of the distance
    > from the line is
    >
    > (3) distanceSquared = (gradient*xPoint-yPoint+yAtZero )^2 / (gradient
    > ^2+1)


    I haven't checked the details (can't be bothered, to be honest ;-) but you are
    computing the distance to the infinite line defined by the equation, not to the
    finite line segment. For instance the distance from the point (20, 20) to the
    line /segment/ from (0,0) to (10, 10) should not be zero, but 10.

    -- chris
     
    Chris Uppal, Feb 24, 2005
    #7
  8. SPG

    Chris Uppal Guest

    SPG wrote:

    > I implemented your method, but I am not sure if this does what I need.
    > When I put my mouse right over the middle of the line, I get quite a large
    > distance value, because this appears to calculate the distance between the
    > start or end points.


    I think you have probably mis-transcribed the 'C' into Java.

    That code worked for many years in production, and I've just checked to see if
    it still works and it doesn't /seem/ to have gone off ;-)

    -- chris
     
    Chris Uppal, Feb 24, 2005
    #8
  9. SPG

    Steve Bosman Guest

    Chris Uppal wrote:
    > Steve Bosman wrote:
    >
    > I think there are a couple of problems with this.
    >
    >
    > > where g is the gradient which with two known points (xStart,

    yStart)
    > > and (xEnd, yEnd) is easily obtained
    > > (1) gradient = (yEnd-yStart)/(xEnd-xStart)

    >
    > This will zero-divide if the line is vertical.
    >

    I'm sure I stated non-vertical lines. Vertical lines (like horizontal
    lines) are trivial to detect a distance from.

    >
    > > And this means for a point (xPoint, yPoint) the square of the

    distance
    > > from the line is
    > >
    > > (3) distanceSquared = (gradient*xPoint-yPoint+yAtZero )^2 /

    (gradient
    > > ^2+1)

    >
    > I haven't checked the details (can't be bothered, to be honest ;-)

    but you are
    > computing the distance to the infinite line defined by the equation,

    not to the
    > finite line segment. For instance the distance from the point (20,

    20) to the
    > line /segment/ from (0,0) to (10, 10) should not be zero, but 10.
    >

    Good point, completely forgot it was for a line segment :) Can't think
    of a test for this at the moment...
     
    Steve Bosman, Feb 24, 2005
    #9
  10. SPG

    Chris Uppal Guest

    I wrote:

    > > I implemented your method, but I am not sure if this does what I need.
    > > When I put my mouse right over the middle of the line, I get quite a
    > > large distance value, because this appears to calculate the distance
    > > between the start or end points.

    >
    > I think you have probably mis-transcribed the 'C' into Java.


    I got bored ;-)

    -- chris

    =============

    double
    distanceSquared(Point from, Point to, Point pos)
    {
    double x_ft = from.x - to.x;
    double y_ft = from.y - to.y;
    double x_fp = from.x - pos.x;
    double y_fp = from.y - pos.y;
    double t = x_ft*x_fp + y_ft*y_fp;

    /* "below" from on segment ? */
    if (t <= 0)
    return from.distanceSq(pos);

    /* "above" to on segment ? */
    double d_ft = from.distanceSq(to);
    if (t >= d_ft)
    return to.distanceSq(pos);

    /* else we have to calculate the distance to the line */
    double r = x_ft*y_fp - x_fp*y_ft;
    r *= r;
    r /= d_ft;
    return r;
    }
     
    Chris Uppal, Feb 24, 2005
    #10
  11. SPG

    Chris Uppal Guest

    Steve Bosman wrote:

    > > This will zero-divide if the line is vertical.
    > >

    > I'm sure I stated non-vertical lines. Vertical lines (like horizontal
    > lines) are trivial to detect a distance from.


    Agreed, but why bother with special cases ?


    > Good point, completely forgot it was for a line segment :) Can't think
    > of a test for this at the moment...


    As best as I can remember, my earlier posted code was based on dropping a
    vertical from the point to the (infinite) line. It uses the parametric form of
    the equation for the line in a specific form where "t" is the distance along
    the line starting at "from" and moving towards "to". the:

    double t = x_ft*x_fp + y_ft*y_fp;

    expression (where x_ft is the delta in X between From and To, and so on -- poor
    naming I know, but it came from the equations) computes the value of "t" for
    the point on the (infinite) line which is closest to the mouse position. Then
    if "t" is either negative or greater than the distance between "from" and "to",
    then the mouse must be closest to the corresponding end-point. Otherwise, the
    distance is that from the point implied by 't' on the line segment (obtained by
    plugging "t" into the parametric line equation).

    For all I know, there are much better ways of computing it. But it works for
    me...

    -- chris
     
    Chris Uppal, Feb 24, 2005
    #11
  12. SPG

    Steve Bosman Guest

    Steve Bosman wrote:
    > Chris Uppal wrote:
    > > I haven't checked the details (can't be bothered, to be honest ;-)

    > but you are
    > > computing the distance to the infinite line defined by the

    equation,
    > not to the
    > > finite line segment. For instance the distance from the point (20,

    > 20) to the
    > > line /segment/ from (0,0) to (10, 10) should not be zero, but 10.
    > >

    > Good point, completely forgot it was for a line segment :) Can't

    think
    > of a test for this at the moment...


    Okay got it, but it is getting way too complicated.

    First post gives square distance to infinite line (lets call this d2).
    To check whether this is same as distance to line segment the following
    should work.

    4. Calculate square of distance from start to end point.
    5. Calculate square of distance from start to test point.
    6. Calculate square of distance from finish to test point.

    4 to 6 use something like this
    private static int distanceSqr(Point a, Point b) {
    int dx = (a.x-b.x);
    int dy = (a.y-b.y);
    return dx*dx+dy*dy;
    }


    7.
    (5)-d2 gives square of distance from start to test point (parallel to
    line)
    8.
    (6)-d2 gives square of distance from finish to test point (parallel to
    line)

    If either (7) or (8) is larger than (4) distance d2 is not correct and
    answer is the minimum of (5) or (6).

    Assuming Chris' code works my method is way too complicated and there
    is obviously something I have forgotten since my maths degrees.

    Ho hum, nevermind

    Steve
     
    Steve Bosman, Feb 24, 2005
    #12
  13. SPG

    Steve Bosman Guest

    Chris Uppal wrote:
    > Steve Bosman wrote:
    >
    > > > This will zero-divide if the line is vertical.
    > > >

    > > I'm sure I stated non-vertical lines. Vertical lines (like

    horizontal
    > > lines) are trivial to detect a distance from.

    >
    > Agreed, but why bother with special cases ?
    >
    >
    > > Good point, completely forgot it was for a line segment :) Can't

    think
    > > of a test for this at the moment...

    >
    > As best as I can remember, my earlier posted code was based on

    dropping a
    > vertical from the point to the (infinite) line. It uses the

    parametric form of
    > the equation for the line in a specific form where "t" is the

    distance along
    > the line starting at "from" and moving towards "to". the:
    >
    > double t = x_ft*x_fp + y_ft*y_fp;
    >
    > expression (where x_ft is the delta in X between From and To, and so

    on -- poor
    > naming I know, but it came from the equations) computes the value of

    "t" for
    > the point on the (infinite) line which is closest to the mouse

    position. Then
    > if "t" is either negative or greater than the distance between "from"

    and "to",
    > then the mouse must be closest to the corresponding end-point.

    Otherwise, the
    > distance is that from the point implied by 't' on the line segment

    (obtained by
    > plugging "t" into the parametric line equation).
    >
    > For all I know, there are much better ways of computing it. But it

    works for
    > me...
    >

    Knew I was missing something :) now I know what t is I understand what
    you were attempting to do. I wasn't having a go at your code since OP
    had stated in one of his posts that it didn't appear to be working,
    just trying to give an alternate method.
     
    Steve Bosman, Feb 24, 2005
    #13
  14. SPG

    Steve Bosman Guest

    Chris Uppal wrote:
    >
    > For all I know, there are much better ways of computing it. But it

    works for
    > me...
    >

    Well I've now tried your way and tried my (revised) way, both are
    giving the same answers and yours seems the most elegant to me.

    Steve
     
    Steve Bosman, Feb 24, 2005
    #14
  15. SPG

    SPG Guest

    All

    Thank you all very much for your help here.
    Steve and Chris have been tremendous in helping me solve my massive (but
    insignificant to the rest of the business!) problem,

    I guess I should have listened harder during Math!

    Cheers again,

    SPG
    "SPG" <> wrote in message
    news:3KPRd.18689$...
    > Hi All,
    >
    > I have a bit of a problem that you may be able to solve for me.
    > I need to draw a line on a canvas, using the awt.graphics class only.
    >
    > Let me stress from the start I have to support MS JVM here..... Hence I
    > cannot use and of the 2d functionality (Suckola)
    >
    > Anyhow, The drawing part is easy, and I have done this. But.. I need to
    > detect a mouse click on any part of the line itself, so I can allow the
    > user to move it.
    >
    > The code posted works, but it only detects intersection inside the
    > rectangle that is startx, start.y, end.x, end.y
    > I need to actually refine this so I only get the intersection where the
    > x,y coords are physically on the line..
    >
    > Some one out there knows the math on how to do this... Please help!!!
    > Assume a mouseClick event will fire a call into the intersects(x,y)
    > method..
    >
    > Cheers,
    >
    > Steve
    >
    > import java.awt.*;
    >
    > public class TrendLine {
    > private Point _start;
    > private Point _end;
    >
    > public TrendLine() {
    > _start = new Point(0,0);
    > _end = new Point(0,0);
    > }
    >
    > public void setStart(Point _start) {
    > this._start = _start;
    > }
    >
    > public Point getStart() {
    > return _start;
    > }
    >
    > public void setEnd(Point _end) {
    > this._end = _end;
    > }
    >
    > public Point getEnd() {
    > return _end;
    > }
    >
    > public boolean intersects(int x, int y){
    > if( (x >= _start.x && x <= _end.x)
    > || (x <= _start.x && x >= _end.x)){
    > if( ( y >= _start.y && y <= _end.y)
    > || (y <= _start.y && y >= _end.y)){
    > return true;
    > }
    > }
    > return false;
    > }
    >
    > public void draw(Graphics g){
    > //Draw Line
    > g.drawLine(getStart().x, getStart().y, getEnd().x, getEnd().y);
    > g.setColor(c);
    > }
    > }
    >
     
    SPG, Feb 27, 2005
    #15
  16. SPG

    ACE01

    Joined:
    Nov 7, 2006
    Messages:
    2
    line intersection

    hi people i need help on cracking this java code i am not good at java i need some1 to help me the code is

    /**
    * Routine to calculate where a pair of lines intersect (if they do).
    *
    * @param (integers) X co-ordinates and Y co-ordinates of both ends of two lines.
    * output: matrix size 3 to hold (X,Y) of intersection,
    * and integer to indicate which type of intersection
    * 3 = true intersection
    * 2 = line segment 2 only
    * 1 = line segment 1 only
    * 0 = not on either segment
    * -1 = parallel
    * -2 = colinear
    */
    public int [] lineIntersection(int x1Coord1, int y1Coord1,
    int x1Coord2, int y1Coord2,
    int x2Coord1, int y2Coord1,
    int x2Coord2, int y2Coord2) {
    int result [];
    result = new int [3];

    // replace the following three lines of code with the correct code
    result[0]=0; // X co-ordinate
    result[1]=0;// Y co-ordinate
    result[2]=0; // intersction type

    return result;
    } // end lineIntersection()


    /**
    * lineEquation routine to calculate the equation
    * of a straight line from the co-ordinates
    * of two points on that line.
    * The equation is of the form AX + BY + C = 0
    *
    * @param X and Y co-ordinates of two points on line
    *
    * output: matrix size 3 to hold coefficients of line equation (A, B, and C)
    *
    */

    public int [] lineEquation(int xCoord1, int yCoord1, int xCoord2, int yCoord2) {
    int [] result;
    result = new int [3]; // to hold values of A, B, and C

    // replace the following three lines of code
    // with the correct code

    result[0] = 1;
    result[1] = 1;
    result[2] = 1;

    return result;
    } // end lineEquation()
     
    ACE01, Nov 7, 2006
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    1
    Views:
    3,436
    Betty
    Apr 11, 2005
  2. PyPK

    Straight line detection

    PyPK, Sep 28, 2005, in forum: Python
    Replies:
    3
    Views:
    636
    Nigel Rowe
    Oct 15, 2005
  3. Laurent Laporte
    Replies:
    2
    Views:
    655
    Marc 'BlackJack' Rintsch
    Dec 29, 2005
  4. Emile van Sebille

    Re: Python Line Intersection

    Emile van Sebille, Apr 9, 2010, in forum: Python
    Replies:
    1
    Views:
    740
    Josh English
    Apr 9, 2010
  5. Chris Rebert

    Re: Python Line Intersection

    Chris Rebert, Apr 9, 2010, in forum: Python
    Replies:
    5
    Views:
    2,539
    Lie Ryan
    Apr 10, 2010
Loading...

Share This Page