algorithm - elasticsearch Geo_Polygon过滤算法

Question

通过 Elasticsearch GeoPolygonFilter 源代码，我遇到了pointInPolygon 方法。我无法真正理解该算法为何起作用，或者它是如何起作用的。这如何确定给定的 (lat,lon) 对位于该点定义的多边形内？

private static boolean pointInPolygon(Point[] points, double lat, double lon) {
    int i;
    int j = points.length - 1;
    boolean inPoly = false;

    for (i = 0; i < points.length; i++) {
        if (points[i].lon < lon && points[j].lon >= lon
                || points[j].lon < lon && points[i].lon >= lon) {
            if (points[i].lat + (lon - points[i].lon) /
                    (points[j].lon - points[i].lon) * (points[j].lat - points[i].lat) < lat) {
                inPoly = !inPoly;
            }
        }
        j = i;
    }
    return inPoly;
}

Answer 1

pointInPolygon() 方法实现了 crossing number algorithm .如果您对有关此功能的完整初步讨论感兴趣，可以找到它 here .

基本思想(在上面的第一个链接和 here 中说明)是检查从测试点开始的线在每个方向上穿过多边形边界的次数。如果该点位于多边形内部，您将获得奇数个十字，如果该点位于多边形外部，您将获得偶数个十字。