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

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) теперь хочу искать, находится ли эта точка в каком-либо из этого многоугольника или в обоих или ближайшем к какому многоугольнику.

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

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

Как искать = Да... получил список алгоритмов и библиотеку для того же.

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

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

Answer 1

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

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

R-дерево позволяет индексировать прямоугольники (в данном случае ограничивающие прямоугольники многоугольников). Таким образом, вы можете очень быстро найти небольшое количество возможных полигонов, используя 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, по-видимому, не предоставляет метод для этого, но кратчайшее расстояние от точки до линии является довольно простым вычислением)
• какой полигон имеет линию с кратчайшим расстоянием до точки?

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

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

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

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