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!

Answer 1

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

Answer 2

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/