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

Question

Учитывая два полигона:

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-сервер для создания объединения, но мне нужно выполнить то же самое в коде. Я ищу математическую формулу или пример кода на любом языке, который выставляет фактическую математику. Я пытаюсь создать карты, которые динамически объединяют страны в регионы. Я задал связанный вопрос здесь: Группировка географических фигур

Answer 1

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечания

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

Answer 2

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

<ч />

Answer 3

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

Оболочка Cython для перевода на С ++ библиотеки Клипера Ангуса Джонсона (версия 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)

Answer 8

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

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

Answer 9

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

Answer 10

Это очень старый вопрос, но у меня сработала функция 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;
}