Как мне объединить сложные полигоны?

Даны два полигона:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

Как я могу рассчитать объединение (комбинированный полигон)?

Пример Дейва использует SQL-сервер для создания объединения, но мне нужно сделать то же самое в коде. Я ищу математическую формулу или пример кода на любом языке, который выставляет фактическую математику. Я пытаюсь создать карты, которые динамически объединяют страны в регионы. Я задал связанный вопрос здесь: Группировка географических фигур

Источник

9 ответов

Это очень хороший вопрос. Я реализовал тот же алгоритм на C# некоторое время назад. Алгоритм строит общий контур из двух многоугольников (т.е. строит объединение без дырок). Вот.

Цель

Шаг 1. Создайте график, который описывает полигоны.

Вход: первый многоугольник (n точек), второй многоугольник (m точек). Вывод: график. Вершина - точка многоугольника точки пересечения.

Мы должны найти пересечения. Переберите все стороны многоугольника в обоих многоугольниках [O(n*m)] и найдите любые пересечения.

  • Если пересечение не найдено, просто добавьте вершины и соедините их с ребром.

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

Шаг 2. Проверьте построенный график

Если мы не нашли точек пересечения при построении графа, мы имеем одно из следующих условий:

  1. Polygon1 содержит polygon2 - вернуть полигон1
  2. Polygon2 содержит polygon1 - вернуть полигон2
  3. Полигон1 и полигон2 не пересекаются. Вернуть polygon1 И polygon2.

Шаг 3. Найти левую нижнюю вершину.

Найдите минимальные координаты x и y (minx, miny). Затем найдите минимальное расстояние между (minx, miny) и точками многоугольника. Эта точка будет левой нижней точкой.

Левая нижняя точка

Шаг 4. Построить общий контур.

Мы начинаем проходить график с левой нижней точки и продолжаем, пока не вернемся к нему. В начале мы отмечаем все ребра как непосещенные. На каждой итерации вы должны выбрать следующую точку и отметить ее как посещенную.

Чтобы выбрать следующую точку, выберите ребро с максимальным внутренним углом против часовой стрелки.

Я рассчитываю два вектора: вектор1 для текущего ребра и вектор2 для каждого следующего не посещенного ребра (как показано на рисунке).

Для векторов я рассчитываю:

  1. Скалярное произведение (точечное произведение). Возвращает значение, связанное с углом между векторами.
  2. Векторное произведение (кросс-произведение). Возвращает новый вектор. Если z-координата этого вектора положительна, скалярное произведение дает мне прямой угол в направлении против часовой стрелки. Иначе (z-координата отрицательна), я рассчитываю получить угол между векторами как 360 - угол от скалярного произведения.

В результате я получаю ребро (и соответствующую следующую вершину) с максимальным углом.

Я добавляю в список результатов каждую пройденную вершину. Список результатов - многоугольник объединения.векторы

замечания

  1. Этот алгоритм позволяет нам объединять несколько полигонов - применять итеративно с парами полигонов.
  2. Если у вас есть путь, состоящий из множества кривых и линий Безье, вы должны сначала сгладить этот путь.
Источник

Это сложная, но хорошо понятная тема, которая часто называется "регуляризованные логические операции над полигонами". Вы можете посмотреть на этот ответ MathOverflow, который включает в себя рисунок ниже (из библиотеки отсечения Алана Мурты), с розовым объединением комбайна OP:

BooleanOps

Источник

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

Источник

Попробуйте gpc.

Источник

Хороший вопрос! Я никогда не пытался сделать это раньше, но сейчас попробую.

Первое: вам нужно знать, где эти две фигуры перекрываются. Чтобы сделать это, вы можете посмотреть на каждое ребро в многоугольнике A и увидеть, где оно пересекается, и ребро в многоугольнике B. В этом примере должно быть две точки пересечения.

Затем: сделайте форму соединения. Вы можете взять все вершины в A и B, а также точки пересечения, а затем исключить вершины, содержащиеся в окончательной форме. Чтобы найти эти точки, похоже, вы могли просто найти любую вершину A, которая находится внутри B, и любой вершина B, которая находится внутри A.

Источник

Я столкнулся с той же проблемой, и я решил ее, используя следующий способ

Оболочка Cython для перевода на C++ библиотеки Angus Johnson's Clipper (версия 6.4.2)https://github.com/fonttools/pyclipper

pc = pyclipper.Pyclipper()
def get_poly_union(polygons):
    pc.AddPaths(polygons, pyclipper.PT_SUBJECT, True)
    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO, pyclipper.PFT_NONZERO)
    return solution[0]

print_image = image.copy()
solution = get_poly_union(polygons_array) 
#polygons_array=[polygon,polygon,polygon, ...,polygon] and polygon=[point,point,point...,point]

cv2.drawContours(print_image, [np.asarray(solution)], -1, (0, 255, 0), 2)

plt.imshow(print_image)
Источник

Это очень старый вопрос, но у меня сработала функция Union_ от Boost.

Смотрите этот фрагмент ниже:

#include <iostream>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/foreach.hpp>


int main()
{
    typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

    polygon green, blue;

    boost::geometry::read_wkt(
        "POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))", green);

    boost::geometry::read_wkt(
        "POLYGON((5 5, 5 15, 15 15, 15 5, 5 5))", blue);

    std::vector<polygon> output;
    boost::geometry::union_(green, blue, output);

    int i = 0;
    std::cout << "green || blue:" << std::endl;
    BOOST_FOREACH(polygon const& p, output)
    {
        std::cout << i++ << ": " << boost::geometry::area(p) << std::endl;

        for (int i = 0; i < p.outer().size(); i++)
        {
            std::cout << p.outer().at(i).x() << " " << p.outer().at(i).y() << std::endl;
        }
    }



    return 0;
}
Источник

Решение, которое я видел, используя деревья BSP, описано здесь.

По сути, он описывает пересечение в терминах объединения ребер многоугольника A, которые находятся внутри многоугольника B (включая частичные ребра, и рассчитывается с использованием дерева BSP). Затем вы можете определить A / B как ~ (~A /\ ~B), где ~ обозначает реверсирование намотки многоугольника, / обозначает объединение и /\ обозначает пересечение.

Источник

Мне нужно было решить эту проблему сегодня и найти решение с помощью этой библиотеки: http://www.cs.man.ac.uk/~toby/alan/software/.

Здесь есть много языковых реализаций, включая Java, Obj-C, C#, Lua, python и другие.

Источник

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

Источник
Другие вопросы по тегам