Алгоритм Raycasting с GPS-координатами

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

Пользователь вводит адрес, а PHP-скрипт извлекает lat / long из API геокодирования и применяет raycasting с кучей координат, которые составляют вершины региона (взяты из файла KML, созданного Картами).

Проблема заключается в следующем: он работает большую часть времени, но некоторые адреса за пределами области обслуживания неправильно сообщают как имеющие право на участие, в то время как некоторые другие в регионе не имеют права. Сначала я думал, что это была проблема с картами Google, но координаты, созданные с помощью адресов в службе геокодирования, точны. Вероятно, это связано с формулой.

Вот он (он основан на коде, который я нашел в другом месте):

// $points is an array full of Point objects (the vertices), which contain lat/long variables // $ctr is simply a counter that we will test to see if it's even/odd for ($i = 0, $j = sizeof($points) - 1; $i < sizeof($points); $j = $i++) { $p1 = $points[$i]; $p2 = $points[$j]; // $test_point is the lat/long pair of the user's address if ($p1->lat < $test_point->lat && $p2->lat >= $test_point->lat || $p2->lat < $test_point->lat && $p1->lat >= $test_point->lat) { if ($p1->long + ($test_point->lat - $p1->lat)/($p2->lat - $p1->lat)*($p2->long - $p1->long) < $test_point->long) $ctr++; } } 

Здесь что-то не хватает? Я попытался получить формулу самостоятельно, и в какой-то степени я понимаю математику, но согласны ли с этим использовать GPS-координаты с карт Google?

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

Ну … ваша вторая, если () не компенсирует тот факт, что любое из вычитаний может привести к отрицательному числу; он будет работать, только если координаты строго упорядочены.

Обновление: на http://rosettacode.org/wiki/Ray-casting_algorithmn существует целая группа алгоритмов на разных языках, которые подробно описывают процесс (к сожалению, для PHP нет версии). То, что, как представляется, отсутствует в вашем решении, – это выбор точки, которая, как гарантируется, окажется вне полигона; так как вы имеете дело с долготой / широтой, что должно быть легко. Во-вторых, убедитесь, что ваш многоугольник закрыт (т.е. переходите от последней точки к первой, если Google Maps этого еще не делает)

Предполагая, что массив $points содержит углы многоугольника, описывающие зону покрытия по часовой стрелке (или против часовой стрелки), ваш код выглядит правильно для меня. В принципе, он подсчитывает количество краев многоугольника, которые пересекают линию, нарисованную восточнее от данной точки до 180-го меридиана.

Я бы, наверное, переписал это так, просто для ясности:

 $p0 = end($points); foreach ( $points as $p1 ) { // ignore edges of constant latitude (yes, this is correct!) if ( $p0->lat != $p1->lat ) { // scale latitude of $test_point so that $p0 maps to 0 and $p1 to 1: $interp = ($test_point->lat - $p0->lat) / ($p1->lat - $p0->lat); // does the edge intersect the latitude of $test_point? // (note: use >= and < to avoid double-counting exact endpoint hits) if ( $interp >= 0 && $interp < 1 ) { // longitude of the edge at the latitude of the test point: // (could use fancy spherical interpolation here, but for small // regions linear interpolation should be fine) $long = $interp * $p1->long + (1 - $interp) * $p0->long; // is the intersection east of the test point? if ( $long < $test_point->long ) { // if so, count it: $ctr++; } } } $p0 = $p1; } 

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

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

Существует ошибка с этим алгоритмом, когда луч касается касательной к форме. Просто добавьте epsilon к широте тестовой точки, когда это может произойти (строка 3 кода Илмари):

 if ($test_point->lat == $p0->lat) $test_point->lat += 0.0000000001; 

Также см. http://rosettacode.org/wiki/Ray-casting_algorithm (исправленный URL).

Благодарю.