Well, I''ve done extensive searching on GameDev and Google on this topic and have found heapsa posts and answers to it. The problem is that I don''t understand how to turn _any_ of them into code In fact I don''t even understand any of them. What I need is to find if and where two lines (start point, end point) intersect. Here''s my skeleton code:
And that''s as far as I have got So...would anyone mind filling out Intersect() for me? *big, sheepish grin* ---------------------------------------------------------- "Go out with me you will." - Young Yoda''s favourite pickup line

hi... i just did some math & programming 2 help u...

that''s my result function :


bool Intersect(Line l1, Line l2, Vector & out)
{
float h1, h2;
float i1, i2;

float S1X, S1Y, S2X, S2Y;
float E1X, E1Y, E2X, E2Y;

float m1, m2;

float sx, sy; // intersection x & y

S1X = l1.start.x; S1Y = l1.start.y;
E1X = l1.end.x; E1Y = l1.end.y;

S2X = l2.start.x; S2Y = l2.start.y;
E2X = l2.end.x; E2Y = l2.end.y;

float swap;

if (S1X > E1X) // if start > end, swap ''em
{
swap = E1X; E1X = S1X; S1X = swap;
swap = E1Y; E1Y = S1Y; S1Y = swap;
}

if (S2X > E2X) // if start > end, swap ''em
{
swap = E2X; E2X = S2X; S2X = swap;
swap = E2Y; E2Y = S2Y; S2Y = swap;
}

h1 = E1Y-S1Y; h2 = E1X-S1X;
i1 = E2Y-S2Y; i2 = E2X-S2X;


// S1Y + m1*(x-S1X) = S2Y + m2*(x-S2X);

if ( (h2==0.0f) && (i2 == 0.0f))
{
return false; // if h2 & i2 == 0, both lines are parallel to y-axis... no intersection.
}

bool calced = false;

if (h2==0.0f) // if line #1 parallel to y-axis, calc special
{
m2 = i1/i2;
sx = S1X; sy = S2Y+m2*(sx-S2X);
calced = true;
}

if (i2==0.0f) // if line #2 parallel to y-axis, calc special
{
m1 = h1/h2;
sx = S2X; sy = S1Y+m1*(sx-S1X);
calced = true;
}

if (!calced) // if not calced before, calc now...
{
m1 = h1/h2;
m2 = i1/i2;

if (m1==m2) return false; // if m1 & m2 are equal, lines are parallel or equal... no intersection.


sx = (S2Y - m2*S2X - S1Y + m1*S1X) / (m1-m2);
sy = S1Y+m1*(sx-S1X);
}

if (!( ((sx <= E1X) && (sx >= S1X)) && ((sx <= E2X) && (sx >= S2X)) ) )
return false; // if intersection not within lines'' "borders"

out.x = sx;
out.y = sy;

return true;
}


didn''t check it for all cases but i think it should work for all possible pair of lines
you can of course optimize this function... i just wrote it down quickly & for (semi-) good understandability

hope, this helps you !

If I have made no fault, I think that I have a much shorter solution for your problem...

Line1: from A(a0/a1) to B(b0/b1)
Line2: from C(c0/c1) to D(d0/d1)
IntersectionPoint: P(p0, p1)

...
s = (c1 - d1) * (b0 - a0) - (c0 - d0) * (b1 - a1);
if (s == 0)
{
// Lines don't intersect
}
s = ((c1 - a1) * (b0 - a0) - (c0 - a0) * (b1 - a1)) / s;
if (s < 0 || s > 1)
{
// Lines don't intersect
}

p0 = c0 + s * (d0 - c0)
p1 = c1 + s * (d1 - c1)
....

I hope that I don't tell you something wrong..
please tell me if it works..

[edited by - Kaesebrot on May 27, 2002 9:46:20 AM]

yes... that one also works perfect...

but mine looks like a lot more work

(Kaesebrot''s version is a lot more optimized & better ! so don''t use mine ! )

Thanx alot guyz

----------------------------------------------------------
"Go out with me you will." - Young Yoda''s favourite pickup line

Hmmm... I''m getting a very odd problem with Kaesebrot''s method. It works fine apart from when I have a long line going away from the other line. It works ok with relatively short lines. A bit of ASCII art to illustrate the problem:

  |  |  |     |   --------------------------------------  |  |  | 

For some reason it detects a collision with the line on the left

Here''s my code:


Any help would be appreciated

----------------------------------------------------------
"Go out with me you will." - Young Yoda''s favourite pickup line

  ^^^Anybody? 

----------------------------------------------------------
"Go out with me you will." - Young Yoda''s favourite pickup line

I''m no C++ programmer, but I don''t see where you''re passing more than one line/ray to check...

where do c and d come from?

quote:I''m no C++ programmer, but I don''t see where you''re passing more than one line/ray to check...

where do c and d come from?

The Intersect function is encapsulated within the Ray class, so I only pass one Ray to check against it. The end result is that I''m still checking two lines. Thanx for the reply tho

----------------------------------------------------------
"Go out with me you will." - Young Yoda''s favourite pickup line

i''ve checked kaesebrot''s code with these 2 lines :

l1.start.x = 0.0f;
l1.start.y = 2.0f;
l1.end.x = 0.0f;
l1.end.y = 0.0f;

l2.start.x = 2.0f;
l2.start.y = 1.0f;
l2.end.x = 2000.0f;
l2.end.y = 1.0f;

this should be similar to your example, right ?
it works well with his algorithm... i''ve also checked your code & you didn''t do any mistakes...

i''ve never seen before, that you can declare functions in a struct !?
are you sure, this works ? maybe c++ compiles something wrong ?
in pascal (few years ago) i remember, that you could only use member-functions, when you''ve called a constructor before (or if a standard-constructor was called before), because the function-pointers for an object where set in the constructor. this could also be true for c++... maybe you should try to make your structs classes & allocate your objects by
ray = new Ray();
(same thing for Vector).

i''m not sure about this... but you should check this !

maybe that can help...