Using Swift, how can I determine if a coordinates ordered pair (x,y) is within the bounds of n ordered pairs?

Question

Is there a math function of some kind in Swift (or maybe multiple functions that work together), where I can create sets of ordered pair coordinates, and then pass in a single ordered pair coordinate to get a bool true/false of whether it's within the bounds of the set?

I'm not the greatest at math, so I'm hoping someone who is (and understands how to solve this problem in Swift) can help me out here.

Example data:

I have a coordinate where someone is located in lat-long. Let's say (28.3797770, -81.5431893).

I also have a set of coordinates that corresponds to an area. It could be 3-sided or higher. In this example with the screenshot, it's 7 coordinates.

latitude, longitude

(28.3795930, -81.5433286)
(28.3797771, -81.5431891)
(28.3797098, -81.5430725)
(28.3796355, -81.5431288)
(28.3794715, -81.5428780)
(28.3793546, -81.5429665)
(28.3795859, -81.5433219)

See https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon for an approach using ray casting — Paulw11, Jul 18 '18 at 23:24
Note that the polygon needs to be closed, so you would "add" an edge between the last and first points — Paulw11, Jul 18 '18 at 23:31

score 2 · Answer 1 · answered Jul 19 '18 at 02:22

Based on this answer I came up with the following Swift code:

PolygonRegion.swift

import Foundation
import CoreLocation

struct PolygonRegion {

    let verticies:[CLLocationCoordinate2D]
    private var maxLat: CLLocationDegrees!
    private var maxLon: CLLocationDegrees!
    private var minLat: CLLocationDegrees!
    private var minLon: CLLocationDegrees!
    private var epsilon: CLLocationDegrees

    var center: CLLocationCoordinate2D {
        return CLLocationCoordinate2D(latitude: minLat+(maxLat-minLat)/2, longitude: minLon+(maxLon-minLon)/2)
    }

    var latSpan: CLLocationDegrees {
        return abs(maxLat-minLat)
    }

    var lonSpan: CLLocationDegrees {
        return abs(maxLon-minLon)
    }

    init(verticies: [CLLocationCoordinate2D], epsilon: CLLocationDegrees = 0.01) {
        self.verticies = verticies
        self.epsilon = epsilon

        for point in self.verticies {
            maxLat = maxLat != nil ? max(maxLat, point.latitude):point.latitude
            maxLon = maxLon != nil ? max(maxLon, point.longitude):point.longitude
            minLat = minLat != nil ? min(minLat, point.latitude):point.latitude
            minLon = minLon != nil ? min(minLon, point.longitude):point.longitude
        }
    }

    public func isPointInside(_ testPoint: CLLocationCoordinate2D) -> Bool {
        guard isInsideBoundingBox(testPoint) else {
            return false
        }

        var intersections = 0

        let outsidePoint = CLLocationCoordinate2D(latitude: self.minLat - epsilon, longitude: testPoint.longitude)

        let testRay = Ray(point1: outsidePoint, point2: testPoint)

        for index in 0..<verticies.count {
            let edge = Ray(point1: verticies[index], point2: verticies[(index+1)%verticies.count])
            if intersectionType(testRay,edge) == .intersecting {
                intersections += 1
            }

        }

        if intersections % 2 == 0 {
            return false
        }

        return true
    }


    private func isInsideBoundingBox(_ testPoint: CLLocationCoordinate2D) -> Bool {

        return !( testPoint.latitude < minLat || testPoint.latitude > maxLat || testPoint.longitude < minLon || testPoint.longitude > maxLon )
    }

    // See https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon/218081?s=1|193.4130#218081

    private func intersectionType(_ ray1: Ray, _ ray2: Ray) -> IntersectionType {

        var d1,d2: Double
        var a1,a2,b1,b2,c1,c2: Double

        let v1x1 = ray1.point1.latitude
        let v1y1 = ray1.point1.longitude
        let v1x2 = ray1.point2.latitude
        let v1y2 = ray1.point2.longitude

        let v2x1 = ray2.point1.latitude
        let v2y1 = ray2.point1.longitude
        let v2x2 = ray2.point2.latitude
        let v2y2 = ray2.point2.longitude

        // Convert vector 1 to a line (line 1) of infinite length.
        // We want the line in linear equation standard form: A*x + B*y + C = 0
        // See: http://en.wikipedia.org/wiki/Linear_equation
        a1 = v1y2 - v1y1
        b1 = v1x1 - v1x2
        c1 = (v1x2 * v1y1) - (v1x1 * v1y2)

        // Every point (x,y), that solves the equation above, is on the line,
        // every point that does not solve it, is not. The equation will have a
        // positive result if it is on one side of the line and a negative one
        // if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
        // 2 into the equation above.
        d1 = (a1 * v2x1) + (b1 * v2y1) + c1
        d2 = (a1 * v2x2) + (b1 * v2y2) + c1

        // If d1 and d2 both have the same sign, they are both on the same side
        // of our line 1 and in that case no intersection is possible. Careful,
        // 0 is a special case, that's why we don't test ">=" and "<=",
        // but "<" and ">".
        if (d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0) {
            return .nonIntersecting
        }

        // The fact that vector 2 intersected the infinite line 1 above doesn't
        // mean it also intersects the vector 1. Vector 1 is only a subset of that
        // infinite line 1, so it may have intersected that line before the vector
        // started or after it ended. To know for sure, we have to repeat the
        // the same test the other way round. We start by calculating the
        // infinite line 2 in linear equation standard form.
        a2 = v2y2 - v2y1
        b2 = v2x1 - v2x2
        c2 = (v2x2 * v2y1) - (v2x1 * v2y2)

        // Calculate d1 and d2 again, this time using points of vector 1.
        d1 = (a2 * v1x1) + (b2 * v1y1) + c2
        d2 = (a2 * v1x2) + (b2 * v1y2) + c2

        // Again, if both have the same sign (and neither one is 0),
        // no intersection is possible.
        if (d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0) {
            return .nonIntersecting
        }

        // If we get here, only two possibilities are left. Either the two
        // vectors intersect in exactly one point or they are collinear, which
        // means they intersect in any number of points from zero to infinite.
        if (a1 * b2) - (a2 * b1) == 0.0 {
            return .coLinear
        }

        // If they are not collinear, they must intersect in exactly one point.
        return .intersecting
    }

    private struct Ray {
        let point1: CLLocationCoordinate2D
        let point2: CLLocationCoordinate2D
    }

    private enum IntersectionType {
        case intersecting
        case nonIntersecting
        case coLinear
    }

}

Then

let verticies = [CLLocationCoordinate2D(latitude: 28.3795930, longitude: -81.5433286),
                     CLLocationCoordinate2D(latitude:28.3797771,longitude: -81.5431891),
                     CLLocationCoordinate2D(latitude:28.3797098,longitude: -81.5430725),
                     CLLocationCoordinate2D(latitude:28.3796355,longitude: -81.5431288),
                     CLLocationCoordinate2D(latitude:28.3794715,longitude: -81.5428780),
                     CLLocationCoordinate2D(latitude:28.3793546,longitude: -81.5429665),
                     CLLocationCoordinate2D(latitude:28.3795859,longitude: -81.5433219)]

let region = PolygonRegion(verticies: verticies)

let outsideTestPoint = CLLocationCoordinate2D(latitude: 28.3796098, longitude: -81.5430753)
let insideTestPoint = CLLocationCoordinate2D(latitude: 28.3796098, longitude: -81.5431453)

print(region.isPointInside(insideTestPoint))

gives

true

print(region.isPointInside(outsideTestPoint))

gives

false

score 2 · Answer 2 · answered Jul 19 '18 at 03:43

You can use CoreGraphics CGPath, and the CGPath.contains function to test if a point is inside a polygon.

//: Playground - test if a point is inside polygon

import UIKit
import CoreGraphics

let points = [CGPoint(x: 28.3795930, y: -81.5433286),
              CGPoint(x: 28.3797771, y: -81.5431891),
              CGPoint(x: 28.3797098, y: -81.5430725),
              CGPoint(x: 28.3796355, y: -81.5431288),
              CGPoint(x: 28.3794715, y: -81.5428780),
              CGPoint(x: 28.3793546, y: -81.5429665),
              CGPoint(x: 28.3795859, y: -81.5433219)]

// Build a closed path from points representing the ordered edges of a polygon
func closedPath(points: [CGPoint]) -> CGPath {
    let path = CGMutablePath()
    path.addLines(between: points)
    path.closeSubpath()
    return path
}

let path = closedPath(points: points)
let pointOutside = CGPoint(x: 28.37965, y: -81.5431)
let pointInside = CGPoint(x: 28.3796, y: -81.5431893)

path.contains(pointOutside) // Prints false
path.contains(pointInside)  // Prints true

If you have many areas that you want to test against a single point, you might want to look into using a data structure for spatial indexing, such as a quadtree, or k-d tree.

Using Swift, how can I determine if a coordinates ordered pair (x,y) is within the bounds of n ordered pairs?

2 Answers2