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!

Since you've found the algorithms to use, what's the problem you're having with the *implementation*? — Alejandro C., Dec 05 '16 at 21:58
[This answer](http://stackoverflow.com/a/37756436/696391) shows how to do line-line intersection in swift. When the user adds a new line, just test the new one for intersection with all the existing ones. — samgak, Dec 05 '16 at 22:26
It's very simple. Check all non connected edges (sides) with each other to see if they [intersect](http://stackoverflow.com/a/40953705/4543207). — Redu, Dec 05 '16 at 22:35
Did you get this working? I didn't come back to my answer as I was too busy and it would actually be quite large and I'm unfamiliar with google maps sdk, though could code it for core graphics.. — twiz_, Dec 12 '16 at 16:47
Yes, the solution seems functional. I posted my answer. It doesn't correct the polygon, but alerts the user that it is self-intersecting. — Baylor Mitchell, Dec 12 '16 at 16:57

score 2 · Accepted Answer · edited May 23 '17 at 12:01

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


                }
            }
        }
    }

This fails with the following lat/lng set: 33.86849360537594, -118.17826767729882 33.86468074440517, -118.15178891086123 33.85851566504107, -118.1980087349346 33.85349061795741, -118.17440529645701 — craya, Jan 26 '23 at 20:20

score 1 · Answer 2 · answered Dec 06 '16 at 07:46

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.

Detect self intersection of a polygon with n sides?

2 Answers2