Creating a polygon from random verts

[bitWISE]

I've got a puzzler at work that is holding me up. I'm creating a geographic routing application that basically lets you see where your customers are on top of Google Maps in Adobe Flex. Each customer gets sent to the map as a pushpin and one particular feature I would like to implement is to be able to highlight particular regions of pushpins. Lets say Bob and Jim service customers in Shittycity, USA and I want to see a polygon for each one indicating their current coverage area based on the customer pushpins on the map. Sadly, Google Maps creates polygon overlays exactly as you tell it to so I need to send it the perfect array of points.

Problem one: Find the pushpins which define the smallest polygon that contains all the pushpins for Bob
Problem two: Find the correct order for the pushpins from problem one so that they form the intended polygon rather than zig-zagging

I solved problem one by starting with three of the pushpins and then using a ray intersection test to determine whether I should ignore the next pushpin or use it to extend the polygon.

For problem two, I could shuffle the pushpins until the only edge intersection points are the pushpins themselves but I don't have a good implementation yet.

Any suggestions?

[^misantropia^]

I'll get back to you with a more complete answer tomorrow (on my phone right now) but convert from cartesian to polar first, makes it easier to solve.

[^misantropia^]

Okay. This is a special case of graph traversal, more specifically: shortest path with the additional constraint that not all nodes need to be visited, only the outliers. Have a look at the Wikipedia article on Dijkstra's algorithm (and A*).

The optimal solution is actually pretty hard - and probably NP-complete - but a good approximation is this:

1. Convert from Cartesian (x,y) to polar (degree,radius). Your point of origin should probably be Bob's or Jim's home base or the average of all points.
2. Group by degree at the granularity you want. Sounds complex but isn't. Think of a pie divided in 8 slices. 8 is your granularity. Create 8 lists and put each point in list[point.degree % 8].
3. From each list, take the greatest outlier (the point that has the greatest radius).
4. Sort the results from #3 by degree.
5. Convert the results from #4 back to Cartesian. Now you have your polygon.

Voila, a solution to both questions. There are some details to be taken care of (for example, what if a list contains no points?) but that's all fairly trivial.

[Eraser]

I may be going a bit out on a limb here, but doesn't Google Maps have standard API methods for this sort of thing?

[^misantropia^]

Where is the fun in that?

BTW, list[point.degree % 8] should have been list[floor(8 * (degree / 360))].

[Eraser]

Heh, well it's not a hobbyist project he's working on. I'm sure his employer will be a lot happier when he chose the quick and easy way rather than go and reinvent the wheel.

[bitWISE]

Thanks for the suggestion, I'll try that out.

I may be going a bit out on a limb here, but doesn't Google Maps have standard API methods for this sort of thing?

Their API for creating a polygon only takes an ordered array of LatLng points. My data source is an unordered list, with duplicate and unneeded nodes. Here is what Google does with my unaltered data:

[Eraser]

Ah I see. A mess