VPF::Попадание точки в многоугольник

Vardoulacha

Дата 20.4.2015, 14:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 11.8.2005

Репутация: 7
Всего: 8

Добрый день, уважаемые.

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

При этом точка не может быть на краю области, она обязательно или внутри или снаружи, иного не дано.

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

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

sQu1rr

Дата 20.4.2015, 15:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 2
Всего: 13

http://en.wikipedia.org/wiki/Point_in_polygon

Vardoulacha

Дата 20.4.2015, 16:41 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 11.8.2005

Репутация: 7
Всего: 8

Спасибо, почитаю, а так я кажется понял почему те решения что я нашел не работали, оказывается API Яндекс.Карты работают очень забавно, координаты которые они возвращают через функцию геокодирования никак не подписаны и непонятно где широта, а где долгота, в мануале черт ногу сломит, теперь надо по полочкам разобрать те скрипты, которые нашел и понять где там широта и долгота, похоже в этом причина

Смогу это сделать только в среду, надеюсь прокатит ) Отпишу потом здесь решение

sQu1rr

Дата 21.4.2015, 12:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 2
Всего: 13

Цитата(Vardoulacha @ 20.4.2015, 13:41

)

координаты которые они возвращают через функцию геокодирования никак не подписаны и непонятно где широта, а где долгота

Ну, первое широта, второе, долгота, это вроде интернациональный стандарт.
Да и какая разница, что первое, что второе, как будто от этого что-то зависит. многоугольник просто будет повернут на 90 градусов. Алгоритм все равно будет работать.

ksnk

Дата 21.4.2015, 12:30 (ссылка)

(нет голосов)

Загрузка ...

прохожий

Профиль
Группа: Комодератор
Сообщений: 6855
Регистрация: 13.4.2007
Где: СПб

Репутация: 96
Всего: 386

Цитата(sQu1rr @ 21.4.2015, 12:07

)

Да и какая разница, что первое, что второе, как будто от этого что-то зависит

Для исходных координат, обычно, где широта где долгота - известно. Так что не просто повернуто, но и еще смещено непонятно куда smile

C Яндексом смешно. В своих примера он, например, по запросу `Москва Тверская 7` выдает координатный прямоугольник

Код


<boundedBy xmlns="http://www.opengis.net/gml">
<Envelope>
<lowerCorner>37.602777 55.753321</lowerCorner>
<upperCorner>37.619234 55.762601</upperCorner>
</Envelope>
</boundedBy>

Смех начинается, когда вводишь эту пару в сами yandex.карты в окне параметров. Попадаем в кудато в Иране:crazy

Это сообщение отредактировал(а) ksnk - 21.4.2015, 12:32

--------------------

Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image

sQu1rr

Дата 21.4.2015, 16:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 2
Всего: 13

Цитата(ksnk @ 21.4.2015, 09:30

)

Смех начинается, когда вводишь эту пару в сами yandex.карты в окне параметров. Попадаем в кудато в Иране:crazy

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

Цитата(ksnk @ 21.4.2015, 09:30

)

Для исходных координат, обычно, где широта где долгота - известно. Так что не просто повернуто, но и еще смещено непонятно куда

Не понял, втупился, можно поподробнее?

ksnk

Дата 21.4.2015, 17:04 (ссылка)

(нет голосов)

Загрузка ...

прохожий

Профиль
Группа: Комодератор
Сообщений: 6855
Регистрация: 13.4.2007
Где: СПб

Репутация: 96
Всего: 386

Цитата(sQu1rr @ 21.4.2015, 16:25

)

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

Это я про то, что и сам yandex порядок своих координат путает... Или это фича такая, но выглядит забавно. ;)

Цитата(sQu1rr @ 21.4.2015, 16:25

)

Не понял, втупился, можно поподробнее?

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

--------------------

Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image

Vardoulacha

Дата 22.4.2015, 05:47 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 11.8.2005

Репутация: 7
Всего: 8

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

UPDATE
Ну вот, разобрался

Инструмент яндекса где методом перетаскивания карты можно найти координаты центра карты
http://dimik.github.io/ymaps/examples/location-tool/
порядок координат: широта, долгота
58.00752223, 56.23485616

Геокодер по адресу
http://geocode-maps.yandex.ru/1.x/?geocode=...
порядок координат: долгота, широта
56.235202, 58.007308

Функция установки точки
ymaps.GeoObject()
порядок координат: широта, долгота

Функция получения координат области
myPolygon.geometry.getCoordinates()
порядок координат: широта, долгота

Ну вот, все сложилось
1. я в редакторе строю область, получаю по ней координаты всех вершин в формате: широта, долгота
2. сервисом геокодера по адресу нахожу точку и получаю координаты в формате: долгота, широта
3. алгоритмом пытаюсь определить входит точка в область или нет

Конечно же не входит и никогда не войдет )) Получается надо всего лишь у точки координаты местами поменять и все прокатит )) ушел проверять.

UPDATE2

В мануале по геокодеру написано следующее "Независимо от значения этого параметра в ответе геокодера координаты всегда будут возвращаться в последовательности «долгота широта»." и написано это в параметре sco (только для обратного геокодирования) в разделе "Необязательные параметры"

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

Это сообщение отредактировал(а) Vardoulacha - 22.4.2015, 08:33

Vardoulacha

Дата 27.4.2015, 05:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 11.8.2005

Репутация: 7
Всего: 8

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

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

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

Начнем с исходных данных

Есть массив в котором адреса привязаны к почтовым индексам

Код


$data = [
    '614065' => [
        'Пермский край, город Пермь, шоссе Космонавтов, д. 166',
        'Пермский край, город Пермь, ул. Мира, д. 115',
    ],
];

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

Код


$data_polygon = [
    '614065' => [
        '614065-1' => [
            [57.9622, 56.1605],
            [57.9631, 56.1572],
            [57.9637, 56.1555],
            [57.9639, 56.1547],
            [57.9643, 56.1541],
            [57.9673, 56.1510],
            [57.9681, 56.1497],
            [57.9698, 56.1444],
            [57.9772, 56.1443],
            [57.9772, 56.1518],
            [57.9769, 56.1592],
            [57.9758, 56.1606],
            [57.9752, 56.1611],
            [57.9719, 56.1646],
            [57.9703, 56.1662],
            [57.9692, 56.1674],
            [57.9704, 56.1716],
            [57.9660, 56.1760],
            [57.9644, 56.1708],
            [57.9623, 56.1689],
            [57.9613, 56.1679],
            [57.9606, 56.1672],
            [57.9603, 56.1670],
            [57.9622, 56.1605],
            [57.9622, 56.1605],
        ],
        '614065-2' => [
            [57.9610, 56.1559],
            [57.9608, 56.1556],
            [57.9606, 56.1569],
            [57.9604, 56.1575],
            [57.9602, 56.1581],
            [57.9603, 56.1582],
            [57.9605, 56.1579],
            [57.9605, 56.1581],
            [57.9604, 56.1583],
            [57.9605, 56.1585],
            [57.9606, 56.1587],
            [57.9608, 56.1586],
            [57.9605, 56.1590],
            [57.9610, 56.1599],
            [57.9603, 56.1609],
            [57.9600, 56.1637],
            [57.9593, 56.1657],
            [57.9570, 56.1548],
            [57.9546, 56.1528],
            [57.9538, 56.1501],
            [57.9559, 56.1403],
            [57.9569, 56.1387],
            [57.9577, 56.1354],
            [57.9582, 56.1343],
            [57.9593, 56.1325],
            [57.9654, 56.1274],
            [57.9678, 56.1269],
            [57.9703, 56.1273],
            [57.9767, 56.1251],
            [57.9824, 56.1314],
            [57.9869, 56.1331],
            [57.9908, 56.1353],
            [57.9907, 56.1365],
            [57.9696, 56.1299],
            [57.9670, 56.1393],
            [57.9698, 56.1444],
            [57.9680, 56.1500],
            [57.9670, 56.1514],
            [57.9661, 56.1523],
            [57.9640, 56.1543],
            [57.9625, 56.1595],
            [57.9610, 56.1559],
            [57.9610, 56.1559],
        ],
    ],
];

Здесь представлю код который делает перебор и поиск данных, словом ФУНКЦИЯ представлен код примера определенной функции, смотреть ниже

Код


// Перебираем массив с почтовыми индексами
foreach ($data as $zip => $addr_list) {
    // Перебираем адреса внутри одного индекса
    foreach ($addr_list as $addr) {
        // Делаем запрос в геокодер Яндекса для определения координат центра точки
        $result = json_decode(file_get_contents('http://geocode-maps.yandex.ru/1.x/?geocode=' . urlencode($addr) . '&format=json'), true);

        // Здесь будем хранить результаты
        $finded = [];

        // Если был найден хотя бы один результат
        if ($result['response']['GeoObjectCollection']['metaDataProperty']['GeocoderResponseMetaData']['found'] > 0) {
            // Перебираем все варианты ответа
            foreach ($result['response']['GeoObjectCollection']['featureMember'] as $result_item) {
                // Смотрим на параметр точности, это должно быть полное совпадение
                if ($result_item['GeoObject']['metaDataProperty']['GeocoderMetaData']['precision'] == 'exact') {
                    // Получаем координаты центра точки, разбиваем их по пробелу
                    $coords = explode(' ', $result_item['GeoObject']['Point']['pos']);

                    // Координаты возвращаются в другом порядке, долгота широта, меняем местами
                    $finded[] = [
                        'x' => $coords[1],
                        'y' => $coords[0],
                    ];
                }
            }

            // Если результат всего один, значит мы нашли то что искали
            if (count($finded) == 1) {
                // Здесь будем хранить ответы поиска по областям
                $result_text = '';

                // Перебираем все области необходимого нам почтового индекса
                foreach ($data_polygon[$zip] as $zip_alias => $coords) {
                    ФУНКЦИЯ

                    $result_text .= '|' . $result_polygon_calc . '|';
                }
            } else {
                // Найдено более одного значения
                $result_text = 'many results';
            }
        } else {
            // Ничего не найдено
            $result_text = 'not found';
        }

        echo $zip . ' = ' . $addr . ' = ' . $result_text . '<br>';
    }
}

Теперь перейдем к функциям поиска в областях

Функция №1

Код


function into_poly($sx, $sy, &$coords, $x='x', $y='y')
{
    $pj=0;
    $pk=0;
    $wrkx=0;
    $yu = 0;
    $yl = 0;
    $n = count($coords);
    for ($pj=0; $pj<$n; $pj++)
    {
        $yu = $coords[$pj][$y]>$coords[($pj+1)%$n][$y]?$coords[$pj][$y]:$coords[($pj+1)%$n][$y];
        $yl = $coords[$pj][$y]<$coords[($pj+1)%$n][$y]?$coords[$pj][$y]:$coords[($pj+1)%$n][$y];
        if ($coords[($pj+1)%$n][$y] - $coords[$pj][$y])
            $wrkx = $coords[$pj][$x] + ($coords[($pj+1)%$n][$x] - $coords[$pj][$x])*($sy - $coords[$pj][$y])/($coords[($pj+1)%$n][$y] - $coords[$pj][$y]);
        else
            $wrkx = $coords[$pj][$x];
        if ($yu >= $sy)
            if ($yl < $sy)
            {
                if ($sx > $wrkx)
                    $pk++;
                if (abs($sx - $wrkx) < 0.00001) return 1;
            }
        if ((abs($sy - $yl) < 0.00001) && (abs($yu - $yl) < 0.00001) && (abs(abs($wrkx - $coords[$pj][$x]) + abs($wrkx - $coords[($pj+1)%$n][$x]) - abs($coords[$pj][$x] - $coords[($pj+1)%$n][$x])) < 0.0001))
            return 1;
    }
    if ($pk%2)
        return 1;
    else
        return 0;
}

Пример использования функции №1
Самая простая и удобная в использовании

Код


// Передаем координаты точки поиска, массив координат области и указываем где в массиве координат искать х, а где y
$result_polygon_calc = into_poly($finded[0]['x'], $finded[0]['y'], $coords, $x='0', $y='1');

Функция №2

Код


//Формирование массива [индекс][X][Y]
function fSetArrayXY(&$aArray,$aX,$aY,$aNewArray = false)
{
  if($aNewArray == true):
    $aArray     = array();
  endif;

  //Количество элементов в массиве
  $_Count =   count($aArray);

  //Группа параметров:
  $aArray[$_Count][cX] = $aX;
  $aArray[$_Count][cY] = $aY;
}

//Функция: определение вхождения точки в Полигон
function fPointInsidePolygon($aPolygon = "", $aPoint = "")
{
  $_PolygonSize = count($aPolygon);

  if ($_PolygonSize <= 1):
    $result   = false;
  else:

    $_intersections_num = 0;

    $_prev      = $_PolygonSize - 1;
    $_prev_under= $aPolygon[$_prev][cY] < $aPoint[cY];

    for ($i = 0; $i < $_PolygonSize; ++$i):

      $_cur_under   = $aPolygon[$i][cY] < $aPoint[cY];

      $a[cX]    = $aPolygon[$_prev][cX] - $aPoint[cX];
      $a[cY]    = $aPolygon[$_prev][cY] - $aPoint[cY];

      $b[cX]    = $aPolygon[$i][cX]  - $aPoint[cX];
      $b[cY]    = $aPolygon[$i][cY]  - $aPoint[cY];

      $t = ($a[cX]*($b[cY] - $a[cY]) - $a[cY]*($b[cX] - $a[cX]));

      if (($_cur_under == true) and (!$_prev_under == true)):

        if ($t > 0):
          $_intersections_num++;
        endif;

      endif;

      if ((!$_cur_under == true) and ($_prev_under == true)):

        if ($t < 0):
          $_intersections_num++;
        endif;

      endif;

      $_prev        = $i;
      $_prev_under  = $_cur_under;

    endfor;

    $result = !($_intersections_num & 1) == 0;
  endif;


  return $result;
}

Пример использования функции №2
Эта функция какая-то слишком замудреная

Код


// Составляем массив координат области
$array = [];
foreach ($coords as $coord) {
    fSetArrayXY($array, $coord[0], $coord[1]);
}

// Делаем определенный массив для точки
$_Point = [
    'cX' => $finded[0]['x'],
    'cY' => $finded[0]['y'],
];

// Ищем в области
$_PointInsidePolygon = fPointInsidePolygon($array, $_Point);
if ($_PointInsidePolygon == true) {
    $result_polygon_calc = "1";
} else {
    $result_polygon_calc = "0";
}

Функция №3

Код


class Polygon {

    protected $polygon = array();

    /**
     * Polygon itself, with basic vector-based structure
     * Array: [ [1,1], [2,1], [3,0], [2,-1] ]
     *
     * @var $polygon array
     */

    public function set_polygon($polygon) {
        if (count($polygon)<3) return false;
        if (!isset($polygon[0]['x'])) {
            foreach ($polygon as &$point) {
                $point = array('x' => $point[0], 'y' => $point[1]);
            }
        }
        $this->polygon = $polygon;
    }

    /**
     * Check if $polygon contains $test value
     *
     * @var $test array(x=>decimal, y=>decimal)
     */

    public function calc($test) {
        $q_patt= array( array(0,1), array(3,2) );
        $end = end($this->polygon);
        $pred_pt = end($this->polygon);
        $pred_pt['x'] -= $test['x'];
        $pred_pt['y'] -= $test['y'];
        $pred_q = $q_patt[$pred_pt['y']<0][$pred_pt['x']<0];
        $w = 0;
        for ($iter = reset($this->polygon); $iter!==false;$iter=next($this->polygon)) {
            $cur_pt = $iter;
            $cur_pt['x'] -= $test['x'];
            $cur_pt['y'] -= $test['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;
        return $w;
    }

}

Пример использования функции №3

Код


$polygon->set_polygon($coords);
$result_polygon_calc = $polygon->calc([
    'x' => $finded[0]['x'],
    'y' => $finded[0]['y'],
]);

Результат работы всех трех функций приведу одним примером, все функции возвращают одно и то же

614065 = Пермский край, город Пермь, шоссе Космонавтов, д. 166 = |0||1|
614065 = Пермский край, город Пермь, ул. Мира, д. 115 = |1||0|

Как видно первый адрес попал во вторую область, а второй адрес в первую, все верно, так и должно быть

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »