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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

Смотрите также ГПХ.

Answer 4

Бы этот алгоритм работать на тебя?

Answer 5

Как насчет:

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

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

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

Answer 6

Кажется, есть также 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 — самый впечатляющий проект, по моему мнению.

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