I solved the problem. I had, in fact, googled it, thanks for the suggestion, and there are a number of interesting solutions out there. None of them did what I wanted to do. The zip code solution isn't directly applicable, since the zipcode polygons don't overlap. They do share a boundary, and noise in the definitions of the polygons might produce incidental overlap. But not what I was talking about.
There's a very powerful C library that I considered -- GPC (Generic Polygon Clipper) but I couldn't use it because it's a server solution, and I needed a client (JS-based) solution. I looked at porting the C Code to run as an extension to Ruby, but it looked like work. However, for people who can use a server solution, and don't mind doing the work to integrate it, it looks fantastic. My problem had certain characteristics that made it easier to solve: All polygons were guaranteed to overlap: None of them had voids; And, if two polygons do in fact overlap and produce a void, it can be ignored, and the outer envelope only used. The solution, in schematic form is as follows: First, however many polygons you want to combine, you combine them two at a time. Sort them so the largest are first (you can use Google's polyArea for this). For each pair, find each intersection point. Generate new versions of each polygon, with the intersection points interpolated. This means that both polygons will have an even number of shared points. Find a point on either generated polygon that is outside of the box limits of the other. Use that as a starting point. Traverse the polygon's points in order, pushing them into a new array. It' unimportant which direction you start, as the starting point is guaranteed to be outside the other polygon. Each time you encounter a point which is shared with the other, switch polygons. Find the location of the shared point in the new polygon. Take the two adjacent line segments to the shared point, and find their midpoints Determine which midpoint is inside, which is outside the other polygon. One or the other is required to be true. Whichever is outside, follow in that direction, until you encounter a shared point. At that point, switch polygons again, rinse and repeat. When you encounter the original point you started from, you have your union polygon. There is a special case, where one polygon is entirely contained by the other. If no intersection points are created, you know this is the case, and you need only to test one point at random to see if it is inside or outside polygon the other to determine which polygon should be returned. There is a second special case, where either of the polygons has lines that cross itself, eg a 'W' formation with a strike through the W, then join the endpoints of the two lines. In that case, this won't work it the outer-limit starting point leads to an intersection point, but via a line segment that crosses the polygon it's part of first. Fortunately, I can filter this on the input side (polygons are created by users, and I prevent them from creating ones with crossing lines.). So far this has proved to be very accurate, and acceptably fast. Again, I can limit the number of polygons to under 40, and by sorting them by area, and combining the largest first, I reduce the likelihood of missing areas, since smaller areas combined later will be more likely to be inside the union poly. The major computational vampires are the number of points in each polygon, which once again I can limit to under 30. However, I can't easily limit the number of points generated by the combination process. I use polygon encoding (done on the fly, using code from http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/PolylineEncoder.html to manage and display the resulting polygon. There also may be a problem with rounding errors on intersection points very close to vertexes. I treated this by detecting distances between points of intersecting line segments, and then using the nearest vertex if the distance dropped below a certain level which is around 0.0004. However, this may not be necessary and certainly adds complexity. If a visually correct union poly is all you need, this inaccuracy won't matter. In practical terms, you can perform other close-point merges, since it's advantageous to minimize points, especially when many polygons are being merged, but I leave that as an exercise for the reader. On Jul 4, 1:41 pm, bratliff <[email protected]> wrote: > Another demo: > > www.polyarc.us/polybuilder > > running in the browser without server support. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google Maps API" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/Google-Maps-API?hl=en -~----------~----~----~----~------~----~------~--~---
