Определение вхождения адреса (координат) в полигоне?

Question

[vitovt]

Привет, уважаемому сообществу!


Собственно возникла потребность решить простую задачу, но решение не идет в голову.


Итак, есть каталог интернет-магазинов, каждый из которых может создать свою зону доставки при помощи Яндекс. Карт. Администратор создает «полигоны», координаты которых хранятся в базе. (Кстати, пока хранятся в одном поле coords но полагаю, что придется каждую координату LAT, LNG хранить в отдельных полях)


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


Поиск выдал приблезительные решения, вроде этого habrahabr.ru/post/127446/ но не совсем то. Необходимо на php и mysql определить в какие полигоны входят нужные координаты адреса. Может быт кто-то натолкнет на мысль?

Answer 1

[Tomarev]

Вы можете попробовать этот простой класс https://github.com/xopbatgh/sb-polygon-pointer

Эта мини библиотека очень мне помогла.

$polygonBox = [
    [55.761515, 37.600375],
    [55.759428, 37.651156],
    [55.737112, 37.649566],
    [55.737649, 37.597301],
];

$sbPolygonEngine = new sbPolygonEngine($polygonBox);

$isCrosses = $sbPolygonEngine->isCrossesWith(55.746768, 37.625605);

// $isCrosses is boolean

Answer 2

[vitovt]

Сам задал вопрос, сам похоже нашел ответ ) можно гуглить в сторону Spatial Extensions

Answer 3

[cat_crash]

Есть библиотека GEOS которую можно собрать как расширение php. В мануалах думаю разберетесь.

Answer 4

[Dolios]

Может быт кто-то натолкнет на мысль?

Задача принадлежности точки полигону решается, например, алгоритмом трасссировки луча.
А вообще вот:
Задача о принадлежности точки многоугольнику

Если я правильно понял, чего вы хотите

Answer 5

[Urvin]

В mySQL есть географические типы, есть соответствующие функции для работы с ними.
Однако, эти функции совершают ошибки и мне пришлось делать решение на PHP.

Это SQL

/**
 * Calculates whether Point is in Polygon or not. Uses mySql
 * @param array $aPoint
 * @param array $aCityBounds
 * @return boolean
 */
protected function isPointInCity(array $aPoint,array &$aCityBounds)
{
	$lPointGeomText = 'Point(' . $aPoint[0] . ' ' . $aPoint[1] . ')';
	$lPolyGeomText = '';
	foreach($aCityBounds as &$lBoundPoint)
		$lPolyGeomText .= (empty($lPolyGeomText) ? '' : ',') . $lBoundPoint[0] . ' ' . $lBoundPoint[1];
	// include first point to finish polygon
	$lPolyGeomText = 'Polygon((' . $lPolyGeomText . ',' . $aCityBounds[0][0] . ' ' . $aCityBounds[0][1] . '))';
	$lQuery = "SELECT MBRIntersects(GeomFromText('" . $lPolyGeomText . "'),GeomFromText('" . $lPointGeomText . "'))";
	
	return intval(DbWrapper::dbGetValue($lQuery)) > 0 ? true : false;
}

Это — без:

protected function isPointInCityBoundingBox(array $aPoint, array &$aCityBoundBox)
{
	return $aPoint[0] >= $aCityBoundBox['minx'] && $aPoint[0] <= $aCityBoundBox['maxx'] &&
		   $aPoint[1] >= $aCityBoundBox['miny'] && $aPoint[1] <= $aCityBoundBox['maxy'];
}

/**
 * Calculate if point is inside polygon, more precisely than mySql now
 * @param array $aPoint
 * @param array $aCityBounds
 * @param array $aCityBoundBox
 * @return boolean
 */
protected function isPointInCityNoSql(array $aPoint, array &$aCityBounds, array &$aCityBoundBox)
{
	if(!$this->isPointInCityBoundingBox($aPoint, $aCityBoundBox))
		return false;
	
	$pj = 0;
	$pk = 0;
	$wrkx = 0;
	$yu = 0;
	$yl = 0;
	$lPointsCount = count($aCityBounds);
	for($pj = 0; $pj < $lPointsCount; $pj++)
	{
		$yu = $aCityBounds[$pj][1] > $aCityBounds[($pj + 1) % $lPointsCount][1] ? $aCityBounds[$pj][1] : $aCityBounds[($pj + 1) % $lPointsCount][1];
		$yl = $aCityBounds[$pj][1] < $aCityBounds[($pj + 1) % $lPointsCount][1] ? $aCityBounds[$pj][1] : $aCityBounds[($pj + 1) % $lPointsCount][1];
		if($aCityBounds[($pj + 1) % $lPointsCount][1] - $aCityBounds[$pj][1])
			$wrkx = $aCityBounds[$pj][0] + ($aCityBounds[($pj + 1) % $lPointsCount][0] - $aCityBounds[$pj][0]) * ($aPoint[1] - $aCityBounds[$pj][1]) / ($aCityBounds[($pj + 1) % $lPointsCount][1] - $aCityBounds[$pj][1]);
		else
			$wrkx = $aCityBounds[$pj][0];
		if($yu >= $aPoint[1])
			if($yl < $aPoint[1])
			{
				if($aPoint[0] > $wrkx)
					$pk++;
				if(abs($aPoint[0] - $wrkx) < 0.00001)
					return true;
			}
		if((abs($aPoint[1] - $yl) < 0.00001) && (abs($yu - $yl) < 0.00001) && (abs(abs($wrkx - $aCityBounds[$pj][0]) + abs($wrkx - $aCityBounds[($pj + 1) % $lPointsCount][0]) - abs($aCityBounds[$pj][0] - $aCityBounds[($pj + 1) % $lPointsCount][0])) < 0.0001))
			return true;
	}

	return ($pk % 2) ? true : false;
}

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

Answer 6

[Антон Пронин]

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