Пересечение, объединение и разность многоугольников

Цитата Nymph666 @ 14.01.08, 04:46

то есть ты хочешь сказать, что он работает и для вогнутых?

ага

Цитата Nymph666 @ 14.01.08, 04:46

что именно для одного многоугольника дерево ДОЛЖНО вырождаться в линейный список

Нет. Когда мы строим дерево для выпуклого многоугольника, то какой бы мы ни взяли сплиттер (грань этого многоугольника), весь многоугольник лежит в отрицательной полуплосткости оносительно прямой, проведенной через этот сплиттер, вот и получаем, что за каждый шаг построения дерева мы откусываем от границы многоугольника по одной грани в качестве сплиттера, а остальное выкидиваем в отрицательное поддерево. Получается линейный список.
Для вогнутых это не так: изначально в качестве сплиттера мы можем выбрать такую грань, что прямая, проходящая через нее, рассечет наш многоугольник на две части, т.е. сразу получится дерево. Хотя для некоторых невыпуклых многоугольников существует такой порядок выбора сплиттеров, что дерево все равно остается линейным списком (хотя и с меняющимся знаком), но этот случай нам не интересен, т.к. никакой выгоды отсюда мы извлечь не можем. Если интересно, то алгоритм выбора сплиттеров такой: строим выпуклую оболочку для многоугольника, потом в качестве сплиттеров выбираем те грани, которые вошли в выпуклую оболочку (легко привести пример токого многоугольника, что ни одна его грань в выпуклую оболочку не войдет), запоминаем смену знака и повторяем итерацию, и так пока либо не кончатся грани (последовательность найдена), либо не перестанет менятся выпуклая оболочка (требуемой последовательности сплиттеров не существует).Вообще, к "линейности" bsp-дерева стремится не нужно, получилось линейным, ни и ладно...

Цитата Nymph666 @ 14.01.08, 04:46

То есть ты хочешь сказать, что когда мы разбиваем этим деревом другой многоугольник все будет правильно работать?

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

Можешь написать сюда свой вариант построения дерева (на псевдокоде, либо на конкретном языке)? Если где-то просто непонимание алгоритма, то попробую объяснить это по-лучше.

Цитата albom @ 14.01.08, 05:23

Цитата

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

.

Вот я так и понимала алгоритм. То есть при каждой "итерации" мы откусываем область, которая не входит в многоугольник...А при вогнутом так не получается. То есть какие-либо ребра могут оказаться в positive.

 void splitSegments(const BSPNode* tree, const Segments &segments, Segments &p, Segments &n)
{
    Segments pList, nList;
    for (size_t i = 0; i < segments.size(); i++)
    {
        const Segment& cur = segments[i]; // берем  каждый отрезок
        Segment p, n;
        bool    pp, nn;
        split(cur, tree->splitter, p, n, pp, nn);  // делим его сплиттером
        if (pp)
            pList.push_back(p);
        if (nn)
            nList.push_back(n);
    }
    if ( tree->positive != NULL )
        splitSegments(tree->positive, pList, p, n); // делим P список рекурсивно
    else
        p.insert(p.end(), pList.begin(), pList.end()); // дерево кончилось => все что попалов в P список лежит
вне многоугольника
 
    if ( tree->negative != NULL )
        splitSegments(tree->negative, nList, p, n);
    else
        n.insert(n.end(), nList.begin(), nList.end());

- Вот в этой функции получается, что: Мы берем отрезки многоугольника и делим их "первым" сплиттером:

   for (size_t i = 0; i < segments.size(); i++)
    {
        const Segment& cur = segments[i]; // берем  каждый отрезок
        Segment p, n;
        bool    pp, nn;
        split(cur, tree->splitter, p, n, pp, nn);  // делим его сплиттером
        if (pp)
            pList.push_back(p);
        if (nn)
            nList.push_back(n);
    }

Затем сплиттером в положительной ветке делим то, что попало в PList. А то есть этот PList делится на положительную и отрицательную часть. Не понимаю:

 n.insert(n.end(), nList.begin(), nList.end());

То есть что в итоге попадает в n? То есть функция поделит все отрезки на те, которые входят в полигон и на те, которые не входят?

Сообщение отредактировано: Nymph666 - 14.01.08, 07:13

Вот, нарисовал пример, давай смотреть.

• На первой картинке изображен наш невыпуклый четырехугольник ABCD (порядок обхода важен).
• На второй изображено то что мы хотим получить. А хотим мы получить возможность разделить пространство на две области: положительную (зеленая, вне многоугольника) и отрицательную (красная, внутри соответственно).
  Ну кроме этого мы еще хотим уметь разделять контур другого многоугольника на две части, такие что каждая часть лежит целиком в области одного цвета, но это сейчас не главное.
  
  
• Итак, начинаем строить bsp-дерево и переходим к картинке #3.
  Выбрали в качестве сплиттера ребро AB, построили прямую (синяя такая), и разделили остальные ребра на два множества: N_1={BC, CD, DA} и P_1={} (пусть индекс _1 служит для нумерации множеств на разных этапах рекурсии).
  Множество P_1 оказалось пустым, и рекурсивный вызов процедуры buildTree сразу же возвратил nil, ну мы и сохранили результат.
  Заметим, что теперь синяя прямая AB отделила от нашей плостости некую область 1, которая целиком лежит вне многоугольника!!
  Таким образом, если некий объект лежит ниже AB, то про него мы можем однозначно сказать, что он вне многоугольника.
  Теперь работает рекурсивный вызов для N_1. Тут все сложнее, и поэтому мы переходим к картинке #4.
• Сплиттер BC (что поделаешь, мы берем первое ребро в попядке обхода).
  Так вот, сплиттер рассек ребро DA на два: DE и EA. Опять строим два множества N_2={EA} и P_2={CD, DE}.
  Больше тут ничего интересного, и мы делаем рекурсивный вызов для P_2.
  
  Небольшое отступление. Сплиттеры показаны синим цветом, предыдущие сплиттеры - бледно-голубым. Кроме того, важно что не все сплиттеры прямые, не в том смысле что кривые, а в том что есть еще и лучи, и отрезки.
  
• Картинка #5.
  Сплиттер CD. N_3={DE}, P_3={}.
  Вот, теперь вызов рекурсии для P_3 вернет nil и мы откусили от плосткости еще одну область 2.
• Картинка #6. Рекурсивный вызов для N_3.
  Сплиттер DE. N_4={}, P_4={}.
  Вызвали рекурсию для P_4 - получили область 3.
• Картинка #6. Рекурсивный вызов для N_4.
  Множество N_4 пусто => получили область 4.
• Картинка #7. Рекурсивный вызов для N_2.
  Сплиттер EA. N_5={}, P_5={}.
  Вызов для P_5 дал область 5.
• Картинка #8. Рекурсивный вызов для N_5.
  Пусто, все. Вернули область 6.
• Дальше идут возвраты из рекурсии, но картинки там не интересные.

Итак, мы построили дерево. Вспоминаем исходную задачу. Смотрим на рисунок... Ага, внутренность многоугольника это области 4 и 6. Внешность - 1, 2, 3, 5.
Теперь смотрим на дерево... Вот оно! Области 1, 2, 3, 5 - это левые листья в дереве (на самом деле в программе там нет никаких листьев, т.к. хранить в них особенно нечего, а поэтому там просто nil), а области 4 и 6 - правые.

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

Вместо точки, можно так же спустить по дереву отрезок, деля его на два, если он вдруг пересек сплиттер.
Вот в этой процедуре

 void splitSegments(const BSPNode* tree, const Segments &segments, Segments &p, Segments &n);

множество n - это множество отрезков, законцивших свой спуск в правом листе, а отрезки из p соответственно спускаются в левые листья.

Собственно, строка

 n.insert(n.end(), nList.begin(), nList.end());

и делает это запоминание, ведь она выполняется когда мы дошли до правого листа.

Остальное вроде просто: спускаем контур по дереву, и из его половинок конструируем новые многоугольники.

Цитата Nymph666

То есть функция поделит все отрезки на те, которые входят в полигон и на те, которые не входят?

точно

Сообщение отредактировано: albom - 14.01.08, 10:03

Прикреплённая картинка

Спасибо, вроде разобралась. Единственное, а обязательно нужно разбивать DA на DE и EA? У меня в алгоритме проверяется только пересечение отрезков: если пересечение то одну половину в p, другую - в n. Да, я даже замечала, что иногда когда мы определяем для точек отрезка куда они относятся - одна лежит в p, а другая - в n. Получается это неправильно и нужно искать пересечение отрезка с прямой? Как это сделать с двумя отрезками(как и с двумя прямыми) понятно, а когда отрезок и прямая?
С построением собственно результирующих многоугольников идеи в принципе есть: раз у нас есть результирующие ребра, то их не так уж сложно упорядочить и получить окончательный результат...
ток не поняла что значит

Цитата

спускаем контур по дереву

?

Цитата Nymph666 @ 15.01.08, 06:28

а обязательно нужно разбивать DA на DE и EA?

Да, обязательно. В bsp-дереве мы не можем допустить, что бы какая-либо сущность пересекала прямую сплиттера, иначе оно просто не будет работать.

Цитата Nymph666 @ 15.01.08, 06:28

Получается это неправильно и нужно искать пересечение отрезка с прямой?

Да, отрезок нашей геометрии нужно пересекать с прямой, содержащей сплиттер (а вот он уже отрезок).

Цитата Nymph666 @ 15.01.08, 06:28

а когда отрезок и прямая?

Простой вариант с параметаризацией.
Пусть у нас заданы две точки A и B - начало и конец отрезка, и две произвольные точки C, D на прямой.
Тогда решаем систему:
A * (1 - t1) + B * t1 = C * (1 - t2) + D * t2
(относительное t1 и t2)

Находим X = A * (1 - t1) + B * t1 - точку пересечения прямых AB и CD.
Теперь, если 0 < t1 < 1, то есть пересечение отрезка с прямой (и он делится на два: AX и XB), иначе отрезок прямую не пересекат (т.е. целиком лежит в одной из полуплоскостей).

Цитата Nymph666 @ 15.01.08, 06:28

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

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

Цитата Nymph666 @ 15.01.08, 06:28

ток не поняла что значит

Цитата

спускаем контур по дереву

Разделяем границу многоугольника A на два множества: A+ и A-.

Уря, заработало Функция разбиения одного полигона относительно другого...

Для двух многоугольников вродь теперь работает:-) Осталось упорядочить и посчитать площадь...
Но у меня даны несколько многоугольников... Причем результат ведь может получиться многосвязным и с дырками. Предполагаю, что потом надо брать каждый из многоугольников, попавших в результат и применять выбранную операцию для каждого. Но вот что делать с дырками? Может обходить их по часовой стрелке?
Также возникает вопрос как определять: данный многоугольник - многоугольник или дырка? Проверять на принадлежность другим многоугольникам? В принципе можно проверить одну точку. Но и тогда получается квадратичная сложность от количества многоугольников, которые попали в результат...

Цитата Nymph666 @ 16.01.08, 04:09

Осталось упорядочить и посчитать площадь...

Для подсчета площади не нужно ничего упорядочивать. Достаточно подсчитать сумму оринтированных площадей, натянутых на ребра полученного многоугольника.
Т.е. фиксируем произвольную точку A. В цикле пробегаемся по всем ребрам. У каждого ребра есть начало (S) и конец (E), считаем векторное произведение V = AS * AE. Накапливаем его S = S + V. Тогда после цикла |S/2| есть искомая площадь с учетом всех дырок, итп.

Цитата Nymph666 @ 16.01.08, 04:09

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

Вы имеете ввиду, что после если нужно найти, например, R = A - (B - C), то сначала вы найдете (B-C), потом, если результат будет многосвызным, разобъете его на простые многоугольники и по очереди вычтите их из A?
Это неверный подход.
Для данного алгоритма не составляют проблему ни многосвязность, ни дырки. Просто ничего не нужно делать.

Цитата Nymph666 @ 16.01.08, 04:09

Но вот что делать с дырками? Может обходить их по часовой стрелке?

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

Цитата Nymph666 @ 16.01.08, 04:09

данный многоугольник - многоугольник или дырка?

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

Цитата Nymph666 @ 16.01.08, 04:09

данный многоугольник - многоугольник или дырка? Проверять на принадлежность другим многоугольникам?

Плохая идея. Во-первых, нужно считать всякие уровни вложенности. А во-вторых, если захотите к операциям AND, OR, MINUS добавить еще и NOT (дополнение), и построить замкнутую алгебру над многоугольниками, то такой метод не будет работать.

Цитата Nymph666 @ 16.01.08, 04:09

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

Направленная площадь. Сложность проверки контура линейно зависит от его длины.

Вот только в этом случае нужно уметь быстро собирать множество отрезков результата в простые контура.
Неплохая, по-моему, реализация это сбалансированное бинарное дерево, ключ (составной) - координаты начала отрезка. Сложность сбора O(N*logN).

В принципе, можно считать, что вершины многоугольников "хорошо" распределены и избавится от сбалансированности, а использовать Quadtree. Макс. сложность будет O(N^2), но в среднем можно ожидать O(N*logN).

Цитата

Для подсчета площади не нужно ничего упорядочивать.

Я для подсчета площади(исходных многоугольников) тоже использовала ориентированную площадь. Ток там формула была иная S = S + ((X1*Y2)-(Y1*X2)), где X1,Y1 -первая вершина ребра X2,Y2 - вторая вершина. А про твою формулу слышу впервые...То есть ты хочешь сказать, что мы берем массив получившихся ребер, произвольную точку и считаем площадь?


Ориентированная площадь непосредственно связана с направлением обхода многоугольника. Я хотела искать дырки, скажем, для изменения направления их обхода(если они против часовой), ну и может для подсчета площади. Но если учитывать написанную тобой формулу и то, что

Цитата

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

получается после сборки мы уже получим дырки с правильным направлением обхода?

То есть: После того как мы получили кучу отрезков входящих в результат, нужно их собрать в простые контура. Все больше ничего не делаем берем список контуров и рассматриваем их как один многоугольник и опять строим BSP и т.д. Я правильно поняла?

Цитата

Неплохая, по-моему, реализация это сбалансированное бинарное дерево, ключ (составной) - координаты начала отрезка. Сложность сбора O(N*logN).

В принципе, можно считать, что вершины многоугольников "хорошо" распределены и избавится от сбалансированности, а использовать Quadtree. Макс. сложность будет O(N^2), но в среднем можно ожидать O(N*logN).

А можно поподробнее про эти методы?;-)

Сообщение отредактировано: Nymph666 - 17.01.08, 04:42

Цитата Nymph666 @ 17.01.08, 04:33

Ток там формула была иная S = S + ((X1*Y2)-(Y1*X2))

Та же самая, просто A=0.

Цитата Nymph666 @ 17.01.08, 04:33

То есть ты хочешь сказать, что мы берем массив получившихся ребер, произвольную точку и считаем площадь?

Да, все равно от порядка сложения результат не зависит.

Цитата Nymph666 @ 17.01.08, 04:33

получается после сборки мы уже получим дырки с правильным направлением обхода?

Направление обхода будет правильным, если правильно делать операции, например, когда берем разность A-B, то результат есть объединение A+ и B-, но в B- нужно поменять направление обхода.

Цитата Nymph666 @ 17.01.08, 04:33

После того как мы получили кучу отрезков входящих в результат, нужно их собрать в простые контура. Все больше ничего не делаем берем список контуров и рассматриваем их как один многоугольник и опять строим BSP и т.д. Я правильно поняла?

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

Цитата Nymph666 @ 17.01.08, 04:33

А можно поподробнее про эти методы?

Строишь Quadtree для всех отрезков границы. Тогда контуры собираются так: выбираем из Γ (граница) какой-нибудь элемент A, добавляем его в S (текущий простой контур). Теперь делаем запрос в квадродерево с ключем A.end, если оно вернет некий отрезок B, то A=B и повторяем, иначе S - контур, выводим его, и повторяем с самого начала. Естественно, следим что бы каждый отрезок обрабатывался только один раз.

Цитата

Выделять простые контура нужно только если их планируется использовать где-то еще.

Использовать для последующего построения пересечения, объединения и разности с другим многоугольником (третьим, четвертым, ...)
Получается ничего не нужно упорядочивать, просто продолжаем строить BSP дерево и делить новый многоугольник этими ребрами?

Цитата

Направление обхода будет правильным, если правильно делать операции, например, когда берем разность A-B, то результат есть объединение A+ и B-, но в B- нужно поменять направление обхода.

Для пересечения,объединения нужно менять направление обхода?

Цитата Nymph666 @ 17.01.08, 12:03

Получается ничего не нужно упорядочивать, просто продолжаем строить BSP дерево и делить новый многоугольник этими ребрами?

Да.
Правда может возникнуть проблема с увеличением кол-ва ребер, которые при деление были поделены на два, но обе половинки вошли в ответ.
Тут два варианта, либо периодически их нужно объединять в одно ребро. Либо сохранять в узле bsp-дерева все такие ребра (т.е. делим ребра не на два класса, а на три: лежащие с одной стороны сплиттера, с другой, и на самом сплиттере).

Цитата Nymph666 @ 17.01.08, 12:03

Для пересечения,объединения нужно менять направление обхода?

Нет

Цитата

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

Да, замечала, есть такое дело
Если объединять, то просматриваем все отрезки, вошедшие в результат и если начало_второго(CD)=конец_первого(AB) и смотрим принадлежит ли другая точка, скажем второго отрезка(то есть точка D) первому отрезку АВ(ну в смысле прямой им образованной). Принадлежность проверяется подстановкой координат точки в уравнение(в то, которое мы уже использовали когда строили BSP)и если оно равно нулю, то следовательно D принадлежит AB. Объединяем AB и CD.
Я правильно думаю? Или как-то по-другому можно?

Иногда сохраняют с отрезком информацию, что если вместе с ним в результат вошел другой отрезок (у всех отрезков есть некий уникальный идентификатор), то их нужно заменить на другой отрезок.
Хотя в двумерном случае можно оставить все так.

Здравствуй, albom! Программу написала, тока она периодически не правильно работает при некоторых данных для двух многоугольников, а для нескольких все еще хуже,- редко работает правильно(((
Причем проверяла работу алгоритма вроде как все работает "правильно"(по алгоритму).
Например, вот здесь.
На рисунке:

Здесь два полигона(один из них -пятиугольник ABLNM): 0 и 1 - это начальные точки полигонов. Ищем объединение. Обходим против часовой стрелки.
Сначала естественно строим BSP-деревья. Вроде все правильно.
Затем спускаем отрезки первого полигона...
В общем, сразу к ошибке(неправильно отсортирован отрезок CH):
Сначала первым ребром нулевого многоугольника мы разбиваем отрезок AB на два: AC(positive) и CB(negative).
Отрезок AC рассматривать не будем, так как он сортируется правильно.
Смотрим что у нас в дереве:
splitter165 189 88 285//сплиттер
pList rebro 220,34375 120 270 120
pList rebro 270 120 178,922789048651 171,641717549734
pList rebro 173 175 288 220
pList rebro 288 220 271 267
pList rebro 271 267 224 237
pList rebro 224 237 217 299
pList rebro 217 299 165 189
nList rebro 88 285 150 120(EG)
nList rebro 150 120 220,34375 120(RU)
nList rebro 178,922789048651 171,641717549734 173 175(UK)
То есть на следующем шаге мы делим ребро CB относительно сплиттера 88 285 150 120(EG). Оно делится на два отрезка: CD(negative) и DB(positive).
DB также не будем трогать в силу правильной сортировки.
Теперь CD делим относительно сплиттера 150 120 220,34375 120(RU)(он тоже попадает в nList)
Он весь попадает в negative.
Ну и последний сплиттер178,922789048651 171,641717549734 173 175(UK)(он тоже попадает в nList):
он делит CD на CH(positive) и HD(negative).
И в итоге получается, что CH находится в Plus ну и соответственно входит в объединение, что неправильно!(((
Почему такое получается?
Может я опять что-то не так делаю?*CRY*