Check whether a point is inside of a simple polygon

Question

I'm trying to determine whether a point is located inside of a polygon or not. I use the following (for Swift modified) algorithm from this website:

func contains(polygon: [Point], test: Point) -> Bool {
    let count = polygon.count
    var i: Int, j: Int
    var contains = false
    for (i = 0, j = count - 1; i < count; j = i++) {
        if ( ((polygon[i].y >= test.y) != (polygon[j].y >= test.y)) &&
            (test.x <= (polygon[j].x - polygon[i].x) * (test.y - polygon[i].y) /
                (polygon[j].y - polygon[i].y) + polygon[i].x) ) {
                    contains = !contains;
        }
    }
    return contains;
}

However, when having a simple polygon with the following coordinates: (x: 0, y: 40), (x: 0, y: 0), (x: 20, y: 0), (x: 20, y: 20), (x: 40, y: 20), (x: 40, y: 40), and check for the point (x: 30, y: 20) the result is true as the if-statement evaluates to true when i and j are 5 and 4 ((x: 40, y: 40) and (x: 40, y: 20)), though the point is only located at the border of the polygon. The function should actually only evaluate true if the point is really located in the polygon. Thanks for any help or improvements/adjustments of the algorithm!

While the issue you describe certainly exists, your description of the test case does not look realistic. The condition in `if` statement does not evaluate to `true` on point `(30, 20)` and edge `(40, 20)-(40, 40)`. The `((polygon[i].y >= test.y) != (polygon[j].y >= test.y))` part is already `false`. `(20 >= 20) != (40 >= 20)` is `false`. — AnT stands with Russia, Aug 16 '15 at 07:55
There's no answer. It's what's called degeneracy.Floating point arithmetic is only so accurate, and so in fact there is a fuzzy border where points may be inside or outside the polygon, depending on how you write the test, even though all ways are mathematically correct. — Malcolm McLean, Jan 29 '17 at 17:43

score 20 · Answer 1 · answered Mar 30 '15 at 12:12

If this is for an iOS application, convert your polygon to a UIBezierPath, then use function containtsPoint() to verify if your point in in side that bezierpath

Example (iOS):

func contains(polygon: [CGPoint], test: CGPoint) -> Bool {
        if polygon.count <= 1 {
            return false //or if first point = test -> return true
        }

        var p = UIBezierPath()
        let firstPoint = polygon[0] as CGPoint

        p.moveToPoint(firstPoint)

        for index in 1...polygon.count-1 {
            p.addLineToPoint(polygon[index] as CGPoint)
        }

        p.closePath()

       return p.containsPoint(test)
    }

No it's not for an iOS application - however this effort isn't that bad - it would be interesting to know what algorithm the `containsPoint()` function is using — borchero, Mar 30 '15 at 12:32

score 7 · Answer 2 · answered Jul 26 '15 at 11:03

Works for me too, so i don't the where is the problem

I've also made a slighted modified version to use swift iterators:

func contains(polygon: [Point], test: Point) -> Bool {

  var pJ=polygon.last!
  var contains = false
  for pI in polygon {
    if ( ((pI.y >= test.y) != (pJ.y >= test.y)) &&
    (test.x <= (pJ.x - pI.x) * (test.y - pI.y) / (pJ.y - pI.y) + pI.x) ){
          contains = !contains
    }
    pJ=pI
  }
  return contains
}

Here are the results with your array sample in playground:

contains(poly,Point(x:40,y:40))   -> true
contains(poly,Point(x:30,y:20))   -> false
contains(poly,Point(x:40,y:20))   -> true
contains(poly,Point(x:1,y:1))     -> true

Maybe my question doesn't clarify this - a point lying on the edge of the polygon shouldn't be considered lying inside so (40, 40) should actually evaluate to false. But don't waste time to find another algorithm the more general issue has been resolved using another approach — borchero, Jul 26 '15 at 11:06

score 7 · Answer 3 · edited Feb 28 '20 at 08:17

7

A simple extension of MKPolygon in the swift:

extension MKPolygon {
    func contain(coor: CLLocationCoordinate2D) -> Bool {
        let polygonRenderer = MKPolygonRenderer(polygon: self)
        let currentMapPoint: MKMapPoint = MKMapPoint(coor)
        let polygonViewPoint: CGPoint = polygonRenderer.point(for: currentMapPoint)
        if polygonRenderer.path == nil {
          return false
        }else{
          return polygonRenderer.path.contains(polygonViewPoint)
        }
    }
}

edited Feb 28 '20 at 08:17

Ilesh P

3,940
1
24
49

answered Jan 29 '17 at 16:35

Anh Kiệt Bùi

101
1
6

This [answer](https://stackoverflow.com/a/54797280/8730130) avoids using a `MKPolygonRenderer` and uses the `MKPolygon` directly – Moshe Gutman Feb 21 '19 at 16:42
`MKMapPointForCoordinate(coor)` is now `MKMapPoint(coor)` – Ruben Marin Feb 28 '19 at 12:35

score 5 · Answer 4 · answered Mar 30 '15 at 13:05

Here is a improved implementation of PNPoly algorithm. I used it and it works fine.

func isPointInsidePolygon(polygon: [CGPoint], test:CGPoint) -> Bool {
 var  i:Int, j:Int = polygon.count - 1
 var  contains = false

 for (i = 0; i < polygon.count; i++) {
    if (((polygon[i].y < test.y && polygon[j].y >= test.y) || (polygon[j].y < test.y && polygon[i].y >= test.y))
        && (polygon[i].x <= test.x || polygon[j].x <= test.x)) {
            contains ^= (polygon[i].x + (test.y - polygon[i].y) / (polygon[j].y - polygon[i].y) * (polygon[j].x - polygon[i].x) < test.x)
    }

    j = i
 }

 return contains
}

for further query check: http://alienryderflex.com/polygon/

Volodymyr B. · Answer 5 · 2015-03-30T11:43:27.540

0

Here is javascript code (easy to understand, you can rewrite on swift). It works perfectly for me, almost 100%, i.e. great precision.

Your solution have bad precision.

function pointIsInPoly(v, polygon) {
    var edge_error = 1.192092896e-07; // epsilon i.e ~0.000000192
    var x = 0;
    var y = 1;
    var i, j;
    var r = false;
    for (i = 0, j = polygon.length - 1; i < polygon.length; j = i++)
    {
        var pi = polygon[i];
        var pj = polygon[j];
        if (Math.abs(pi[y] - pj[y]) <= edge_error && Math.abs(pj[y] - v[y]) <= edge_error && (pi[x] >= v[x]) != (pj[x] >= v[x]))
        {   
            return true;
        }

        if ((pi[y] > v[y]) != (pj[y] > v[y]))
        {
            var c = (pj[x] - pi[x]) * (v[y] - pi[y]) / (pj[y] - pi[y]) + pi[x];
            if (Math.abs(v[x] - c) <= edge_error)
            {
                return true;
            }
            if (v[x] < c)
            {
                r = !r;
            }
        }
    }
    return r;
}

edited Mar 30 '15 at 11:43

answered Mar 30 '15 at 11:23

Volodymyr B.

3,369
2
30
48

It would be interesting to know why this particular value is chosen for edge_error, and how modifying this value influences the result. – What does *"perfectly for me, almost 100%."* mean? :) – Martin R Mar 30 '15 at 11:36
edge_error - it's epsilon, you can change it to smaller or bigger value, now it's 0.00000011920.. . "almost 100%" - means all solutions for this task have some precision, but this one very accurate. – Volodymyr B. Mar 30 '15 at 11:41
Same problem here... The coordinates from above also result in `true` – borchero Mar 30 '15 at 11:47

score 0 · Answer 6 · answered Sep 11 '22 at 16:46

Updating @Duyen-Hoa's answer to Swift 5.5:

func contains(polygon: [CGPoint], test: CGPoint) -> Bool {
    if polygon.count <= 1 {
        return false //or if first point = test -> return true
    }
    let p = UIBezierPath()
    let firstPoint = polygon[0] as CGPoint
    p.move(to: firstPoint)
    for index in 1...polygon.count-1 {
        p.addLine(to: polygon[index] as CGPoint)
    }
    p.close()
    return p.contains(test)
}

Check whether a point is inside of a simple polygon

6 Answers6

Linked