Geo Fencing - точка внутри / снаружи полигона

Question

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

Кто-нибудь знает, есть ли какой-либо пример подобного алгоритма?

Answer 1

Я добавляю одну деталь, чтобы помочь людям, которые живут на ... юге земли !! Если вы в Бразилии (это мой случай), наши координаты GPS все отрицательные. И все эти алгоритмы дают неверные результаты.

Самый простой способ, если использовать абсолютные значения широты и долготы всей точки. И в этом случае алгоритм Яна Коберского идеален.

Answer 2

Я перевел метод c # на Php и добавил много комментариев, чтобы понять код.

Описание PolygonHelps:
Проверьте, находится ли точка внутри или снаружи многоугольника. Эта процедура использует координаты GPS и работает, когда полигон имеет небольшую географическую область.


ВХОД:
$ poly: массив Point: список вершин многоугольника; [{Point}, {Point}, ...];
$ point: точка для проверки; Точка: {"lat" => "x.xxx", "lng" => "y.yyy"}


Когда $ c равно false, число пересечений с многоугольником является четным, поэтому точка находится за пределами многоугольника;
Когда $ c равно true, число пересечений с многоугольником является нечетным, поэтому точка находится внутри многоугольника;
$ n - количество вершин в многоугольнике;
Для каждой вершины в многоугольнике метод вычисляет линию, проходящую через текущую вершину и предыдущую вершину, и проверяет, имеют ли две линии точку пересечения.
$ c изменяется, когда точка пересечения существует.
Таким образом, метод может вернуть true, если точка находится внутри многоугольника, иначе вернуть false.

class PolygonHelps {

    public static function isPointInPolygon(&$poly, $point){

        $c = false; 
        $n = $j = count($poly);


        for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){

            if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) ) 
                || ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) ) 

            && ( $point->lng <   ( $poly[$j]->lng - $poly[$i]->lng ) 
                               * ( $point->lat    - $poly[$i]->lat ) 
                               / ( $poly[$j]->lat - $poly[$i]->lat ) 
                               +   $poly[$i]->lng ) ){

                $c = !$c;
            }
        }

        return $c;
    }
}

Answer 3

многоугольник определяется как последовательный список пар точек A, B, C .... A. нет стороны A-B, B-C ... пересекает любую другую сторону

Определить поле Xmin, Xmax, Ymin, Ymax

случай 1, контрольная точка P лежит за пределами поля

В случае 2 контрольная точка P лежит внутри коробки:

Определите «диаметр» D коробки {[Xmin, Ymin] - [Xmax, Ymax]} (и добавьте немного больше, чтобы избежать возможной путаницы с D на стороне)

Определить градиенты М со всех сторон

Найдите градиент Mt, наиболее отличающийся от всех градиентов M

Тестовая линия проходит от P при градиенте Mt на расстояние D.

Установить количество пересечений на ноль

Для каждой из сторон A-B, тест B-C для пересечения P-D со стороной от его начала до, но НЕ ВКЛЮЧАЯ его конца. Увеличить количество пересечений если необходимо. Обратите внимание, что нулевое расстояние от P до пересечения указывает, что P находится на стороне

Нечетное число указывает, что P находится внутри многоугольника

Answer 4

Если у вас есть простой многоугольник (ни одна из линий не пересекается), и у вас нет отверстий, вы также можете триангулировать многоугольник, что вы, вероятно, в любом случае собираетесь сделать в ГИС-приложении, чтобы нарисовать TIN, затем проверьте точки в каждом треугольнике. Если у полигона есть небольшое количество ребер, но много точек, это быстро.

Интересную точку в треугольнике см. текст ссылки

В противном случае определенно используйте правило намотки, а не пересечение ребер, у пересечения ребер есть реальные проблемы с точками на ребрах, что очень вероятно, если ваши данные генерируются из GPS с ограниченной точностью.

Answer 5

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

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

Если ваш воображаемый луч движется в направлении -x, вы можете выбрать только количество линий, которые включают хотя бы одну точку, координата y которой строго меньше, чем координата y вашей точки. Вот так вы получаете правильную работу большинства странных крайних случаев.

Answer 6

Проверьте, находится ли точка внутри многоугольника или нет -

Рассмотрим многоугольник с вершинами a1, a2, a3, a4, a5. Следующий набор шагов должен помочь определить, находится ли точка P внутри многоугольника или снаружи.

Вычислить векторную область треугольника, образованного ребром a1-> a2 и векторами, соединяющими a2 с P и P с a1. Точно так же вычислите векторную область каждого из возможных треугольников, одна сторона которых является стороной многоугольника, а две другие соединяют P с этой стороной.

Чтобы точка находилась внутри многоугольника, каждый из треугольников должен иметь положительную площадь. Даже если один из треугольников имеет отрицательную область, точка P выделяется из многоугольника.

Чтобы вычислить площадь треугольника с учетом векторов, представляющих его 3 ребра, см. http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm