是什么让多边形算法只有在正向和反向运行时才能正常工作？

Question

我为“c++ 的多边形点算法”找到的最流行的答案似乎是这个 C 算法： https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html

但是，当我在我的程序中实现它时，它无法对某些形状正常工作。就像我画一个圆圈，但一侧是一条小角度的直线。经过几个小时的猜测和尝试其他算法，我想出了一个解决方案，我运行算法一次，然后我再次运行算法，但多边形点颠倒了。这解决了所有形状的问题，但我不明白为什么。我将如何消除这个额外的循环？输入数据是否需要以某种方式对点进行排序或处理才能正常工作？

我对该算法的应用是让用户使用 javascript api 在 google 地图上绘制任何多边形形状，然后发送形状的点到服务器，C++ 然后运行s 算法从搜索结果中排除位置。因为用户正在绘制多边形，所以它可以顺时针或逆时针绘制，并且可以是任何复杂甚至重叠的形状，所以我不能在我的应用程序中强制使用可预测的绘制顺序或简单的多边形。

我的数据结构有点不同，但我觉得逻辑和原来的算法是一样的。我也有意在 2 个比较中使用了 >=，我认为这涵盖了点在多边形边缘的一些情况，但我认为其余的是相同的。

数组正在存储 x,y,x,y 之类的点。我的数组在数组的开头和结尾总是有相同的点。我也是故意使用 int 的，因为在我的用例中我不需要 double/float 。我正在显示世界的一小部分，并将度数转换为英尺以使用 int。

bool pointInPolygon = false;
int lastPointIndex=search->polygonSize-2;
int lastX=search->polygon[lastPointIndex];
int lastY=search->polygon[lastPointIndex+1];
for (int i=0; i < search->polygonSize; i+=2) {
    int x=search->polygon[i];
    int y=search->polygon[i+1];
    if ( ((y>=listing->longitude) != (lastY>=listing->longitude)) && 
(listing->latitude <= (lastX-x) * (listing->longitude-y) / (lastY-y) + x) ){
        pointInPolygon = !pointInPolygon;
    }
    lastX=x;
    lastY=y;
    lastPointIndex=i;
}
if(!pointInPolygon){
    return false;
}
pointInPolygon=false;
lastPointIndex=search->polygonSize-2;
lastX=search->polygon[lastPointIndex];
lastY=search->polygon[lastPointIndex+1];
for (int i=0; i < search->polygonSize; i+=2) {
    int x=search->polygonReverse[i];
    int y=search->polygonReverse[i+1];
    if ( ((y>=listing->longitude) != (lastY>=listing->longitude)) && 
(listing->latitude <= (lastX-x) * (listing->longitude-y) / (lastY-y) + x) ){
        pointInPolygon = !pointInPolygon;
    }
    lastX=x;
    lastY=y;
    lastPointIndex=i;
}
if(!pointInPolygon){
    return false;
}

这是问题点的示例： 8245533,28415352,8236498,28392000,8220158,28373794,8205897,28364691,8195806,28361525,8176659,28360734,8170041,28362317,8161681,28366275,8152969,28374190,8143906,28390417,8140769,28403082,8137979,28435932,8137979, 28451368,8139374,28459679,8148438,28482239,8153318,28489759,8159590,28495695,8165861,28499258,8174918,28500445,8245533=28[414535]

这里有一个点在算法只运行一次的时候没有正确过滤。像我的代码例子一样运行两次就不会出现这个问题。 8230098,28456924

此图显示了地图上的同一多边形和点。请注意，我将经度坐标偏移 180 度以获得正数。

更新：看起来 aschepler 发现我的整数在多边形中的长线的这种情况下溢出，我需要使用双精度。我将继续使用 int 但在多边形搜索中转换为 double 以更正此问题。如果他们选择 post 作为答案，我会将它们标记为答案。谢谢！

我认为使用 int 而不是 double 作为坐标会很聪明，因为我只需要搜索美国，并且我已将 8 个搜索条件组合到 AVX2 SIMD 指令中，这些指令以 int 形式存储在 256 位中C++ 中的数据类型，用于构建非常快速的内存搜索系统。在对坐标进行初始矩形过滤后，我现在必须转换为 double 以对较少数量的记录进行多边形搜索。它仍然非常有效。我必须记住，如果有一天我再次需要它，我的坐标相乘需要更高的精度。只搜索一个矩形只需要 > 或 < 操作，所以有足够的精度。

Answer 1

@aschepler 在上面的评论中回答了我的问题。当点是一条长直线时，int 溢出。我不得不为乘法运算使用更高精度的转换，如 double 或 long long 来修复它。谢谢！

是什么让多边形算法只有在正向和反向运行时才能正常工作？

What would make the point in polygon algorithm only work correctly when run in both forward and reverse?

c++

algorithm

point-in-polygon

是什么让多边形算法只有在正向和反向 运行 时才能正常工作？

What would make the point in polygon algorithm only work correctly when run in both forward and reverse?

c++

algorithm

point-in-polygon

是什么让多边形算法只有在正向和反向运行时才能正常工作？