3

I was wondering how to programatically merge several polygons on a map as one, meaning it'd still have the same general shape but the boundaries between them was removed and they'd work as a single set of coordinates, like on that picture:

https://i.stack.imgur.com/r1ThG.png

I'm using java on eclipse and open street map for the display.

(so I have several sets of coordinates and I want to make them a single set without simplifying the general shape).

overlord pancake
  • 51
  • 7
  • 3
    that has already been resolved, see http://stackoverflow.com/questions/2667748/how-do-i-combine-complex-polygons and http://mathoverflow.net/questions/111296/subtract-rectangle-from-polygon/111323#111323 – Martin Frank Aug 21 '15 at 09:31
  • 1
    @SashaSalauyou I don't think convex hull will work in this case, OP does not to simplify(change) the general shape. – Tawcharowsky Aug 21 '15 at 11:21
  • I do not think this should be marked as duplicate, for reasons I try to articulate in my answer below. – Joseph O'Rourke Aug 21 '15 at 15:02
  • Since you mentioned OSM, [JOSM](http://josm.openstreetmap.de/) (a Java-based OSM editor) has an implementation for [merging polygons](https://josm.openstreetmap.de/wiki/Help/Action/JoinAreas). Maybe you can borrow its code. – scai Aug 21 '15 at 15:23

1 Answers1

1

The union computation, as cited by @MartinFrank, would work, but is quite complex and more than is needed in this case. Clearly if you can merge two polygons P1 and P2 that share some positive length of boundary, you can merge any number. From the image provided, it appears that the polygons may exactly (as opposed to approximately) share boundary portions. If this is the case, then the following would work.

Walk (loop) around the boundary of P1, checking if the current vertex is also a vertex of P2. Once you have identified a common shared vertex v, then it is easy to walk forward & backward around the two polygons until you identify starting a and stopping b vertices that delimit the extent of the shared boundary. Then delete that ab portion, and stitch the two remaining boundary sections together to form P1 union P2.

Community
  • 1
  • 1
Joseph O'Rourke
  • 4,346
  • 16
  • 25