当标准测试失败时，用于查找点是否在2D多边形内的替代测试

Question

我写了以下代码来确定一个点是否在多边形内——使用交叉数和缠绕数测试的算法。然而，我发现当我的多边形是：（10,10），（10,20）、（20,20）和（20,10）时，这些测试失败了，而我想找到它是否在多边形中的点是：（20,15）。我这里的点表示位置的（纬度、经度）。

（20,15）位于边界上，因此应在多边形内

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct {int x, y;} Pt;
inline int
isLeft( Pt P0, Pt P1, Pt P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y)
            - (P2.x -  P0.x) * (P1.y - P0.y) );
}
int crossingNumTest( Pt P, Pt* V, int n )
{
    int    cn = 0;    
    for (int i=0; i<n; i++) {    
       if (((V[i].y <= P.y) && (V[i+1].y > P.y)) 
        || ((V[i].y > P.y) && (V[i+1].y <=  P.y))) { 
            float vt = (float)(P.y  - V[i].y) / (V[i+1].y - V[i].y);
            if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) 
                 ++cn;   
        }
    }
    return (cn&1);    
}
int windingNumTest( Pt P, Pt* V, int n )
{
    int    wn = 0;    
    for (int i=0; i<n; i++) {   
        if (V[i].y <= P.y) {    
            if (V[i+1].y  > P.y)  
                 if (isLeft( V[i], V[i+1], P) > 0)  
                     ++wn;           
        }
        else {                       
            if (V[i+1].y  <= P.y)    
                 if (isLeft( V[i], V[i+1], P) < 0)  
                     --wn;          
        }
    }
    return wn;
}
//===================================================================
int main(int argc, char** argv) {
    Pt arr[11];
    arr[0].x=10;
    arr[0].y=10;
    arr[1].x=10;
    arr[1].y=20;
    arr[2].x=20;
    arr[2].y=20;
    arr[3].x=20;
    arr[3].y=10;
    Pt test;
    test.x=20; test.y=15;
    cout<<"1.polygon inside="<<crossingNumTest(test,arr,4)<<"n";
    cout<<"2.polygon inside="<<windingNumTest(test,arr,4)<<"n";
    return (EXIT_SUCCESS);
}

Answer 1

这很可能是浮点精度问题。

您正在检查的点正好在多边形的线上，因此浮点很可能无法正确地表示该点，并在不在外部时显示为在外部。

您可以接受这种行为，也可以在检查时添加一个小的容错范围。请参阅浮动和双重比较的最有效方法是什么？为了更大的画面。实际上，你需要确定你将接受的公差，并在检查时稍微扩展你的多边形。

Answer 2

不需要float，并且会产生潜在的舍入问题
使用精确（可能更快）的整数数学。将测试改为数学等效
（注意：这种新方法不可能除以0，因为没有进行除法）

// float vt = (float)(P.y  - V[i].y) / (V[i+1].y - V[i].y);
// if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) ++cn;   
//  Note: Use long long math if needed
int dy0 = P.y  - V[i].y;
int dy1 = V[i+1].y - V[i].y;
int dx0 = P.x  - V[i].x;
int dx1 = (V[i+1].x - V[i].x;
if (dy1*dx0 < dy0*dx1) ++cn;

[Edit]@user3629249 comment指出了一个数组访问违规。建议：

int crossingNumTest( Pt P, Pt* V, int n ) {
    // for (int i=0; i<n; i++) {    
    for (int i=1; i<n; i++) {    
       // if (((V[i].y <= P.y) && (V[i+1].y > P.y)) 
       if (((V[i-1].y <= P.y) && (V[i].y > P.y)) 
    ...
}