# 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, 2014 at 22:56
• @k20 Not necessarily. In fact, even loops are possible. Yet another case to consider. Nov 7, 2014 at 2:13
• @k20 I did not even consider the loop case until you pointed it out. Nov 7, 2014 at 2:16
• So how exactly do you define the grey region? Nov 7, 2014 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. Nov 7, 2014 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. Nov 5, 2014 at 3:01