Как найти, существует ли точка, в которой многоугольник

Question

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

polygonA = 1(0,0),2(0,5),3(3,4),4(3,5),5(2,2) 
polygonB = 1(10,10),2(10,15),3(13,14),4(13,15),5(12,12) 

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

Как хранить такие данные (полигон)? есть ли система/база данных/алгоритм для этого поиска?

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

Как искать = Да ... есть список из algorithms и library для того же.

Как хранить = на основе моих исследований SQL и NoSQL db имеют свои решения. NoSQL = MongoDb кажется самым близким, что мне нужно. Но проблема в том, что я могу запросить как «db.places.find ({« loc »: {" $ inside ": {" $ polygon ": polygonB}}})« Но не могу сделать запрос вроде db.places.find ({ loc ": {" $ внутри ": {}}}) SQL проверил postgre и openGIS для некоторой помощи. Но колоду не понять, возможно ли это.

Если кто-то может мне помочь с этим ... Спасибо заранее.

Answer 1

Основной метод (если у вас есть небольшое количество полигонов) - хранить все полигоны в коллекции и петлю над элементами, чтобы проверить, находится ли точка внутри многоугольника.

С другой стороны, если у вас много полигонов, я бы рекомендовал использовать структуру данных R-дерева, которая недоступна в стандартной библиотеке. Вы должны проверить этот проект, если хотите перейти с параметром R-tree: http://sourceforge.net/projects/jsi/.

R-tree позволяет вам индексировать прямоугольники (ограничивающие прямоугольники в этом случае). Таким образом, вы можете найти небольшое количество полигонов-кандидатов очень быстро, используя R-дерево. Затем вы можете перебрать список кандидатов, чтобы получить окончательный результат.

Answer 2

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

GeneralPath gp = new GeneralPath(); 
    double[] x = ... 
    double[] y = ... 
    gp.moveTo(x[0], y[0]); 
    for (int i =1; i < x.length; i++) { 
     gp.lineTo(x[i], y[i]); 
    } 
    gp.closePath(); 

    if (gp.contains(pointX, pointY)) { 
     ... 
    } 

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

Для точного решения, это составляет (без оптимизации) к:.

• принять самое короткое расстояние между точкой и каждой из линий (сегментов), соединяющих вершины каждого из многоугольников (Java2D по-видимому, не дает метода для этого, но кратчайшее расстояние от точки до линии составляет fairly simple calculation)
• , у которого многоугольник имеет линию с кратчайшим расстоянием до точки?

Практически вы можете ориентироваться на этот процесс для некоторых приложений.Например, вы могли бы гораздо эффективнее сделать это:

• занять центральную точку прямоугольника каждого многоугольника (GeneralPath.getBounds() даст вам это)
• считать расстояние между точкой запроса и каждой из этих центральных точек и посмотреть, что ближе всего.

Если вам нужен точный ответ, вы можете объединить эти методы для оптимизации поиска среди всех вершин. Например, вы можете упорядочить полигоны на расстояние до их «центральной точки» (как указано выше). Поиск от минимального до максимального расстояния. Если минимальное расстояние до сегмента, которое вы нашли до сих пор, равно d, вы можете автоматически исключить любой полигон P, где расстояние от точки запроса до его «центральной точки» равно d + r, где r равно половине длины диагональ ограничивающего прямоугольника Р (другими словами, для простоты вы представляете ограничивающий круг вокруг этого ограничивающего прямоугольника и проверяете, что расстояние до этого ограничивающего круга больше, чем ближайшая точка, найденная до сих пор на других полигонах).

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