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

Константин_Гам · 2012-06-01T06:08:30.000Z

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

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

Sergey_Astakhov · 2012-06-01T06:41:50.000Z

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

PaulKaz · 2012-06-01T06:46:35.000Z

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

Константин_Гам · 2012-06-01T06:56:34.000Z

Sergey Astakhov:

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

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

Константин_Гам · 2012-06-01T06:58:16.000Z

PaulKaz:

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

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

wowik · 2012-06-01T06:58:50.000Z

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

Larry0ua · 2012-06-01T07:09:44.000Z

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

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

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

Miroff · 2012-06-01T07:12:17.000Z

GaM:

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

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

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

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

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

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

Sergey_Astakhov · 2012-06-01T07:15:05.000Z

GaM:

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

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

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

GaM:

PaulKaz:

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

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

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

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

PaulKaz · 2012-06-01T07:26:39.000Z

GaM:

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

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


#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);
}

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

Константин_Гам · 2012-06-01T07:27:37.000Z

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

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

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

Константин_Гам · 2012-06-01T07:30:34.000Z

PaulKaz:

GaM:

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

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


#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);
}

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

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

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

PaulKaz · 2012-06-01T08:11:07.000Z

Вот на 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;
}

Константин_Гам · 2012-06-01T08:31:07.000Z

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

PaulKaz · 2012-06-01T08:43:27.000Z

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

Sergey_Astakhov · 2012-06-01T09:08:17.000Z

GaM:

Хм на js понятней и пригодится, но основная цель это php.

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