我正在尝试确定一个点是否位于多边形内部。我使用以下(针对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)
)时,if语句求值为true
,尽管该点仅位于多边形的边界处。如果点确实位于多边形中,则函数实际上只应计算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)
}
也适用于我,所以我不知道的问题在哪里
我还制作了一个使用swift迭代器的轻微修改版本:
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
}
以下是你在操场上的阵列样本的结果:
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
swift:中MKPolygon
的简单扩展
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)
}
}
}
这里是PNPoly算法的改进实现。我用过它,效果很好。
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
}
以进行进一步的查询检查:http://alienryderflex.com/polygon/
这是javascript代码(易于理解,可以在swift上重写)。它非常适合我,几乎100%,即非常精确。
你的解决方案精度很差。
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;
}
更新@Duyen Hoa对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)
}