CODEWITHSUNDEEP
geometrycollision-detection
GreenFox
GreenFox

Reputation: 485

Equation for Sliding Collision of LineSegments

I need an equation to find point F. Point A, B, and D are known. Point F is unknown. Point F is on line AB. Line AB is perpendicular to line DF. What is the equation for F?

Upvotes: 0

Views: 208

Answers (3)

Phil H
Phil H

Reputation: 20141

I'm assuming you want something computationally fast, since you mention 'collision', and this is Stack Overflow. First, a diagram:

perpendicular intersection of AB and DF, with F the intersection point

We want to calculate the components of AF, which we'll label f = qi + pj. AFD forms a triangle, so we can get the length of f from AD, which we'll label d. Let's mark lengths in italics versus vectors in bold:

f = d cos(θ).

But trig is computationally expensive. So let's use the fact that the vector dot product between b (AB) and d is:

b · d = b d cos(θ)

The angle is the same because AF and AB are on the same line. Substituting in for dcos(θ):

b · d = b f

f = (b · d) / b

Now we have f, but we want its components p and q. Calling the angle to the horizontal φ:

q = f cos(φ)

p = f sin(φ)

But again we're avoiding trig. We know that f is along b, so f = kb, and in fact using the unit vector in the direction of b:

f = f (b/b)

Substituting our expression for f:

f = [(b · d) / b ] (b/b)

= [(b/ b) · d ] (b/b)

= [b · d] b / (b2)

Defining a factor k which is common to both components:

k = (bx dx + by dy) /b2

By keeping the b2 separate, we can avoid a square root operation to get the unit vector along b

Our components, then:

q = k bx

p = k by

Finally, add back in the offset of point A.

Fx = Ax + q

Fy = Ay + p

So, the pseudo code:

var vbx = Bx - Ax;   //vector b x component
var vby = By - Ay;   //vector b y component
var dot = vbx*(Dx-Ax) + vby*(Dy-Ay); // dot product of b and d
var k = dot/(vbx*vbx + vby*vby);  // inverse of square of vector b length
var fx = Ax + k*vbx
var fy = Ay + k*vby

No square root calls, no trig, 8 additions/subtractions, 6 multiplications, 1 division. The only instabilities I can see are: divide by zero when A and B are at the same position, possible overflow calculating dot if AB is large and AD is large.

Upvotes: 1

mjfgates
mjfgates

Reputation: 3431

You haven't specified exactly where point F is along line DF, so there's no single answer. If you're just trying to find SOME point along a line perpendicular to line AB, from point D, then

F.x = D.x + (B.y - A.y)
F.y = D.y + (B.x - A.x)

will work.

Upvotes: 0

Jon
Jon

Reputation: 2532

First, find the slope of line AB with the point-slope formula using A and B's coordinates: Point Slope Formula

You can then find b to finished the equation for line AB: y = mx + b where m is the slope you already found and b is the y-intercept that you just found.

The slope of line DF would be the negative reciprocal of the slope of line AB. Plug this into the equation: y = mx + b where m is the negative reciprocal of the slope of line AB and b comes later.

Now, solve for b using the x and y values of point D, and plug that into the equation.

You should now have an equation for line DF and another equation for line AB. Now solve for the intercept of the two equations by setting them equal to one another and solving for x first and then plugging in x and finding y.

Here's an example.

A = (1, 2). B = (4, 8). D = (2, 5).

Line AB:

    (y - y1) = m*(x - x1)
    (1 - 4) = m*(2 - 8)
    -3 = m*(-6)
    0.5 = m

    y = (0.5)*x + b
    2 = (0.5)*1 + b
    2 = (0.5) + b
    1.5 = b

y = 0.5*x + 1.5

Line DF:

    m = -(1/mAB)
    m = -(1/0.5)
    m = -2

    y = -2*x + b
    5 = -2*2 + b
    5 = -4 + b
    9 = b

y = -2*x + 9

Intersection of AB and DF (i.e. coordinates of point F)

Line DF: y = -2*x + 9
Line AB: y = 0.5*x + 1.5

    -2*x + 9 = 0.5*x + 1.5
    9 = 2.5*x + 1.5
    7.5 = 2.5*x
    x = 3

    y = -2*x + 9
    y = -2*3 + 9
    y = -6 + 9
    y = 3

F = (3, 3)

Upvotes: 0

Related Questions