Получите, если координата находится внутри полилинии

Question

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

Например, в этом образе:

polywantcracker http://f.cl.ly/items/461O0V050S2p3Z3J2J1R/Image%202013.04.01%2009:20:57.png

Как я могу знать, если 40.744818, -73,989701 (на примере), внутри или нет?

Лучшее, если в PHP: P

Спасибо!

Answer 1

Этот вопрос уже решен (с JavaScript), пожалуйста, прочитайте: https://gis.stackexchange.com/questions/26225/solving-the-point-in-polygon-problem-using-google-maps-and-fusion-tables

А вот matemathical описание: http://en.wikipedia.org/wiki/Point_in_polygon, здесь есть несколько различных алгоритмов, что вы можете использовать. Я рекомендую вам Ray casting algorithm (RCA) отсюда: http://rosettacode.org/wiki/Ray-casting_algorithm

Существует псевдо-код, что вы могли бы реализовать в PHP;)

Для решения математических задач, рекомендуем посетить этот проект: http://www.phpmath.com/home И надеюсь, что ты может найти реализованное решение php для вашей проблемы;)

И если вам нужно больше производительности, вы можете посмотреть после collusion detection в 2D. Первый шаг: создать внешний прямоугольник вокруг вашего многоугольника, см. Пункт insde в прямоугольнике. Если внутри, у вас есть шанс, что ваша точка находится внутри поля, а затем запустите Ray Casting Algorithm. См.:

$px //the x coordinate of your point 
$py //the y coordinate of your point 
$ppy //the y coordinates of points of your polygon (in the correct order) 
$ppx //the x coordinates of points of your polygon (in the correct order) 

$isInside = 
    (max($ppy)>$py && min($ppy)<$px && max($ppx)>$px && min($ppy)<$px)? 
    RCA($px,$py,$ppx,$ppy): 
    false;  
} 

/** 
* @description decide, is a point in poligon 
* @param float $px the x coordinate of your point 
* @param float $py the y coordinate of your point 
* @param array(float) $ppx the x coordinates of the points of polygon 
*    array(x1,x2,...) 
* @param array(float) $ppy the y coordinates of the points of polygon 
*    array(y1,y2,...) 
*    points of polygon: [x1,y1],[x2,y2],... 
* @return boolean : Is the point inside the polygon? 
*/ 
function RCA($px,$py,array $ppx,array $ppy){ 
     //the implementation 
} 

(Если в вашем использовании, есть много координат кнаружи от внешнего прямоугольника, этот код работать быстрее 2-max, 2 min, 2 < и 2 > условия тестирования более быстрее, чем RCA, и если точка находится вне прямоугольника, нет необходимости запускать RCA)

(решение ниже не объект ориентирован. Если вы используете OOP решение может быть приятнее :))

ссылка помощь, где является воплощением tation in php: http://assemblysys.com/php-point-in-polygon-algorithm/ (не совсем то, что я написал, но должен работать)