Алгоритм создания полигонов замкнутых областей

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

Когда окружности пересекаются, создаются замкнутые области (как на диаграмме Венна http://en.wikipedia.org/wiki/Venn_diagram)

Как создать отдельные полигоны всех этих областей? Цель состоит в том, чтобы иметь возможность раскрасить каждую область отдельным полигоном, как в этом примере:

введите здесь описание изображения

введите здесь описание изображения

Возможно ли общее решение с итеративными булевыми операциями пересечения?

ИЗМЕНИТЬ

Следующий простой фрагмент представляет собой скрипт [NodeBox](http://nodebox.net/code/index.php/Home), рисующий пересекающиеся эллипсы.

oval(x0,y0,w,h) создает эллипс.

Согласно документу, логические операции над путями, такими как p[19].difference(p[17]), дадут "плоский" результат. («состоит из многочисленных отрезков прямой линии»).

Координаты пути могут быть добавлены или изменены.

size(500, 500)

p = []
s = 54
nofill()
stroke(0)
for k in xrange(10):
    w  = 10+k*s/2
    w2 = 10+k*s 
    h = 10+k*s
    h2= 10+k*s
    p.append( oval(WIDTH/2 - w/2, HEIGHT/2 - h/2, w,  h, draw=False))
    p.append( oval(WIDTH/2 - w2/2, HEIGHT/2 - h2/2, w2, h2, draw=False))


cp = p[19].difference(p[17]).intersect(p[18], flatness = 0.3)

for pi in p:
    drawpath(pi)

fill(color(1,0,0))
drawpath(cp)

algorithm geometry polygon language-agnostic nodebox
person synchro    schedule 21.12.2013    source источник
comment
Какие структуры информации/данных у вас есть на входе? Покажите нам, что вы уже сделали для этого.   -  person RBarryYoung    schedule 21.12.2013
comment
Я добавил некоторый код Python NodeBox, библиотека позволяет логические операции с путями. Мой представитель слишком мало, чтобы включить изображение   -  person synchro    schedule 21.12.2013
comment
Добавьте ссылку на свое изображение в вопросе, и мы можем добавить его для вас.   -  person RBarryYoung    schedule 21.12.2013

Ответы (1)


arrow_upward
3
arrow_downward

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

Let p = P
for each polygon f in F
  Replace f by f-p and intersect(f, p).
  Set p = p-f
end
add p to F

Идея состоит в том, чтобы использовать новый многоугольник p для разделения существующих «плоских» многоугольников в F на части, общие с p и не общие с p, затем удалить это перекрытие с исходным многоугольником из самого p и продолжить. Когда вы это сделаете, от p останется та часть, которая не пересекалась ни с чем в F, поэтому мы добавляем ее как новый многоугольник к F.

Таким образом, чтобы обработать случайный набор круглых многоугольников, вы начинаете с F, содержащего один из них (который, безусловно, является плоским набором!) и добавляете больше, по одному, пока не закончите.

На практике это невероятно менее эффективно, чем пользовательский алгоритм. Стандартным способом решения подобных проблем является метод прокрутки. Представьте себе вертикальную линию, проходящую слева направо по кругам. Когда он «касается» круга, он начинает строить многоугольник. При касании пересечения один полигон закрывается, два продолжаются и открывается новый (в общем случае). Когда он достигает самой правой точки окружности, соответствующий многоугольник закрывается. «Замкнутый» полигон удаляется из линии развертки и добавляется в выходной список. Алгоритмы развертки концептуально не сложны, но их реализация сложна из-за большого количества особых случаев (особенно для линий, параллельных щетке, и когда вершина одного многоугольника лежит на краю другого, хотя общий метод для работы с ними - симуляция простоты).

«Обобщенное расположение» — это термин вычислительной геометрии, используемый для описания подобных задач. Обобщенная компоновка — это набор линий, сегментов и/или многоугольников (нормальная компоновка — это просто наборы линий). Например, библиотека CGAL для обобщенных расположений может решить именно вашу проблему с высокая эффективность. CGAL — это большая общая библиотека на C++, поэтому есть некоторые затраты на обучение. Лицензирование для коммерческих целей является сложной задачей.

person Gene    schedule 21.12.2013