Line intersection detection....

[SPG]

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);
}
}

 

[Chris Uppal]

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]

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..

 

[SPG]

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

 

[Jacob]

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.

 

[Steve Bosman]

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

 

[Chris Uppal]

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]

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

 

[Steve Bosman]

Steve Bosman wrote:

I think there are a couple of problems with this.



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.

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...

 

[Chris Uppal]

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]

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

 

[Steve Bosman]

equation,
not to the
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]

Agreed, but why bother with special cases ?



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]

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

 

[SPG]

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

 

[ACE01]

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()