Determine non-convex hull of collection of line segments

1. Pick a safe starting point. Can be e.g. the endpoint with maximum x.
2. March along the line segment.
3. Upon encountering any intersection, always turn left and march along this new segment.
4. Upon encountering an endpoint, record it. Goto 2.
5. Stop when you have returned to your starting point. Your list of recorded endpoints now makes up the ordered list of vertices of your concave hull.

NB: This will fail if there is a "free-floating" outlying line segment that does not intersect any other line segment. However, you specify that "the bars uniquely define a solution", which rules out this fail condition. (Outlying segments make possible two distinct solutions.)

EDIT ... or rather, outlying segments can make two distinct solutions possible -- depending on the exact layout. Proof: Below is an example where the yellow segment that I added makes two solutions possible (blue and grey horribly hand-drawn lines). Were the yellow segment orientated perpendicular to the way it's drawn now, only one solution would be possible. Sounds like your problem is poorly defined.

EDIT Actually this can also fail if your segment collection is "very concave", i.e. if there are endpoints tucked away in recluse corners of your pile of segments. In the figure below I added a black segment. My algorithm would illegally join its endpoint to another endpoint (dashed grey line). I'll leave my answer be in case others are inclined to build upon it.

EDIT after giving this some more thought: Even in the "very concave" case, this solution will definitely give you all of the points of your concave hull in the proper order, but they may be interspersed with extra, inappropriate points such as the black one. So there may be too many points.

The answer is then, of course, to do some pruning. It would be fairly complicated pruning especially if you can have multiple, consecutive "recluse points" like the black one, so I don't have a smart algorithm in mind. But even blind, brute force could be feasible. Each point can be either accepted or rejected (boolean), so if you have N properly ordered candidate points in your concave hull, then there are only 2^N possibilities to check. This is way, way fewer possibilities than brute force for your original problem of permutations, which would have SUM of (n!/(n-k)!) for k=1:(n-1) possibilities (pardon my notation). So this algorithm narrows down your problem significantly.

I think this is the way to go.

Not a fully fleshed-out idea, but anyway: Suppose you started w/ the circular-sweep algorithm for a convex-hull (where you sort, and then process, the points by their angle from a center point). If all of the points end up in this hull, you're done. If not, then you have to "tighten" the hull to include these points. Each of these points were at once candidates for the convex hull, and got removed because they broke the convexness. Sometimes (as with the top purple point in the first example), we can simply leave them in. Where we can't, because the new segment of the hull crosses a segment (as going from the bottom green to the bottom purple in the first example, assuming the bottom aqua point got processed before the green one), the fix is a little more involved (and the part I haven't fleshed out, and is the very part alluded to in the question's latest edit).