Computing the union 2 MKPolygons

I am working on map applications with polygon MKOverlays. I have a requirement to merge (union) overlapping polygons.

Is there a well known algorithm to do this? Are there any free existing libraries/implementations that help with such geometry operations?

I have found the GEOS开发者_高级运维 library, but apparently its licensing terms disallow use without distributing your source code. Is anyone else using this library. If yes, where can I find the way to include this in my Xcode project.

The only free libraries I'm aware of are -

Clipper: http://angusj.com/delphi/clipper.php

Boost Polygon: http://www.boost.org/doc/libs/1_47_0/libs/polygon/doc/index.htm

Boost Geometry: http://trac.osgeo.org/ggl/

Try gpc. They have several licences. Also there are similar libraries listed on their page.

There is a great library RSClipperWrapper which is basically a wrapper for Clipper. There is even a great library comparison inside their website:

TL;DR, free library, error free and fast.

A few notes:

• RSClipperWrapper takes CGPoint but fear not, you can pass lat/long into it and it will get the job done (tested and verified).

• For convinice I've written an extension so we can just pass a custom Polygon array and get the merged polygons - if you're using MKPolygon or other type then don't forget adjust your type:

  extension Clipper {
    static func union(polygons: [Polygon]) -> [Polygon] {
      let pointsPolygons = convert(polygons: polygons)
      let unionfied = Clipper.unionPolygons(pointsPolygons, withPolygons: pointsPolygons)
      return convert(pointsPolygons: unionfied)
     }
  
    static func convert(polygons: [Polygon]) -> [[CGPoint]] {
      var polygonsPoints: [[CGPoint]] = []
      for polygon in polygons {
          var points: [CGPoint] = []
          for location in polygon.locations {
              points.append(CGPoint(x: location.coordinate.latitude, y: location.coordinate.longitude))
          }
          polygonsPoints.append(points)
      }
      return polygonsPoints
     }
  
    static func convert(pointsPolygons: [[CGPoint]]) -> [Polygon] {
      var polygons: [Polygon] = []
      for pointsPolygon in pointsPolygons {
          var locations: [CLLocation] = []
          for point in pointsPolygon {
              locations.append(CLLocation(latitude: CLLocationDegrees(point.x), longitude: CLLocationDegrees(point.y)))
          }
          let polygon = Polygon(locations: locations)
          polygons.append(polygon)
      }
      return polygons
   }
  }