CODEWITHSUNDEEP
c#c++graphicsgeometry
Exploring_Programming
Exploring_Programming

Reputation: 81

Check if a 3D Point lies on a given 3D line(between two 3D Points)

I have two 3D Points viz. (x1,y1,z1) and (x2,y2,z2) and a 3D Point (x,y,z). I would like to know if (x,y,z) lies on the line connecting (x1,y1,z1) and (x2,y2,z2).

I tried the following algorithm:

    if ((((x - x1) / x2-x1) == ((y - y1) / y2-y1)) && (((x - x1) / x2 - x1) 
== ((z - z1) / z2- z1)) --> then,the 3D Line intersects (x,y,z)

But,what if my x1 = x2 (or) y1 = y2 (or) z1=z2? Then I would be getting an error saying "Division by zero" is not possible.

I would be glad,if someone can propose some alternative method.

Thanks in Advance.

Upvotes: 3

Views: 4362

Answers (5)

Spektre
Spektre

Reputation: 51923

simple dot product can do this easily ... so let consider we got line defined by two points p0,p1. Any point p on that line will have the same or negative slope to any of the endpoints so

|dot(p1-p0,p-p0)|/(|p1-p0|*|p-p0|) = 1.0

to make it more robust with floating point compare like this:

|dot(p1-p0,p-p0)|/(|p1-p0|*|p-p0|) >= 1.0-1e-10;

Where 1e-10 is small enough epsilon ... rewriten to code:

dx=x1-x0;
dy=y1-y0;
dz=z1-z0; 

ex=x-x0;
ey=y-y0;
ez=z-z0;

q =dx*ex;
q+=dy*ey;
q+=dz*zy;
q*=q;
q/=(dx*dx+dy*dy+dz*dz);
q/=(ex*ex+ey*ey+ez*ez);

if (q>=1.0-1e-10) point p(x,y) is on the line
 else p(x,y) is not on line

As you can see no need for the sqrt we can compare the power instead ...

However you should handle edge case when p==p0 then either use p1 or return true right away.

In case you want points only inside the line segment (not outside the edge points) then you need a slight change in code

0.0 <= dot(p1-p0,p-p0)/|p-p0| <= 1.0

So:

dx=x1-x0;
dy=y1-y0;
dz=z1-z0; 

ex=x-x0;
ey=y-y0;
ez=z-z0;

q =dx*ex;
q+=dy*ey;
q+=dz*zy;
if (q<0.0) p(x,y) is not on line
q*=q;
q/=(ex*ex+ey*ey+ez*ez);

if (q<=1.0) point p(x,y) is on the line
 else p(x,y) is not on line

btw the result of the dot product gives you ratio of one vector projected to another perpendicularly or cos of the angle between them (if they are normalized) so for parallel vectors the result is 100% of length or 1.0. If you tweak the 1e-10 value using goniometry and p-p0 you can convert this to detect points up to some perpendicular distance to line (which might get handy for thick lines and or mouse selecting).

Upvotes: 2

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171177

As you yourself point out, doing this in a robust way is not trivial. Therefore, I suggest you don't reinvent the wheel and use a geometric library. I have good experience with using Wild Magic from geometrictools.com.

In your case, the predicate to use would be gte::DCPQuery to get the distance between a point and the line, and then test if it's close enough to zero for your purpose of "on the line."

An example of use could look like this:

using namespace gte;

Line3<double> line({x1, y1, z1}, {x2 - x1, y2 - y1, z2 - z1});
Vector3<double> point{x, y, z};

DCPPoint3Line3 query;
auto result = query(point, line);
bool pointIsOnLine = (result.distance < some_epsilon);

(Code note touched by compiler, intended to show the approach, not to be "semicolon-perfect").

Upvotes: 0

gtosto
gtosto

Reputation: 1341

if you are not concerned about performance issue you can use the parametric equation of a segment in the space.

P(t) = P0 + t(P1 - P0) where P0 and P1 are 3d point and t is a parameter ranging from 0 to 1.

this lead to 3 equations

x(t) = x0 + t(x1 - x0)
y(t) = y0 + t(y1 - y0)
z(t) = z0 + t(z1 - z0)

so to check if your (x,y,z) point lies in the line, you could get an initial value for t, for example t = (x - x0)/(x1-x0) then check if that satisfies the other two equations

t = (x - x0)/(x1-x0)

if ( (y0 + t(y1-y0) == y) and (z0 + t(z1-z0) == z) ) then
 ---> we are in the line

Like @Jay pointed out, this is floating point math you have to deal with some tolerance with values. For example to test y could be y0 + t(y1-y0) - y < 0.001

Upvotes: 0

vineeth560
vineeth560

Reputation: 89

To solve the above-mentioned problem you need to check the area of the triangle considering them as 3 points in the 3-d space. To find the area go through this link. If area = 0 then given points are collinear.

Upvotes: 0

Jay
Jay

Reputation: 656

I would use point-line distance measurement, and return true if the distance is less than some error threshold close to zero.

To elaborate, we are using a line made of two points, p1 and p2. We want to know if p3 is on the line. First we find d using the point-to-line distance formula.

d = ((p0 - p1).cross(p0 - p2)).length() / (p2 - p1).length()

That is, assuming you can use +, -, cross, length operations. You might prefer to find d squared for performance reasons.

d2 = ((p0 - p1).cross(p0 - p2)).lengthSquared() / (p2 - p1).lengthSquared()

Now, if d or d2 are exactly zero, then you must be on the line. But this is floating point arithmetic so I would allow a little bit of leeway depending on your application. So in essence, d < 1e6 or something should do the trick.

Upvotes: 1

Related Questions