Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of $3$D points representing a line segment. Points are not equidistant distributed on the line segment. Points are also unordered. I also have the center point and the normal to the line segment All points in this point set definitly belong to the same line, i.e. no outliers

I'd like to calculate the length of this line segment by calculating the start and end points.

My first naive solution is to look for min and max $x,y,z.$ But this is wrong, since it ignores the line rotation. Most probably looking for min/max $x,y,z$ in accordance with the line normal should give the answer. But how can this be done?

share|improve this question
    
What is the normal to a 3D line segment? –  Rahul Aug 2 '12 at 10:56
    
the direction/rotation of the line segment –  Moataz Elmasry Aug 2 '12 at 10:58
    
My naive solution is to sort the points according to their $x, y, z$ coordinates (in this lexicographic order). Then look for the two extreme points according to that order. Is this what you've tried? –  user2468 Aug 2 '12 at 11:11
    
No its the vector perpendicular to the line –  Moataz Elmasry Aug 2 '12 at 11:20
2  
I would like to see an example in which finding the points that minimize and maximize $x$, $y$, and $z$ "is wrong" or "won't work". –  Rahul Aug 2 '12 at 11:29

3 Answers 3

up vote 2 down vote accepted

Calculating all distances is expensive. A cheaper solution is two find the bounding box in only ${\cal O}(n)$ comparisons.

Perform a linear search through all the points; find and record the six values of $\min x,$ $\max x,$ $\min y,$ $\max y,$ $\min z,$ and $\max z.$ Also, record the six points associated with each extrema: $$ \{ p_{\min x}, p_{\max x}, p_{\min y}, p_{\max y}, p_{\min z}, p_{\max z} \}. $$

If all the points one line, then the intersection of the line with the bounding box is exactly two points, and the list of six points above will have only two unique points: the end points.


Here is a picture of the bounding box from Wikipedia, you can easily see that in the case of a line, the intersection of your points set is just two vertices of the box.

share|improve this answer

One way would be to multiply all points by the rotation matrix corresponding to the line pointing in the $z$ direction. Then you simply find $\max z$ and $\min z$. A faster way would be to calculate the distance for each point from the center, and take the farthest points as the endpoints. The distance between them will give you the line's length.

share|improve this answer
    
can you further elaborate on: "the rotation matrix corresponding to the line pointing in the z direction" –  Moataz Elmasry Aug 2 '12 at 11:18
    
I like the second solution also –  Moataz Elmasry Aug 2 '12 at 11:19
    
+1 for nice answer (2nd part) –  Arjang Aug 3 '12 at 2:59

I thought about a solution (that is expensive programatically). Calculate the squared euclidean distance between each two points. then take the points with the highest squared euclidean distance, calculate the root and here you go. thogh it costs O(n2), but I saved doing a square root on each iteration

share|improve this answer
    
This does not seem to be an answer to the question. You should edit the question itself and expand it with your thoughts. –  Mariano Suárez-Alvarez Aug 2 '12 at 16:11

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.