Convex hull of parallel lines

Question

I have arbitrary many lines in 3D space which are all parallel to each other. Now I want to find the convex hull of these lines. To illustrate this, I've drawn a picture:

I know the start- and endpoints of all lines (the blue dots). The lines are not equally long. If a viewer looks in the direction of the lines (marked as the viewer direction in the pic) he sees only the dots. Now I want to find the convex hull of these dots. Hopefully its clear what I mean.

My idea was to project the start or endpoints on a plane which is perpendicular to the line's direction. After that I can apply some kind of convex hull algorithm to these points. But I have no idea how.

Answer 1

Your idea is exactly correct. One way to accomplish this is to define a vector v along your viewing direction, and then rotate v to the z-axis. The same rotation will convert lines to vertical lines. Then drop the z-coordinate of the endpoints to get your projected points. Then compute the convex hull. There are hull algorithms all over the web, including my own here.

Answer 2

Here's a suggestion based on the calculus of variations.

Consider enclosing your collection of parallel line segments in a simple closed curve minimizing the area of the curve given the constraint that it has to enclose all your segments.

Your "curve" is going to be piecewise linear, so there you might be able to use a P.W basis function in the iterations, though it's possible that you could run into some singularities when the algorithm needs to drop a segment.