Velocity Reviews > Java > Line intersection detection....

# Line intersection detection....

Chris Uppal
Guest
Posts: n/a

 02-24-2005
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

Steve Bosman
Guest
Posts: n/a

 02-24-2005

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 ( 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
Guest
Posts: n/a

 02-24-2005

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
Guest
Posts: n/a

 02-24-2005

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

SPG
Guest
Posts: n/a

 02-27-2005
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" <(E-Mail Removed)> wrote in message
news:3KPRd.18689\$(E-Mail Removed) .uk...
> 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..
>
> 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);
> }
> }
>

ACE01
Junior Member
Join Date: Nov 2006
Posts: 2

 11-07-2006
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()