Вычислите объединение двух произвольных форм
Я работаю над приложением, я должен смочь объединить две перекрывающихся произвольных формы, как оттянуто пользователем. Это была бы Операция объединения на двух формах. Результирующая форма была бы контуром двух перекрывающихся форм.
Формы хранятся как последовательность точек в по часовой стрелке способ.
Идеально я хотел бы алгоритм, который возьмет два массива Точек (x, y) и возвратит единый массив результирующей формы.
Я читал Википедию на Логических операциях на полигонах, которая упоминает алгоритм строки Развертки, но я не могу сделать ссылку между этим и моей целью, увы я не Математик.
Я разрабатываю приложение в ActionScript 3, но я знаком с C#, Java, и я могу выбрать свой путь через C и C++.
5 ответов
Правильная реализация булевых операций не тривиальна, к счастью, есть библиотеки, которые уже реализуют эту функциональность.
Какой язык вы используете? Если это C++, то посмотрите на CGAL, библиотеку алгоритмов вычислительной геометрии.
Как насчет:
- Выберите левую точку двух форм. Позвоните в форму и сделайте ее текущей формой.
- Ветер по часовой стрелке вдоль текущей формы к следующей точке и проверьте, следует ли посмотреть ли один или несколько линий.
- Если какие-либо строки выполняют пересечение, найдите первую точку пересечения и добавьте это в новую форму. Переключитесь на обмоть по другой форме.
- Если нет строк пересекаются, перемещайтесь на следующую точку в форме A и добавьте, что в качестве точки вашей новой формы. Продолжайте обмоток вдоль текущей формы.
- Повторите шаг 2.
Я думаю, что если вы продолжаете обмотку по тому, какая форма является током, ищете пересечения, которые должны делать то, что вы хотите. Я думаю, что это должно справиться с вогнутой формыми, а также ...
Я уверен, что есть много оптимизации, вы можете добавить, как только у вас есть основы, работающие.
Указаны два списка точек (A и B)
- [1] для каждой строки в a, он пересекает линию в b
-.- [2] Если нет (больше) линий пересекаются, не совпадают
-.- [3] Если линия в (а) пересекает линию в B, затем
-.-.- [4] Добавьте точку пересечения на выход
-.-.- [5] делает следующую строку от пересечения B
-. - .- .- [6] Если нет, добавьте это к выводу (он внутри b) goto 5
-.-. - .- .- [7] Если так, добавьте пересеченные к выводу и спискам переключателей A & B GOTO 2
также см. Точку пересечения двух линий . Я не собираюсь написать код извините :)