IsPointInsideSegment(pt, line) in Python

Question

Is there a nice way to determine if a point lies within a 3D line segment?

I know there are algorithms that determine the distance between a point and line segment, but I'm wondering if there's something more compact or efficient.

Answer 1

First, find the distance from the point to the line. If the distance from the point to the line is zero, then it's on the line.

Answer 2

Given three points A, B, and C -- where AB is your line and C is your other point, you can also restate your problem as two lines, AB and AC. If the angle between AB and AC is zero (i.e. if the area of the triangle ABC is zero) then your point C is on the line.

If you think about this in terms of angles, you can use the dot product of the two vectors (AB and AC) to find the angle between them. Some quick googling turns up a couple of useful links:

• http://knol.google.com/k/koen-samyn/dot-product-cross-product-in-3d/2lijysgth48w1/10#
• http://www.jtaylor1142001.net/calcjat/Solutions/VDotProduct/VDPTheta3D.htm

The bonus of this method is that it's easy to define tolerances in terms of angles; e.g. you may want to consider any point that falls within 5 degrees of the line to be "on the line" even though there is strictly some distance between the line and the point. Depending on your application, this may be more useful than an actual linear measurement.

Answer 3

One way to restate your question is to ask of the point is a solution to the equation which contains the line segment in question, and (if so) if it lies between the end points of the segment.

Since you don't describe the details of how you're representing your line segments and don't mention any modules or libraries that you're using I guess you'd have to code up the algebra yourself. (It's not trivial and my algebra is too rusty in any event).

You might consider looking at a library that does the work for you (either to incorporate into your project or to study its code). In this case I'd take a close look at:

• [PyEuclid]: http://code.google.com/p/pyeuclid/

... claims to be compatible with PyGame and supports objects for 2D and 3D vectors, rays, segments, and circles/spheres. Basically if the distance between your point and your segment is less than epsilon (some threshold appropriate to your calculations) then you treat that as an intersection.

(Although it doesn't explicitly say so in the docs that I read, I'm guessing that they must handle floating point rounding issues in their code somewhere. All of PyEuclid seems to be in a single 2200+ line .py file).