0
$\begingroup$

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?

  • 0
    I also don't know what you mean by "indicating the line segment direction". If I give you the vector $(1,0,0)$ and tell you that it is normal to my line segment, then you don't know whether my line is parallel to $(0,1,0)$, $(0,0,1)$, $(0,5,12)$, or anything else in the $yz$ plane. So specifying one normal of a line segment in 3D doesn't determine its direction. By the way, you should use @Rahul when you reply to my comments so that I get notified (but not any more because I'm going to bed).2012-08-02

3 Answers 3

0

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

  • 0
    This does not seem to be an answer to the question. You should edit the question itself and expand it with your thoughts.2012-08-02
3

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.

  • 0
    I like the second solution also2012-08-02
2

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.