c++ - 由于标准测试失败，用于查找点是否在 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

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

您正在检查的点恰好位于多边形的线上，因此 float 很可能无法正确表示该点并在不正确时将其显示为在外面。

您可以接受此行为或在您的检查中添加一个小的错误容忍度。参见 What is the most effective way for float and double comparison?为了更大的图景。实际上，您需要确定您将接受的公差，并在检查时稍微扩展多边形。