If you''re working in 2D, there''s an easy solution. A ''general'' line equation is

Ax + By + C = 0

We can write

D = Ax + By + C

(if A² + B² = 1, then D is the distance, but it''s not important).

You can use this equation to find the relationship between any point and the line. If D < 0, then the point is on one side of the line, if D > 0, it''s on the other. If D = 0, the point is on the line.

So, ray-square intersection is quite easy: there is an intersection if D = 0 for any of the four vertices, or if the sign of D is not the same for all four vertices (meaning that some are on one side, and the rest are on the other side).

Cédric

P.S.: Just reread your post... Is your ray "infinite", or is it a line segment?

While I think Dreamforger's equations are correct, I'm not sure how you can get a solution from the last one. Here's the method I'd suggest (using some of his notation) that works for an arbitrary polygon:

Let L1 be the start of the line, and L2 the end. Then the line's direction is (L2 - L1). So the line can be written as

L1 + a*(L2-L1)

where a is a number between 0 and 1.

Let N be the unit normal vector of the plane that the polygon (square) lies in (all the vertices need to lie in the same plane for this to work), and let P1 be any point on this plane (take one of the polygon's vertices for example).

Then, consider the vector from P1 to a point on the line. This vector will be:

(L1 + a*(L2-L1)) - P1

When this vector is lieing in the plane, the point of intersection with the line will clearly be in the plane too. This vector lies in the plane if the dot product of it with N is 0:

[(L1 + a*(L2-L1)) - P1] . N = 0

Rearranging this gives:

(L1 - P1).N + (a*(L2-L1)).N = 0

and then:

a = [(P1 - L1).N] / [(L2-L1).N]

which in turn gives the point of intersection by putting this 'a' value back into the line equation (L1 + a*(L2-L1)). Of course, (L2-L1).N cannot be 0 if this is to work. This makes sense geometrically, as if it were 0, the line would be parallel to the plane, and they would clearly never intersect. So it's probably best to check if it is 0 before doing the division. If this 'a' value turns out to be not in the range [0,1], then the line segment specified by L1 and L2 does not intersect the plane (but would if it was bigger).

So now you've got a point that is on the line and in the plane (unless they are parallel, or the line doesn't stretch far enough). All that's left to do now is to determine if this point is inside the polygon (square). There are several ways of doing this I think, and I can describe one of them to you if you want.

I'm fairly sure this method is sound, but it is something I've made up, rather than getting it from somewhere reliable...

Miles

[EDIT: just read cedricl's post, and if you mean the line to be infinite, then take out the check that a is in [0,1]. Oh, and I've realised that if the line lies in the plane, they may still intersect (this would mean that (L2-L1).N = 0, which I've said indicates no intersection). I'll have a think about that one ]

[edited by - Miles Clapham on July 8, 2002 9:35:14 AM]

Here''s an idea for when the line is in the same plane as the polygon. This can be determined, for example, by seeing if both (P1 - L1).N and (P1 - L2).N are 0. Then, the line intersects the the polygon if it intersects any of the sides of the polygon.

Miles

[EDIT: OmniBrain nipped in while I was typing This is meant to refer to Dreamforger]

Ah, sorry, I should have spotted that one

Just a little thing...

In order to solve those equations, the determinant of the matrix (3x3) must be non-zero. If you work out what that means in terms of u.x, etc., and do a bit of rearranging, you can get this equation:<br><br>U . (V x W) = 0 (where x is the vector cross product).<br><br>This is<br><br>(L2-L1) . ((P1-P2) x (P1-P3)) = 0<br><br>and ((P1-P2) x (P1-P3)) is a normal to the plane the square lies in. So what it is saying is that the line is parallel to the plane (square), and that there is no solution to the equation when this is true. Well of course, that makes sense, as there shouldn't be any solution when they are parallel, as they would never intersect.<br><br>So, what am I getting at? Well, just to be careful that if you use the simultaneous equations method, you still need to take this into consideration. The procedure that solves the equations should be aware of the case when they are unsolvable, and return an error accordingly.<br><br>There is also the question of what happens when the line lies in the plane of the square. In this case, as I mentioned a few posts ago, it is still possible to have an intersection (and not have one). When the line is in the plane, they will of course be parallel. I'm not sure, however, whether or not the equation-solving procedure would still work in this case. I'm guessing it wouldn't work, as I imagine it would be using either matrix inversion, or row reduction. Besides, which point in the intersection would the values of a,b and c refer to, since there are an awful lot to choose from?<br><br>So I believe you still need to do the check for the line lieing in the plane, and then do the corresponding, slightly awkward, test for that case. You'd probably be able to get by without considering this, as if you're using floats, the chance of the line being exactly parallel to the plane in the first place might be quite small. But bad things might happen, and I really wouldn't recommend it.<br><br>I think still prefer my method, which I reckon would be a bit faster, becase there are fewer ops involved, and no need to call the eq solver. The problem's special cases are still a little tedious though, so maybe there's another way?<br><br>Miles<br><br><SPAN CLASS=editedby>[edited by - Miles Clapham on July 9, 2002 6:22:59 AM]</SPAN>