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

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

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

Итак, приступим!

Кратко порядок алгоритма:

  • Переводит переданные координаты точки в нужный формат в виде массива [x => num, y => num].
  • Сам переданный полигон (массив массивов [x, y]) также переводит в нужный формат.
  • Рассчитывает попадает ли указанная точка в этот полигон. Возвращает true/false.

Полный код: 

<?php

class Polygon
{
    /**
     * @param $lat - coord X number
     * @param $lon - coord Y number
     * @param $polygonArray - array of points ([x, y])
     *
     * @return bool
     */
    public static function isPointInPolygon($lat, $lon, $polygonArray)
    {
        $pointArray = self::formatPointToArray($lat, $lon);

        return self::pointInPolygon($pointArray, $polygonArray);
    }

    private static function formatPointToArray($lat, $lon)
    {
        return ['x' => $lat, 'y' => $lon];
    }

    private static function formatPolygon($polygon)
    {
        if (!isset($polygon[0]['x'])) {
            foreach ($polygon as &$point) {
                $point = [
                    'x' => $point[0],
                    'y' => $point[1],
                ];
            }
        }

        return $polygon;
    }

    private static function pointInPolygon($point, $polygon)
    {
        $q_patt = [[0, 1], [3, 2]];

        $polygon = self::formatPolygon($polygon);

        $pred_pt = end($polygon);
        $pred_pt['x'] -= $point['x'];
        $pred_pt['y'] -= $point['y'];
        $pred_q = $q_patt[$pred_pt['y'] < 0][$pred_pt['x'] < 0];
        $w = 0;

        for ($iter = reset($polygon); $iter !== false; $iter = next($polygon)) {
            $cur_pt = $iter;
            $cur_pt['x'] -= $point['x'];
            $cur_pt['y'] -= $point['y'];
            $q = $q_patt[$cur_pt['y'] < 0][$cur_pt['x'] < 0];

            switch ($q - $pred_q) {
                case -3:
                    ++$w;
                    break;
                case 3:
                    --$w;
                    break;
                case -2:
                    if ($pred_pt['x'] * $cur_pt['y'] >= $pred_pt['y'] * $cur_pt['x'])
                        ++$w;
                    break;
                case 2:
                    if (!($pred_pt['x'] * $cur_pt['y'] >= $pred_pt['y'] * $cur_pt['x']))
                        --$w;
                    break;
            }

            $pred_pt = $cur_pt;
            $pred_q = $q;
        }

        return $w != 0;
    }
}

Таким образом, входным методом является isPointInPolygon(), который принимает на вход 2 координаты и полигон (массив массивов [x, y]).

Пример использования

Возьмем для примера полигон точек, описывающий МКАД в Москве. 

<?php

$mkadPolygon = [
    [
        55.608453194574,
        37.494475522621,
    ],
    [
        55.613591349063,
        37.488613938377,
    ],
    [
        55.618200299476,
        37.483151140944,
    ],
    //...
];

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

Допустим, у нас есть какая-то точка, заданная 2 координатами [x, y] (или [lat, lon], как их часто называют в картах): 55.765692, 37.600303 – она точно находится внутри МКАДа (если интересно, то точка соответствует Патриаршим прудам в Москве).

Вызываем метод класса, передавая координаты и полигон: 

<?php

//true
Polygon::isPointInPolygon(55.765692, 37.600303, $mkadPolygon);

Результатом выполнения в данном случае будет true.

Если же взять, например, точку 55.992992, 37.213338 (Зеленгоград), то функция вернет уже false. 

<?php

//false
Polygon::isPointInPolygon(55.992992, 37.213338, $mkadPolygon);

P.S. Если вы храните полигон где-то в админке в виде JSON, то не забывайте сначала перевести его в массив через json_decode(), а потом уже передавать в метод.