CODEWITHSUNDEEP
mathvectorlua3d
burli
burli

Reputation: 345

How can I determine if a point is on a line between two other points in 3d in Lua (or other language)?

I have a line between two points a and b (3d vectors) and a third point p (from scalar projection).

I want to determine if the third point p is on the line between a and b or not between them.

What is the most efficient algorithm for the LuaJIT? Other languages would be fine too, but efficiency is important

Thanks to numberZero I got this code and it seems to work

function vec3d:is_between(a, b)
    local ab = b - a
    local ap = self - a
    local lp = ap:len()
    local lb = ab:len()
    local dot = ap:dot(ab) / (lp * lb)
    return lp < lb and dot > 0.95
end

Upvotes: 0

Views: 727

Answers (2)

number Zero
number Zero

Reputation: 66

If you know that the points lie on a single line, you may just calculate a dot product, and if 0 ≤ 〈AB, AP〉 ≤ 〈AB, AB〉, then P is between A and B. But note that if P is not exactly on the line, this method may give strange results. But it should be the fastest.

You may also want to calculate 2 values, distance from P to AB and (orthogonal) projection of AP onto AB. The latter is AP_AB = 〈AP, AB〉 / 〈AB, AB〉 (in AB units, so that if AP and AB are collinear, AP = AB * AP_AB), and the former is ρ(P, AB) = ρ(AP, AB * AP_AB) = |AP - AB * AP_AB|. So, if the ρ(P, AB) is small, you decide that if 0 ≤ AP_AB ≤ 1, then P is between A and B

Upvotes: 1

GoojajiGreg
GoojajiGreg

Reputation: 1183

If you already know the three points are collinear, you could compute the vector AP from a to p and the vector AB from a to b. If p is between a and b, then the dot product of AP and AB will equal 1 (i.e. the vectors point in the same direction) and the vector magnitude of AP will be less than that of AB.

If you don't know whether the points are collinear, it's easy to check. You can determine the collinearity of three points xi = (xi, yi, zi) for i = 1, 2, 3 by implementing a test on the ratio of distances:

x2 - x1 : y2 - y1 : z2 - z1 = x3 - x1 : y3 - y1 : z3 - z1.

as explained in this Wolfram Mathworld article on Collinearity. From the same article, an even easier condition

is obtained by noting that the area of a triangle determined by three points will be zero iff they are collinear (including the degenerate cases of two or all three points being concurrent), i.e....in expanded form

x1( y2 - y3 ) + x2( y3 - y1) + x3( y1 - y2 ) = 0.

Upvotes: 2

Related Questions