quote:

---

i''ve never seen before, that you can declare functions in a struct !?
are you sure, this works ? maybe c++ compiles something wrong ?

---

Structs are not different from classes for the compiler regardless that in structs members are public by default, and in classes they are private.

There is no problem with that, he can instantiate or allocate them with new, no problem.

Anyway, I think is a bad programming practice to put member functions inside of structures.

well... ok...

as i said, i don''t really know... not much time passed since i''ve changed from pascal to c++.

AdmiralBinary : your code seems to be correct...
maybe you''re passing wrong lines/parameters ?!?
what intersection coordinates do you get ?
if nothing can fix it, maybe you can do some extra-checking of the coordinates to see, if they are in the lines'' ranges...


but... it SHOULD work... (tested it for almost every case...)

quote:

---

Anyway, I think is a bad programming practice to put member functions inside of structures.

---

Yeah I know But I''m making a few sacrifices as far as neat code goes in order to finish this as soon as possible.

One question: Do I have to pass the lines in a specific order? I mean, will Intersect(r1,r2) have a different result from Intersect(r2,r1)?

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

Here''s some code which illustrates my problem:


Try it and you should find it thinks there''s a collision.

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

yes... you''re right... it really does report an intersection. and i''ve checked swapping the parameters ( called
Intersect(l2, l1); instead of Intersect(l1, l2) seems to make a difference... it doesn''t report an intersection the other way
''round..

well... i made some tests & added a few lines... i don''t really know if it works for ALL cases (since i still don''t understand what the code (the math behind it) completely), now, but it works for all cases it worked before PLUS your problem case.

here''s the code...

bool Intersect2 (Line l1, Line l2, Vector & out)
{
float a0, a1, b0, b1, c0, c1, d0, d1, p0, p1;
float s;

a0 = l1.start.x;
a1 = l1.start.y;
b0 = l1.end.x;
b1 = l1.end.y;

c0 = l2.start.x;
c1 = l2.start.y;
d0 = l2.end.x;
d1 = l2.end.y;

s = (c1 - d1) * (b0 - a0) - (c0 - d0) * (b1 - a1);
if (s == 0)
{
return false;
}

//

if (s < 0.0f)
{
a0 = l2.start.x;
a1 = l2.start.y;
b0 = l2.end.x;
b1 = l2.end.y;

c0 = l1.start.x;
c1 = l1.start.y;
d0 = l1.end.x;
d1 = l1.end.y;
s = (c1 - d1) * (b0 - a0) - (c0 - d0) * (b1 - a1);
if (s == 0)
{
return false;
}
}

//

s = ((c1 - a1) * (b0 - a0) - (c0 - a0) * (b1 - a1)) / s;
if ((s < 0) || (s > 1))
{
return false;
}

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

out.x = p0;
out.y = p1;
return true;
}


you can test this & give feedback, if you still have problems...
or just use the function, i gave you..
it works for all cases (i think). if you need more performance, you can still do a lot optimization to it.

That all seems pretty complicated. I remember this post from about a month ago that seemed to have a simpler solution.

Hey thanx everybody - it''s finally working. The only thing I had to add was this (before checking for collision):


Thanx again

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

Well, originally you were asking how the line intersection worked, so I think I'll explain Kaesebrot's algorithm (and point out the mistake in it). Also, I'm not sure if your solution (swapping points) will always return the correct result.

First of all, we know that if two lines are parallel, then they either intersect on all points (they are the same line) or don't intersect at all. In order to check if two lines are parallel you only need to check if their slopes are parallel. The slope of a line is defined to be the difference between y-values of two points on the line divided by the difference between the x-values of those points. Using this definition you'll see:

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

l1 slope: (b1 - a1) / (b0 - a0)
l2 slope: (d1 - c1) / (d0 - c0)

To check if the lines are parallel, set the slopes equal to each other:

(b1 - a1) / (b0 - a0) = (d1 - c1) / (d0 - c0)
(b1 - a1)(d0 - c0) = (b0 - c0)(d1 - c1)
(b1 - a1)(d0 - c0) - (b0 - c0)(d1 - c1) = 0

Note: This is where Kaesebrot's mistake was.

So if we let g = (b1 - a1)(d0 - c0) - (b0 - c0)(d1 - c1) then if g = 0 the lines are parallel and we don't need to do anything else. We don't worry about the case where the lines are the same because you can't return a single point of intersection since there are multiple points. Note: There is one case where there exists a valid intersection; this is when only the endpoints of the two lines are the same, if it is important then you can check for this special case.

Once we have determined the lines aren't parallel we need to find the point of intersection. One way of writing the general form of a line is:

x = x1 + t(x2 - x1)
y = y1 + t(y2 - y1)

Where two points on the line are (x1, y1), (x2 y2) and t is a real number. Since we're only interested in values of x between x1 and x2, t must be between 0 and 1 (the same argument applies with the y values). Using this definition we can say:

l1: x = a0 + t(b0 - a0)         l2: x = c0 + s(d0 - c0)    y = a1 + t(b1 - a1)             y = c1 + s(d1 - c1) 

The point of intersection between these two lines will occur where the x and y values of the two lines are equal.

ie.
a0 + t(b0 - a0) = c0 + s(d0 - c1)
a1 + t(b1 - a1) = c1 + s(d1 - c1)

Isolating t, we get:
t = ((c0 - a0) + s(d0 - c0)) / (b0 - a0) = (c1 - a1) + s(d1 - c1) / (b1 - a1)

Isolating s, we get:
s = ((b0 - a0)(c1 - a1) - (b1 - a1)(c0 - a0)) / ((b1 - a1)(d0 - c0) - (b0 - a0)(d1 - c1))

Note: The denominator here equals g, which we used earlier to check if the lines are parallel.

But we know that for all points on l2 0 <= s <= 1, so if s is not in this range then the lines don't intersect. If s is in this range we can just sub s back into the equation for l2 and solve for x and y.

Translating this into code:

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

Hopefully this will show you what's going on behind the algorithm.


Give a man a fish and you feed him for a day; teach him to use the Net and he won't bother you for weeks.


[edited by - thooot on June 3, 2002 10:08:32 AM]

I decided to have a crack at the problem, ignoring what everyone else has siad.. so it may be my solution is exactly whats been said, doesn't work, is the same but slower, or whatnot but anyway...

using Vector objects:

Vector a,b,c,d;


Vector f(b.y-a.y,(b.x-a.x)*-1);
Vector g(d.y-c.y,(d.x-c.x)*-1);

f.setLength(1);
g.setLength(1);

Vector h=c+g*((d-c)*((c-a).DOT(f))-(d-c)*((d-a).DOT(f)));

if ((h-a).DOT(f)>0 && (h-b).DOT(f)<0 && (h-c).DOT(g)>0 && (h-d).DOT(g)<0)
hit


if hit, h is impact point.
I just whipped this up, on paper, so it may be wrong.
and I'm sure it can be significantly simplified.

where:


float Vector::DOT(Vector a)
{
return x*a.x+y*a.y;
}


and setLength is just simple pythag.


[edited by - RipTorn on June 3, 2002 6:55:19 AM]

thooot : thx for the explanation... now it''s better 2 understand.

but the false report of an intersection that admiralbinary mentioned above still occurs with your code...
and still it only works right, if i add the lines of code i''ve put in Kaesebrot''s method (swapping the two lines, if s < 0 after first ''if'')

i don''t really get, why this happens, but maybe there''s some other (faster) way to do the testing right.