эластичный поиск алгоритм GeoPolygonFilter

Question

Пройдя через эластичный поиск 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) состоит в том, чтобы проверить, сколько раз линия, начинающаяся с тестируемой точки, пересекает границы многоугольника в каждом направлении. Если точка лежит внутри многоугольника, вы получите нечетное количество крестов, и если точка лежит вне полигона, вы получите четное количество крестов.