[solved]Line Line Intersection

If you calculate the POI then you can skip step 3 as it's certainly on both of them.

One thing you should definitely... fear... is the inherent inaccuracy of floating point data types. I.e. there's no such thing as an intersection, only "coming really, really close". Instead of

x1 == x2;

use

compare(x1, x2);

where the function compare does something like

if (fabs(x1 - x2) < PRECISION) return 1;
else return 0;

You can #define the PRECISION to be anything reasonable, e.g. 0.0001.

that assumes the liens are infinite in both directions :P

// a {x,y}, b {x,y}, c {x,y}, d {x,y}\\ v {}, q {}\\ amc {}, denom, s, tv.x = b.x-a.x;v.y = b.y-a.y;q.x = d.x-c.x;q.y = d.y-c.y;denom = v.y*q.x - v.x*q.y;if(denom ~=~ 0) { /*lines are parallel*/ return; }denom = 1/denom;amc.x = c.x-a.x;amc.y = c.y-a.y;t = (amc.y*q.x - amc.x*q.y)*denom;if( t < 0 || t > 1 ) { /*no intersection*/ return; }s = (amc.y*v.x - amc.x*v.y)*denom;if( s < 0 || s > 1 ) { /*no intersection*/ return; }/*intersection*/ return {a.x + t*v.x, a.y + t*v.y }

hm, so floating points aren't the way to go? What about Doubles, or is it always the same issue.

I'm doing this in Java by the way.

I'd prefer to do it with segments, but in order to do that don't you just do the same calculation with the infinite lines, then check to see if the point exists on both segments?

have you just ignored my post?

No I didn't I just wasn't thinking. Sorry about that it's time to put it all into code. Thanks both of you.

It always says there's No Intersection at T. Any obvious error's with the code? I'm gonna continue debugging I think I'm missing something...

	public void checkForIntersection(){		double line1x1 = 0, line1y1 = 0,				line1x2 = 0, line1y2 = 0;		double line2x1 = 0, line2y1 = 0,				line2x2 = 0, line2y2 = 0;		if( walls.get(0).splatAxis.equals("XY") ){			line1x1 = (double)(walls.get(0).X - (walls.get(0).Width / 2 ) );			line1y1 = (double)(walls.get(0).Z - (walls.get(0).Depth / 2 ) );						line1x2 = (double)(walls.get(0).X + (walls.get(0).Width / 2 ) );			line1y2 = (double)(walls.get(0).Z + (walls.get(0).Depth / 2 ) );		}		line2x1 = (double)Camera.X;		line2y1 = (double)Camera.Z; 				line2x2 = (double)CameraLook.X;		line2y2 = (double)CameraLook.Z; 				double line1XDelta = line1x2 - line1x1;//v		double line1YDelta = line1y2 - line1y1;//v				double line2XDelta = line2x2 - line2x1;//q		double line2YDelta = line2y2 - line2y1;//q				double denominator = (line1YDelta * line2XDelta) - (line1XDelta - line2YDelta);		if(denominator != 0) {//Lines are parrellel if this is false.			System.out.println("Not Parrellel");			denominator = (1 / denominator);				double AMCX = line2x1 - line1x1; 			double AMCY = line2y1 - line1y1;  						double t = ( ( AMCY * line2XDelta) - ( AMCX * line2YDelta ) ) * denominator;						if( t < 0 || t > 1 ) { 				//No intersection				System.out.println("No intersection at T.");			}else{								double s = ( ( AMCY * line1XDelta )  - ( AMCX * line1YDelta ) ) * denominator;								if( s < 0 || s > 1 ) { 					//No Intersection					System.out.println("No intersection at S.");				}else{					System.out.println("Intersection at: ");					System.out.print( ( line1x1 + ( t * line1XDelta ) ) + " , ");					System.out.println( line1y1 + ( t * line1YDelta ) );				}							}					 }			}

Edit: Danggg does that equation you gave me only work if the points for line AB and CD are between 0 and 1?

whats this about line sweep algorithms?
http://en.wikipedia.org/wiki/Sweep_line_algorithm

[Edited by - Cakey on April 1, 2009 5:09:59 PM]

Nevermind I figured it out. Thanks though!

http://sirisian.pastebin.com/f150d8f44