algorithm - 检查一个点是否在一个简单的多边形内

Question

我正在尝试确定一个点是否位于多边形内部。我使用来自 this website 的以下(针对 Swift 修改)算法:

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;
}

但是，当具有具有以下坐标的简单多边形时:(x: 0, y: 40), (x: 0, y: 0), (x: 20, y: 0), (x : 20, y: 20), (x: 40, y: 20), (x: 40, y: 40)，然后检查点 (x: 30, y: 20) 当 i 和 j 分别为 5 和 4 ((x : 40, y: 40) 和 (x: 40, y: 20))，尽管该点仅位于多边形的边界处。如果该点确实位于 多边形中，则该函数实际上应该只评估 true。感谢您对算法的任何帮助或改进/调整!

Answer 1

如果这是针对 iOS 应用程序，请将多边形转换为 UIBezierPath，然后使用函数 containtsPoint() 验证您的点是否在该 bezierpath 的一侧

示例(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)
    }