判断点是否在多边形上算法roadMap

经历了三个版本，虽然都是小改动，但是表现出的效果还是相差蛮大

第一版是移植的别人的

（试用之后我发现点相交于多边形的边上效果不是很好）

第二版改善了点相交于多边形边上的判断

（改善之后效果比较明显，但还是会偶发判断失准）

第三版增加了数量级的判断，将偶发性的判断失准再降下一个台阶

（数值计算误差是不可避免的，所以在判断相等的时候，必得要确定一个可容忍的误差数量级）

下面上三版的相关代码，第二版带Ex，第三版带ExII

/** 检查多边形的包围盒是否相交~ */
-(BOOL) isBoundingBoxIntersect:(BoundingBox)bb1 bb2:(BoundingBox)bb2 {
    if(bb1.maxX>=bb2.minX && bb2.maxX>=bb1.minX && 
       bb1.maxY>=bb2.minY && bb2.maxY>=bb1.minY) {
        return YES;
    }
    return NO;
}

/** 检查某点是否包含在多边形的范围内~ */
-(BOOL) isPolygonContainsPoint:(BYPolygon*)poly point:(b2Vec2)p {
    int verticesCount = [poly verticesCount];
    b2Vec2 *ptPolygon = [poly vertices];
    
    int nCross = 0;
    for (int i = 0; i < verticesCount; ++ i) {
        b2Vec2 p1 = ptPolygon[i];
        b2Vec2 p2 = ptPolygon[(i + 1) % verticesCount];
        
        // 求解 y = p.y 与 p1-p2 的交点~
        if (p1.y == p2.y) {   // p1-p2 与 y = p0.y 平行~
            continue;
        }
        if (p.y < fminf(p1.y, p2.y)) { // 交点在 p1-p2 延长线上~
            continue;
        }
        if (p.y > fmaxf(p1.y, p2.y)) { // 交点在 p1-p2 延长线上~
            continue;
        }
        
        // 求交点的 X 坐标~
        double x = (double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;
        
        // 只统计单边交点~
        if (x > p.x) {
            nCross ++;
        }
    }
    
    // 单边交点为偶数，点在多边形之外~
    if(nCross%2 == 1) {
        return YES;
    } else {
        return NO;
    }
}


/** 对某点正好被包含在多边形的边上具有更好的适用性~ */
-(BOOL) isPolygonContainsPointEx:(BYPolygon*)poly point:(b2Vec2)p {
    int verticesCount = [poly verticesCount];
    b2Vec2 *ptPolygon = [poly vertices];
    /** added on 2011.10.02.15.21，是否正好相交在边上~ */
    bool isIntersectOnSection = false;
    
    int nCross = 0;
    for (int i = 0; i < verticesCount; ++ i) {
        b2Vec2 p1 = ptPolygon[i];
        b2Vec2 p2 = ptPolygon[(i + 1) % verticesCount];
        
        // 求解 y=p.y 与 p1 p2 的交点
        if (p1.y == p2.y) {   // p1p2 与 y=p0.y平行
            continue;
        }
        if (p.y < fminf(p1.y, p2.y)) { // 交点在p1p2延长线上
            continue;
        }
        if (p.y > fmaxf(p1.y, p2.y)) { // 交点在p1p2延长线上
            continue;
        }
        // 求交点的 X 坐标
        double x = (double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;
        
        /** added on 2011.10.02.15.21，是否正好相交在边上~ */
        if (x == p.x) {
//            NSLog(@"点正好相交在多边形的边上~");
            isIntersectOnSection = true;
            break;
        }
        if (x > p.x) { // 只统计单边交点
            nCross ++;
        }
    }
    if(isIntersectOnSection || nCross%2==1) {    // 单边交点为偶数，点在多边形之外
        return YES;
    } else {
        return NO;
    }
}

/** 对某点正好被包含在多边形的边上具有更好的适用性~ */
-(BOOL) isPolygonContainsPointExII:(BYPolygon*)poly point:(b2Vec2)p {
    int verticesCount = [poly verticesCount];
    b2Vec2 *ptPolygon = [poly vertices];
    /** added on 2011.10.02.15.21，是否正好相交在边上~ */
    bool isIntersectOnSection = false;
    
    int nCross = 0;
    for (int i = 0; i < verticesCount; ++ i) {
        b2Vec2 p1 = ptPolygon[i];
        b2Vec2 p2 = ptPolygon[(i + 1) % verticesCount];
        
        // 求解 y=p.y 与 p1 p2 的交点
        if (p1.y == p2.y) {   // p1p2 与 y=p0.y平行
            continue;
        }
        if (p.y < fminf(p1.y, p2.y)) { // 交点在p1p2延长线上
            continue;
        }
        if (p.y > fmaxf(p1.y, p2.y)) { // 交点在p1p2延长线上
            continue;
        }
        // 求交点的 X 坐标
        double x = (double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;
        
        /** added on 2011.10.02.15.21，是否正好相交在边上~ */
//        NSLog(@" —— x=%f, p.x=%f", x, p.x);
        if (fabs(x - p.x) < 10e-4) {
//            NSLog(@"点正好相交在多边形的边上~");
            isIntersectOnSection = true;
            break;
        }
        if (x > p.x) { // 只统计单边交点
            nCross ++;
        }
    }
    if(isIntersectOnSection || nCross%2==1) {    // 单边交点为偶数，点在多边形之外
        return YES;
    } else {
        return NO;
    }
}

评论

1 楼 luxiaofei 2013-06-05  

看了好久有些不明白
为什么你 p2要这样取呢
b2Vec2 p2 = ptPolygon[(i + 1) % verticesCount]