Алгоритъм за създаване на полигони от затворени области

Имам множество кръгове (като списък от свързани върхове) на произволни позиции.

Когато кръговете се пресичат, се създават затворени области (точно както в диаграма на Вен http://en.wikipedia.org/wiki/Venn_diagram)

Как да генерирам отделни полигони за всички тези области? Целта е да можете да оцветите всеки регион с отделен многоъгълник, както в този пример:

въведете описание на изображението тук

въведете описание на изображението тук

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

РЕДАКТИРАНЕ

Следният прост изрязан е [NodeBox](http://nodebox.net/code/index.php/Home) скрипт, който рисува пресичащи се елипси.

oval(x0,y0,w,h) създава елипса.

Според doc, булевите операции върху пътеки като 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
Добавих малко NodeBox python код, библиотеката позволява булеви операции върху пътища. Моят представител. е твърде ниско, за да включи изображение   -  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