Проверить принадлежность точки к полигоны или "гео-зоны"

Всем привет!
Гугл обгуглил, яндекс обяндексил по полной, а толку…

В общем и целом ищу пример, как можно проверить принадлежность гео-точки lat,lon к полигону, что она внутри него. Нужно просто true/false. Но все примеры что я смог найти какие-то не те в плане результатов + они никак не связаны с нашим миром карт…
Желательно полигон произвольной формы. Я думаю у кого-то в закромах такое есть.
Заранее благодарен, за информацию по теме.

Полигоны то где, в базе или в памяти? Если в базе, то в какой? Есть там георасширения или нет?

Вот есть хорошие примеры.
http://paulbourke.net/geometry/insidepoly/

MySQL (MariaDB), какие-то вроде бы есть.
Зоны в базе, но по идее могут быть выгружены в память пока клиент с нами работает, точка приходит в скрипт, проверяем…

Вот я такую же мега-математику находил, а толку-то от неё? Я не математик, потому для меня это как шифровки СС :slight_smile:

Для точки внутри контура все векторные произведения векторов из точки на пары последовательных точек контура имеют одинаковый знак. Как-то так, или похоже…

нашел такой кусок кода: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html - метод луча в бесконечность

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

to wowik: это верно только для выпуклых многоугольников и частных случаев остальных

А что нужно-то? Алгоритм? Библиотека? Готовое решение?

Алгоритм там постой как гвоздь: строим луч из точки в бесконечность и смотрим сколько отрезков из границы полигона с ним пересекается. Если четное число, то снаружи. Если нечетное, то внутри.

Библиотек полно, те же JTS и GEOS это умеют.

Готовые решения: PostgreSQL + PostGIS.

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

Вот функции у MySQL, проверяющие принадлежность: Within(g1,g2)

Ну там даже примеры на C есть, чего ещё надо? :slight_smile:
Примеры на JavaScript можно в OpenLayers надыбать.
На Java мы JTS юзаем - вполне удобная библиотека с богатыми возможностями.

Ещё важный вопрос проекций. 2D геометрия более-менее работает только на меркаторе и на небольших расстояниях. При работе с градусами и большими расстояниями надо использовать более сложные алгоритмы.

Так вот же пример:


#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
   double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
  int counter = 0;
  int i;
  double xinters;
  Point p1,p2;

  p1 = polygon[0];
  for (i=1;i<=N;i++) {
    p2 = polygon[i % N];
    if (p.y > MIN(p1.y,p2.y)) {
      if (p.y <= MAX(p1.y,p2.y)) {
        if (p.x <= MAX(p1.x,p2.x)) {
          if (p1.y != p2.y) {
            xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
            if (p1.x == p2.x || p.x <= xinters)
              counter++;
          }
        }
      }
    }
    p1 = p2;
  }

  if (counter % 2 == 0)
    return(OUTSIDE);
  else
    return(INSIDE);
}

Проверил, работает вроде как надо.

Попробую базу попытать, может чего получится.

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

То есть надо ограничить площадь полигона? Ну это вполне реально, скажем периметр оного пару км максимум.

Язык какой-то весёлый (для меня), не все слова и значки понимаю :slight_smile: Разберёмся надеюсь.

Спасибо за примеры, будем пробовать!

Вот на js накидал, вроде как работает даже на вогнутых многоугольниках
polygon - L.LatLng[]
point - L.LatLng


function MIN(a,b){return (a<b)?a:b;}
function MAX(a,b){return (a>b)?a:b;}

function isInPoly(polygon,point)
{
	var i=1,N=polygon.length,isIn=false,
		p1=polygon[0],p2;
	
	for(;i<=N;i++)
	{
		p2 = polygon[i % N];
		if (point.lng > MIN(p1.lng,p2.lng)) 
		{
			if (point.lng <= MAX(p1.lng,p2.lng)) 
			{
				if (point.lat <= MAX(p1.lat,p2.lat)) 
				{
					if (p1.lng != p2.lng) 
					{
						xinters = (point.lng-p1.lng)*(p2.lat-p1.lat)/(p2.lng-p1.lng)+p1.lat;
						if (p1.lat == p2.lat || point.lat <= xinters)
							isIn=!isIn;
					}
				}
			}
		}
		p1 = p2;
	}
	return isIn;
}

Хм на js понятней и пригодится, но основная цель это php.
И не очень понял в виде чего polygon на входе, просто массив/объект?

Массив L.LatLng[] (точек leaflet’a)

Для php в интернете упоминается некая библиотека PHP2D, можно её попробовать найти. А вообще - юзайте нормальные языки. :slight_smile: