How Make Polygon Without Intersection in Swift

How make polygon without intersection in Swift

In order to solve your issue you should reorder coordinates of GMSMutablePath in clockwise direction. I have modified your example and added functions reorderMarkersClockwise(), isLess() and getCenterPointOfPoints() that do this task. The code snippet is the following

import UIKit
import GoogleMaps

class ViewController: UIViewController {
    var counterMarker: Int = 0
    var allMarkers:[GMSMarker] = []

    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view, typically from a nib.
    }

    override func didReceiveMemoryWarning() {
        super.didReceiveMemoryWarning()
        // Dispose of any resources that can be recreated.
    }

    override func loadView() {
        let camera = GMSCameraPosition.camera(withLatitude: -33.86, longitude: 151.20, zoom: 6.0)
        let mapView = GMSMapView.map(withFrame: CGRect.zero, camera: camera)

        mapView.delegate = self
        mapView.isMyLocationEnabled = true
        view = mapView
    }
}

extension ViewController: GMSMapViewDelegate {

    func mapView(_ mapView: GMSMapView, didLongPressAt coordinate: CLLocationCoordinate2D) {
        // Custom logic here
        if counterMarker < 4 {
            let marker = GMSMarker()
            marker.position = coordinate
            marker.title = "I added this with a long tap"
            marker.snippet = ""
            allMarkers.append(marker)
            counterMarker += 1
            // Create the polygon, and assign it to the map.
            mapView.clear()
            let rect = reorderMarkersClockwise(mapView)
            for mark in allMarkers {
                mark.map = mapView
            }
            let polygon = GMSPolygon(path: rect)
            polygon.fillColor = UIColor(red: 0.25, green: 0, blue: 0, alpha: 0.05);
            polygon.strokeColor = .black
            polygon.strokeWidth = 2
            polygon.map = mapView

        }
    }

    func mapView(_ mapView: GMSMapView, didLongPressInfoWindowOf marker: GMSMarker) {
        marker.map = nil
        for (index, cmark) in allMarkers.enumerated() {
            if cmark.position.latitude == marker.position.latitude, cmark.position.longitude == marker.position.longitude {
                allMarkers.remove(at: index)
                break;
            }
        }
        counterMarker -= 1

        mapView.clear()
        let rect = reorderMarkersClockwise(mapView)
        for mark in allMarkers {
            mark.map = mapView
        }

        // Create the polygon, and assign it to the map.
        let polygon = GMSPolygon(path: rect)
        polygon.fillColor = UIColor(red: 0.25, green: 0, blue: 0, alpha: 0.05);
        polygon.strokeColor = .black
        polygon.strokeWidth = 2
        polygon.map = mapView
    }

    func reorderMarkersClockwise(_ mapView: GMSMapView) -> GMSMutablePath {
        let rect = GMSMutablePath()
        if (counterMarker > 1) {
            let arr = allMarkers.map{$0.position}.sorted(by: isLess)
            for pos in arr {
                rect.add(pos)
            }
        } else {
            for mark in allMarkers {
                rect.add(mark.position)
            }
        }
        return rect
    }

    func isLess(_ a: CLLocationCoordinate2D, _ b: CLLocationCoordinate2D) -> Bool {
        let center = getCenterPointOfPoints()

        if (a.latitude >= 0 && b.latitude < 0) {
            return true
        } else if (a.latitude == 0 && b.latitude == 0) {
            return a.longitude > b.longitude
        }

        let det = (a.latitude - center.latitude) * (b.longitude - center.longitude) - (b.latitude - center.latitude) * (a.longitude - center.longitude)
        if (det < 0) {
            return true
        } else if (det > 0) {
            return false
        }

        let d1 = (a.latitude - center.latitude) * (a.latitude - center.latitude) + (a.longitude - center.longitude) * (a.longitude - center.longitude)
        let d2 = (b.latitude - center.latitude) * (b.latitude - center.latitude) + (b.longitude - center.longitude) * (b.longitude - center.longitude)
        return d1 > d2
    }

    func getCenterPointOfPoints() -> CLLocationCoordinate2D {
        let arr = allMarkers.map {$0.position}
        let s1: Double = arr.map{$0.latitude}.reduce(0, +)
        let s2: Double = arr.map{$0.longitude}.reduce(0, +)
        let c_lat = arr.count > 0 ? s1 / Double(arr.count) : 0.0
        let c_lng = arr.count > 0 ? s2 / Double(arr.count) : 0.0
        return CLLocationCoordinate2D.init(latitude: c_lat, longitude: c_lng)
    }
}

You can also find a sample project on GitHub: https://github.com/xomena-so/so50679742. Use your API key to run the sample project.

Sample Image

I hope this helps!

Creating a new MKPolygon from two intersecting polygons

Ok guys! well i went off and created my own MKPolygon category to solve what i needed to solve. I hope it is also useful to others!

the github link is: https://github.com/geeksweep/MKPolygon-GSPolygonIntersections

Compute all possible polygons with no line crossing

I am unaware of an existing algorithm to do this, so I will attempt to find some lower bounds for one, starting with the suggestions in the comments:

There are n! possible permutations of n points
Since the start point is arbitrary, and reversing a valid solution also yields a valid solution, you can further reduce this to (n-1)!/2, as MBo suggests.
If you build a convex hull of the set of points (as Damien suggests), the points in the convex hull must appear in sequence (ignoring rotations and reflections). That is, if points a, b, c, d are consecutive in the hull, a, c, b, d will result in a crossing. This greatly reduces the amount of permutations to check. You can build the convex hull in O(n log n) or better, so it is definitely worth it if the hull has many points: a hull with h points allows you to focus on (h-1)!/2 less candidates. On the flip side, if h is a triangle, you gain nothing.
Building triangulations (also suggested by Damien) allows easy generation of many valid answers, but also excludes many possible edges from consideration.

Let us build a backtracking algorithm based on the observation that, given a valid closed polygon, and a point p not part of this polygon, all segments e1, e2 such that e1, p and p, e2 cross no polygon segments result in a new valid closed polygon that includes p. We can avoid double-counting (n! vs (n-1)!/2) by choosing a starting triangle.

  function find_polygons(points) {
      let current = polygon_of(points[0], points[1], points[2]);
      let remaining = copy_of(points).removeAll(current);
      let answers = new Set();
      let goal = points.length();
      find_polygons_recursive(goal, current, remaining, answers);
      return answers;
  }

  function find_polygons_recursive(goal, current, remaining, answers) {
      if (current.length() == goal) {
         answers.add_if_absent(current);
         return;
      }
      for (point p in remaining) {
         let without_p = copy_of(remaining).remove(p);
         for (segment s in current.segments()) {
             if ( ! current.intersects(segment(s1, p)) and
                  ! current.intersects(segment(s2, p))) {
                next = copy_of(current).remove(s)
                    .add(segment(s1,p));
                    .add(segment(s2,p));
                find_polygons_recursive(goal, next, without_p, answers);
             }
         }
      }
  }

At the cost of n^4 space and time, you can pre-compute a matrix of n^2xn^2 booleans indicating which segments intersect with which other segments. This should greatly improve the speed of intersection tests.

Detect self intersection of a polygon with n sides?

This seems to be working pretty well for what I need. Adopted from Rob's answer here

 func intersectionBetweenSegmentsCL(p0: CLLocationCoordinate2D, _ p1: CLLocationCoordinate2D, _ p2: CLLocationCoordinate2D, _ p3: CLLocationCoordinate2D) -> CLLocationCoordinate2D? {
    var denominator = (p3.longitude - p2.longitude) * (p1.latitude - p0.latitude) - (p3.latitude - p2.latitude) * (p1.longitude - p0.longitude)
    var ua = (p3.latitude - p2.latitude) * (p0.longitude - p2.longitude) - (p3.longitude - p2.longitude) * (p0.latitude - p2.latitude)
    var ub = (p1.latitude - p0.latitude) * (p0.longitude - p2.longitude) - (p1.longitude - p0.longitude) * (p0.latitude - p2.latitude)

    if (denominator < 0) {
        ua = -ua; ub = -ub; denominator = -denominator
    }

    if ua >= 0.0 && ua <= denominator && ub >= 0.0 && ub <= denominator && denominator != 0 {
        print("INTERSECT")
        return CLLocationCoordinate2D(latitude: p0.latitude + ua / denominator * (p1.latitude - p0.latitude), longitude: p0.longitude + ua / denominator * (p1.longitude - p0.longitude))
    }
    return nil
}

I then implemented like this:

 if coordArray.count > 2 {
        let n = coordArray.count - 1

        for i in 1 ..< n {
            for j in 0 ..< i-1 {
                if let intersection = intersectionBetweenSegmentsCL(coordArray[i], coordArray[i+1], coordArray[j], coordArray[j+1]) {
                    // do whatever you want with `intersection`

                    print("Error: Intersection @ \(intersection)")

                }
            }
        }
    }

Check whether GMSPolygon is inside other GMSPolygon or not

After searching lot things, i found one solution, i think that is not that much proper, but still better than other 3-4 solutions that i found. If anyone find better solution that this, tell me, if i find them better and proper, i will accept that one and will change in my code too. Rightnow, i have used following code to do this.

GMSPath *path1=polygon1.path, *path2=polygon2.path;
BOOL flag1= NO;
BOOL flag2= NO;
for (int i=0; i<path1.count; i++)
{
    if (GMSGeometryContainsLocation([path1 coordinateAtIndex:i], path2, YES)==false)
    {
        flag1 = true;
    }

    if (GMSGeometryIsLocationOnPath([path1 coordinateAtIndex:i], path2, YES)==true)
    {
        flag2 = true;
    }
}

if (flag1==false)
{
    NSLog(@"polygon1 is fully inside polygon2");
}
else if (flag2 == true)
{
    NSLog(@"polygon1 intersects with polygon2");
}
else
{
    //Do the above procedure again just by switching path1 and path2
    //and at end you can find that is polygon2 is inside polygon1 or not, 
    //and if it is not, then this means both polygon1 and polygon2 are distinct
    //then neither intersects, nor inside each other
}

Intersection over union for rectangles with different orientation

You can use O'Rourke algorithm for calculation of intersection of two convex polygons.
C and Java code is availaible on the page for book "Computational Geometry in C"

Sample Image

Algorithm traverses edges of polygons until it finds intersection (using
orientation test). After intersection it chooses "the most inner" edge from two possible next ones to build intersection core polygon (always convex).

When you have ordered list of vertices, you can calculate polygon area with shoelace formula.

To get area of union, we can calculate (thanks to Yves Daoust for hint)

Area(Union) = Area(P) + Area(Q) - Area(Intersection)

How Make Polygon Without Intersection in Swift