Detect self intersection of a polygon with n sides?

Question

I am using Google Maps SDK to allow a user to draw a polygon on the map by tapping. Everything works perfectly is the user is to draw a polygon following a path and continues on that path without crossing over lines. If that happens, this result is produced:

However, if the user is to make an error and cross over or change the direction of their "tapping" path this happens:

I need to either:
A) alert the user that they have created an invalid polygon, and must undo that action, or
B) correct the polygon shape to form a complete polygon.

With the research I have done, option A seems much more feasible and simple since option B would require rearranging the path of the polygon points.

I have done research and found algorithms and formulas to detect line intersection, but I am yet to find any piece of a solution in Swift to recognize if a polygon self-intersects based off of points (in this case, latitude and longitude). I don't need to know the point, just TRUE or FALSE to the question, "Does this Polygon self-intersect?" The polygon will typically have less than 20 sides.

Perhaps there is a solution built in with the GoogleMaps SDK, but I am yet to find it. Also, I understand that there are already algorithms for problems such as these, I am just having trouble implementing them into Swift 2 or 3. Any help is appreciated, thanks!

Answer 1

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)")


                }
            }
        }
    }

Answer 2

I'm guessing that you're trying to plot out the quickest way to get from point to point as the crow flies. You'll probably want to consider road direction too, which I won't here.

Both your options are possible. It's easy enough to iterate over every existing line when a new line is added and determine if they've crossed over. But your user would definitely rather not be told that they've screwed up, your app should just fix it for them. This is where it gets fun.

I am certain algorithms exist for finding the minimal polygon containing all points, but I didn't look them up, because where's the fun in that.

Here's how I would do it. In pseudocode:

if (line has intersected existing line)

find mean point (sum x sum y / n)

find nearest point to centre by:
taking min of: points.map(sqrt((x - centrex)^2 + (y-centrey)^2))

from the line between centre and nearest point, determine angle to every other line.

points.remove(nearest)

angles = points.map(cosine law(nearest to centre, centre, this point)) 
<- make sure to check if it crossed pi, at which point you must add pi.

sort angles so minimum is first.

starting at nearest point, add line to next point in the array of minimal angle points

I'm sorry I haven't put this into swift. I will update tomorrow with proper Swift 3.