Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working on a trajectory clustering algorithm (in C++) and one of the steps required in this algorithm is to take a set of 3d line segments (D), and for each line segment (L) in D, to calculate an epsilon neighborhood for it to see which other line segments are close to it.

All of the research I have done returns how to do epsilon neighboodhoods with respect to points but not line segments. How would I go about solving this problem?

share|cite|improve this question
If you are given a list of line segments, you just can calculate the distance between L and each other segment and select those which are within epsilon. The usual use of an epsilon neighborhood would be for you to describe all line segments within epsilon of a given one. – Ross Millikan Mar 29 '11 at 17:16
how would i go about calculating that distance though? calculating distance between segments is different than points right? would it be the distance between the endpoints or something else? – basil Mar 29 '11 at 18:25
See…, and also…. The first solves the problem for line segments elegantly, the second only solves it for lines but gives you an idea of how this sort of thing is done without the complications from the limitedness of the segments. Also, the distance between the line segments is $\ge$ the distance between the lines on which they lie, so you can do the easy calculation in the second link first and skip the first one if the result is $>\epsilon$. – joriki Mar 29 '11 at 19:01
@basil: I assumed you were using the same definition of distance between line segments as in your previous post. If not, joriki's links are good. – Ross Millikan Mar 29 '11 at 19:18
I am working out the math for the first link. I am going with $L_1$ going from $Pt_1$=[10.5,7.32,9.09] to $Pt_2$=[22.0, 15.1,23.0] (with the vector being $Pt_1-Pt_2$=[11.5,7.78,13.91]) and with $L_2$ going from $Pt_3$=[14.0,4.11,15.1] to $Pt_4$=[30.08,7.99,31.2] (vector being $Pt_3-Pt_4$=[16.08,3.88,16.1]) It seems to be straighforward, but I am uncertain what it means when it talks about $r_1,r_2,e_1,e_2$. How do I calculate these? – basil Mar 30 '11 at 15:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.