Calculating start/end points of a line segment given by a set of points and normal direction

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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