检查点是否在简单多边形内 [英] Check whether a point is inside of a simple polygon

问题描述

我正在尝试确定一个点是否位于多边形内部.我从此网站:

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)，结果为true，因为当i和j为5和4((x: 40, y: 40)和(x: 40, y: 20))，尽管该点仅位于多边形的边界.如果该点确实位于多边形中 中，则该函数实际上仅应评估true.感谢您对算法的任何帮助或改进/调整！

解决方案

如果这是针对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)
    }

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!

解决方案

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

这篇关于检查点是否在简单多边形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！