3
$\begingroup$

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).

Simple Scenario

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:

Loop Scenario

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ x is increasing on each path? $\endgroup$ – k20 Nov 6 '14 at 22:56
  • $\begingroup$ @k20 Not necessarily. In fact, even loops are possible. Yet another case to consider. $\endgroup$ – metacubed Nov 7 '14 at 2:13
  • $\begingroup$ @k20 I did not even consider the loop case until you pointed it out. $\endgroup$ – metacubed Nov 7 '14 at 2:16
  • $\begingroup$ So how exactly do you define the grey region? $\endgroup$ – Kirill Nov 7 '14 at 5:29
  • $\begingroup$ @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. $\endgroup$ – metacubed Nov 7 '14 at 7:26
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I did consider this algorithm before posting the question, but it does not give the expected results. For example, it will join the first two blue points from the left, even though the second one is inside the concave hull. $\endgroup$ – metacubed Nov 5 '14 at 2:57
  • $\begingroup$ @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. $\endgroup$ – Kirill Nov 5 '14 at 3:01
  • $\begingroup$ Ah, I get you now.. let me try that out on some samples to check for edge cases. Thanks! $\endgroup$ – metacubed Nov 5 '14 at 3:04
  • $\begingroup$ @metacubed Well, did it work? $\endgroup$ – Kirill Nov 6 '14 at 18:31
  • $\begingroup$ I realized that I had missed a major scenario. Your solution works for my originally stated constraints, but not with the updated ones. Please see my edit. $\endgroup$ – metacubed Nov 7 '14 at 3:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.