我正在尝试确定一个点是否位于多边形内部。我使用来自 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
。感谢您对算法的任何帮助或改进/调整!
最佳答案
如果这是针对 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)
}
关于algorithm - 检查一个点是否在一个简单的多边形内,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29344791/