Проверка того, находится ли координата долготы/широты внутри сложного многоугольника во встроенном устройстве?

Мне нужно, чтобы пользователь мог нарисовать сложный многоугольник на карте, а затем попросить приложение проверить, находится ли заданная долгота/широта внутри этого многоугольника.

Я смог найти только алгоритмы, которые использовали простую x/y декартову систему координат, которая не компенсирует кривизну земли.

Пользователь рисует многоугольник на ПК, где точки передаются по радио на встроенное устройство, после чего необходимо проверить, находится ли данный многоугольник в его текущем положении (взято из GPS).

Как и для встроенного устройства, я не могу использовать огромные библиотеки, вместо этого мне нужен алгоритм для выполнения проверки самой или очень маленькой библиотеки. Но я, похоже, не могу найти такой алгоритм.

Ответ 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" тестируемой точки. Затем вы обнаружите, сколько из них пересекает вертикальную линию, которая простирается выше вашей точки. Если четное число пересекает точку, то вы находитесь за пределами полигона. Если нечетное число пересекает выше, то вы внутри.

Ответ 2

Хорошие объяснения и простой код C, который вы можете преобразовать в свои потребности

http://alienryderflex.com/polygon/

Объедините проверку многоугольника с RTree для быстрого отбраковки дерева поиска, если у вас много не перекрывающихся полигонов.