Generating borders with convex hull

Question

I have some polylines (streets on a map) take these three, for instance:

I need to convert these polylines into polygons. The mapping library I'm using has a built in convex hull function which generates something like this:

As you can see, using a convex hull to generate the area borders creates unwanted overlapping.

What I need is to create a convex hull that sort of avoids adjacent lines, like this:

There doesn't appear to be any built in method for doing this, so I'm going to have to get my hands dirty and write one myself. Problem is, I have no idea where to start.

Any information to help get me started is appreciated. If someone could walk me thru the algorithm that would be even better. If there is a name for this algorithm please let me know so I can start searching.

Answer 1

I was hoping for a more efficient implementation, but my "brute force" method isn't as bad as I expected (so far).

I've got a mostly complete implementation that follows these general steps:

1. Create the basic convex hull using the Jarvis algorithm.
   1. Starting at the leftmost point, moving clockwise, append the first intersecting point.
   2. Continue until you get back to the leftmost point.
2. Loop over each point in the adjacent polylines and determine if any of them are inside of the convex hull polygon.
   1. Draw a line from each point to the left, infinitely (or at least past the rightmost point of the polygon).
   2. If the line intersects a line of the polygon an odd number of times, the point lies inside the polygon.
3. Insert the obstructing point between the lines it intersects in the hull.

Still working on Step three. I know there will gotchas but I'm working thru them. I'll update this answer once I get it all figured out.

Here's a quick n dirty Javascript/canvas implementation (first revision) to test the concept as I work thru it.

---

edit

Got this working on all my test cases, time to try with real data.. my solution for step three is..

3. Generate an array for each consecutive group of obstructing points in the convex hull. Find the point in the hull closest to the first obstructing point in the array (point a). Determine if the last point in the obstructing points array is closer to the point preceding point a or the point succeeding it, if it's closer to the former, insert the obstrcuting point into the hull before point a, else, insert after it.

Quick n dirty JS implementation (revision 2)

I'll mark the answer if no gives me a better one once I confirm it works on real data...