Ответ 1
Вот реализация, которую я написал в С# для класса Polygon, который содержит список вершин. Он не учитывает кривизну Земли. Скорее, вы должны предварительно обработать многоугольник на более мелкие сегменты, прежде чем запускать это.
Производительность этого алгоритма очень хорошая. Даже для многоугольников с тысячами ребер он заканчивается примерно на один или два миллисекунды на моем рабочем столе.
Код был оптимизирован совсем немного, и поэтому он не читается как psuedo-code.
public bool Contains(GeoLocation location)
{
if (!Bounds.Contains(location))
return false;
var lastPoint = _vertices[_vertices.Length - 1];
var isInside = false;
var x = location.Longitude;
foreach (var point in _vertices)
{
var x1 = lastPoint.Longitude;
var x2 = point.Longitude;
var dx = x2 - x1;
if (Math.Abs(dx) > 180.0)
{
// we have, most likely, just jumped the dateline (could do further validation to this effect if needed). normalise the numbers.
if (x > 0)
{
while (x1 < 0)
x1 += 360;
while (x2 < 0)
x2 += 360;
}
else
{
while (x1 > 0)
x1 -= 360;
while (x2 > 0)
x2 -= 360;
}
dx = x2 - x1;
}
if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
{
var grad = (point.Latitude - lastPoint.Latitude) / dx;
var intersectAtLat = lastPoint.Latitude + ((x - x1) * grad);
if (intersectAtLat > location.Latitude)
isInside = !isInside;
}
lastPoint = point;
}
return isInside;
}
Основная идея состоит в том, чтобы найти все ребра многоугольника, которые охватывают позицию "x" тестируемой точки. Затем вы обнаружите, сколько из них пересекает вертикальную линию, которая простирается выше вашей точки. Если четное число пересекает точку, то вы находитесь за пределами полигона. Если нечетное число пересекает выше, то вы внутри.