# Computing the (non-convex) boundary of a set of paths between two points

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:

• x is increasing on each path? – k20 Nov 6 '14 at 22:56
• @k20 Not necessarily. In fact, even loops are possible. Yet another case to consider. – metacubed Nov 7 '14 at 2:13
• @k20 I did not even consider the loop case until you pointed it out. – metacubed Nov 7 '14 at 2:16
• So how exactly do you define the grey region? – Kirill Nov 7 '14 at 5:29
• @Kirill The paths are actually the recorded outputs of many different route-finding algorithms. I'm trying to visualize the spread/variance of these routes. – metacubed Nov 7 '14 at 7:26

If you represent the set of paths as a set of individual line segments $S=\{L_k\}$ between consecutive points, then the intersection of the set you want with the line $x=x_0$ is between the lower-most and the upper-most intervals that contain the $x$-coordinate $x_0$.
In particular, your set is bounded by a set of line segments whose endpoints lie only on endpoints of $L_k$ or on their intersections.
So it is enough to get all the $x$-coordinates of the line segments and their mutual intersections, and at each such coordinate find the bottom and top points that lie on any line segment. The lines between these bottom and top points form the boundary of your set.
• @metacubed How? When considering the second blue point, the top/bottom points are not on that blue point's line segment; they belong to the $(1,6)$ and $(0,4)$ line segments (counting points from the left). If you consider all the line segments at that $x$-coordinate, it should work fine. – Kirill Nov 5 '14 at 3:01