c - 多边形中的点 - 算法错误

Question

我有一个算法的 C 代码，用于检查给定点是否在多边形内部。它应该是正确的，我也不断在不同的地方看到这段代码。然而，当我使用它时，它并不能完美地工作 - 大约 20% 的答案是错误的。

int pnpoly(int nvert, double *vertx, double *verty, double testx, double testy)
{
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
        (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
        c = !c;
    }
    return c;
}

也许我的主要功能有问题。有人能给我一个主要函数来检查这个算法吗？

<小时/>

这是我的主要功能

int main(){

    double vertx[4] = {10, 10, 0, 0};
    double verty[4] = {10, 0, 10, 0};

    // for those two it returns "Inside"
    double testx = 6;
    double testy = 4;

    /* for those two it returns "Outside"
    double testx = 5;
    double testy = 4;
    */

    int result = pnpoly(4, vertx, verty, testx, testy);

    if (result) {
        printf("\nInside\n");
    }

    else {
        printf("\nOutside\n");
    }

    return 0;
}

Answer 1

您的多边形是自相交的。 (5,4) 位于“外部”是正常的

我认为您认为您的多边形是正方形，即使对于自相交的多边形，该算法也能完美运行。