Вычислить объединение двух произвольных фигур

Я работаю над приложением, мне нужно иметь возможность комбинировать две перекрывающиеся произвольные формы, нарисованные пользователем. Это будет операция объединения двух фигур. Результирующая форма будет силуэтом двух перекрывающихся фигур.

Фигуры сохраняются как последовательность точек по часовой стрелке.

В идеале мне нужен алгоритм, который будет принимать два массива точек (x, y) и возвращать один массив результирующей формы.

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

Я разрабатываю приложение на ActionScript 3, но я знаком с C #, Java и могу выбрать свой путь через C и C ++.


math geometry boolean-operations
person Greg B    schedule 26.01.2010    source источник

Ответы (6)


arrow_upward
5
arrow_downward

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

На каком языке ты говоришь? Если это C ++, взгляните на CGAL, библиотеку алгоритмов вычислительной геометрии.

person Martin B    schedule 26.01.2010
comment
Спасибо, реализую в AS3, но знаком с C #, Java - person Greg B; 26.01.2010
comment
Ах ... ну, я не уверен, так ли интересно разбирать и переносить исходный код CGAL, поскольку он выражает свои алгоритмы довольно общим образом, смоделированный по образцу STL (IIRC, это было давно). Возможно, вам будет лучше перенести одну из более конкретных библиотек, ссылки на которые указаны в нижней части страницы Википедии. В качестве альтернативы, можете ли вы обойтись простым рендерингом обоих полигонов в растровое изображение и последующим выполнением над ним логических операций? - person Martin B; 26.01.2010
comment
Я нашел этот (частичный) порт AS3 порта Java GPC code.google.com/p/gpcas, который поддерживает операции UNION. Спасибо за ваш вклад. - person Greg B; 26.01.2010
comment
Хорошая находка - похоже, это именно то, что вам нужно! - person Martin B; 26.01.2010

arrow_upward
3
arrow_downward

Даны два списка точек (A и B)
- [1] для каждой прямой в A, пересекает ли она прямую в B
-.- [2], если пересекаются никакие (более) прямые, перекрытия нет
-.- [3] если прямая в (A) пересекает прямую в B, то
-.-.- [4] добавить точку пересечения в выходные данные
-.-.- [5 ] пересекает ли следующая строка из A B
-.-.-.- [6], если нет, добавьте это в вывод (он внутри B) goto 5
-.-.-.- [7], если Итак, добавьте пересечение в выходные и переключите списки A и B goto 2

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

person Dead account    schedule 26.01.2010
comment
спасибо Джон ... должен также сказать добавить логику, чтобы избежать бесконечного цикла - person Dead account; 26.01.2010
comment
Остерегайтесь - эта проблема не так проста, как вы думаете. Некоторая пища для размышлений: одна линия (или край) в A может пересекать более одного ребра в B. Два исходных многоугольника могут не пересекаться; или А может полностью лежать внутри В; или B может полностью лежать внутри A (хотя эти три случая выглядят одинаково, если вы просто смотрите на пересечения между линиями). Многоугольники не обязательно должны быть выпуклыми, а объединение двух невыпуклых многоугольников может иметь дыры. И так далее… вычислительная геометрия печально известна наличием всевозможных особых случаев, о которых вы поначалу даже не догадывались. - person Martin B; 26.01.2010
comment
Да, Мартин - линия в группе A может пересекать более одной линии в группе B. Поэтому вам нужно будет выбрать ближайший перекресток от начальной точки. Я пробовал подход с алгоритмом намотки заливки. - person Dead account; 26.01.2010
comment
Спасибо за мысли, Ян. Я смотрю на очень похожий алгоритм на моем планшете передо мной. Я начал думать о некоторых моментах Мартина Б., которые побудили меня начать поиск библиотеки, которая могла бы сделать это за меня. - person Greg B; 26.01.2010

arrow_upward
3
arrow_downward

См. Также GPC.

person lhf    schedule 27.01.2010

arrow_upward
2
arrow_downward

Подойдет ли вам этот алгоритм?

person Jon Cage    schedule 26.01.2010
comment
Этот алгоритм вычисляет пересечение; Грег Б. ищет союза. Кроме того, этот алгоритм работает только тогда, когда оба многоугольника и их пересечение являются выпуклыми; Грег Б. говорит о произвольных формах, поэтому я предполагаю, что он тоже хочет иметь возможность обрабатывать невыпуклые многоугольники. - person Martin B; 26.01.2010
comment
Ярмарка Мартина. Я предполагал, что это выпуклые формы, и предлагал этот алгоритм в качестве отправной точки для поиска двух пересечений. - person Jon Cage; 26.01.2010
comment
Эта ссылка разорвана - person mcnutt; 21.11.2018

arrow_upward
1
arrow_downward

Как насчет:

  1. Выберите крайнюю левую точку двух фигур. Назовите эту форму A и сделайте ее текущей формой.
  2. Wind clockwise along the current shape to the next point and check to see if one or more lines intersect.
    • If any lines DO intersect, find the first intersection point and add that to your new shape. Switch to winding along the other shape.
    • Если линии не пересекаются, перейдите к следующей точке фигуры A и добавьте ее как точку в вашей новой фигуре. Продолжайте наматывать по текущей форме.
  3. Повторите шаг 2.

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

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

person Jon Cage    schedule 26.01.2010

arrow_upward
1
arrow_downward

Кажется, также есть javascript api:

https://github.com/bjornharrtell/jsts/

который, кажется, реализует стандарт jts и имеет несколько разных реализаций:

http://tsusiatsoftware.net/jts/jts-links.html#ports

все они должны иметь возможность выполнять объединение и т. д .:

http://tsusiatsoftware.net/jts/JTSUser/contents.html

Но csg.js - самый впечатляющий проект IMO

https://github.com/evanw/csg.js

person Karussell    schedule 05.02.2012