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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

См. Также ГПХ .

Answer 3

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

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

Answer 4

Будет ли этот алгоритм работать на вас?

Answer 5

Кажется, что есть также 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

Answer 6

Как насчет:

1. Выберите самую левую точку двух фигур. Назовите эту форму A и сделайте ее текущей формой.
2. Поверните по часовой стрелке вдоль текущей фигуры к следующей точке и проверьте, не пересекаются ли одна или несколько линий.
   • Если какие-либо линии ДОЛЖНЫ пересекаться, найдите первую точку пересечения и добавьте ее к своей новой фигуре. Переключитесь на намотку вдоль другой формы.
   • Если линии не пересекаются, перейдите к следующей точке в форме A и добавьте ее в качестве точки в вашей новой форме. Продолжайте наматывать вдоль текущей формы.
3. Повторите шаг 2.

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

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