4

Possible Duplicate:
How do you detect where two line segments intersect?

Given two points a and b plus two vectors v and u I want to find a third point c, which is the point of intersection in the following manner:

vector2 intersection(vector2 a, vector2 v, vector2 b, vector2 u)
{
    float r, s;

    a + r * v = b + s * u;
    r * v - s * u = b - a

    r * v.x - s * u.x = b.x - a.x
    r * v.y - s * u.y = b.y - a.y
}

Is there any other way than using gaussian elimination to solve this system? Or is this the best (or at least an acceptable) way to handle this?

EDIT: Definition of vector2

typedef union vector2
{
    float v[2];
    struct { float x, y; };
} vector2;

a and b are also of type vector2, because the only difference between a point and a vector is in the the way it is transformed by an affine transformation.

Community
  • 1
  • 1
0xbadf00d
  • 17,405
  • 15
  • 67
  • 107
  • 1
    How is `vector2` defined ? And why are *points* a and b also of type `vector2` ? – Paul R Jan 10 '13 at 11:11
  • I had my explanation below. but regardless. why vector isn't just a struct? why you need the union and the"array"? – Roee Gavirel Jan 10 '13 at 12:05
  • This question has been marked as a duplicate by Gareth Rees, Paul R, Mark Dickinson, and 0xbadf00d because "This question has been asked before and already has an answer.". **BUT** that question has no accepted answer as of this writing. I don't think that a question should be marked as a duplicate unless the referenced question has an accepted answer. – user316117 Dec 28 '15 at 18:53

2 Answers2

1

Looks like an assignment problem to me. Here is the logic that will help you write the code.

Let us call the first Ray as R0.
Locus of a point on R0 is defined as P:

P = P0 + alpha x V0

For the second ray R1:

P = P1 + beta x V1

Since they should intersect:

P0 + alpha x V0 = P1 + beta x V1

alpha and beta are unknowns and we have two equations in x any y.

Solve for the unknowns and get back the point of intersection.

i.e.,

P0.x + alpha * V0.x = P1.x + beta * V1.x
P0.y + alpha * V0.y = P1.y + beta * V1.y

solve for alpha and beta.

If there is a real positive solution for both alpha and beta, rays intersect.
If there is a real but at least one negative solution for both alpha and beta, extended rays intersect.

Delgan
  • 18,571
  • 11
  • 90
  • 141
Ram
  • 3,045
  • 3
  • 27
  • 42
1

It's simple math.

But, first, check that you have intersection. If both vector are parallel you will fail to solve that:

// Edit this line to protect from division by 0 
if (Vy == 0 && Uy == 0) || ((Vy != 0 && Uy != 0 && (Vx/Vy == Ux/Uy)) // => Fail.

Then (I won't show the calculation because they are long but the result is):

R = (AxUy - AyUx + ByUx - BxUy) / (VyUx - VxUy)  
S = (Ax - Bx + RVx) / Ux

Hope that helped you.

xryl669
  • 3,376
  • 24
  • 47
Roee Gavirel
  • 18,955
  • 12
  • 67
  • 94