I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue).
I am trying to find the ordered set of points which comprise the boundary of these paths. This boundary is shown in gray. Note that this boundary would contain the intersection of these lines.
I've implemented convex hull algorithms to try and solve this, but, by definition, they discard the concave part of the boundary.
Is there a deterministic way to solve this without brute-force calculation? If not, are there any approximation algorithms which give better performance?
Based on the comment by @k20, I realized that there was a case which I had not considered. $x$ and $y$ can both increase and decrease along a path. There can even be loops in the path. Here is another example: