Алгоритмы заливки векторной графики?

Question

Я работаю над простым приложением для рисования, и мне нужен алгоритм для создания заливок.
Рабочий процесс пользователя будет выглядеть следующим образом (аналогично Flash CS, только проще):

1. пользователь рисует прямые линии в рабочей области.Они обрабатываются как векторы, и их можно выбирать и перемещать после их рисования.
2. пользователь выбирает инструмент заливки и щелкает область рисования.Если область окружена линиями в каждом направлении, к области применяется заливка.

если линии перемещаются после применения заливки, область заливки изменяется соответствующим образом.

У кого-нибудь есть хорошая идея, как реализовать такой алгоритм?Основная задача в основном определить отрезки, окружающие точку.(и сохраняя эту информацию каким-либо образом, в случае, если линии перемещены)

РЕДАКТИРОВАТЬ: изображение объяснения: (могут быть и другие строки на холсте, которые не имеют значения для алгоритма заполнения)

РЕДАКТИРОВАТЬ2: более сложная ситуация:

РЕДАКТИРОВАТЬ3: я нашел способ заполнить полигоны отверстиями http://alienryderflex.com/polygon_fill/, теперь главный вопрос, как мне найти мои полигоны?

Answer 1

Вы ищете алгоритм определения местоположения.Это не слишком сложно, но это не достаточно просто, чтобы объяснить здесь.В этой книге есть хорошая глава: http://www.cs.uu.nl/geobook/

Когда я вернусь домой, я получу свой экземпляр книги и посмотрю, смогу ли я попробовать в любом случае.Там просто много деталей, о которых вы должны знать.Все сводится к построению DCEL ввода и поддержанию структуры данных по мере добавления или удаления линий.Любой запрос с координатами мыши просто вернет внутренний полжедрок компонента, а в частности, он содержит указатели на все внутренние компоненты, что и является именно тем, о чем вы просите.

Хотя есть одна вещь:что вам нужно знать пересечения во входных данных (потому что вы не можете построить трапецеидальную карту, если у вас есть пересекающиеся линии), и если вы можете сойти с рук (т.е. входных данных достаточно мало сегментов), я настоятельно рекомендую вам просто использовать наивныйАлгоритм O (n²) (простой, кодируемый и тестируемый менее чем за 1 час).Алгоритм O (n log n) занимает несколько дней, чтобы закодировать и использовать умную и очень нетривиальную структуру данных для статуса.Это, однако, также упоминается в книге, поэтому, если вы чувствуете, что у вас есть задача, у вас есть две причины, чтобы купить ее.Это действительно хорошая книга по геометрическим проблемам в целом, поэтому только по этой причине любой программист, интересующийся алгоритмами и структурами данных, должен иметь копию.

Answer 2

Попробуйте это:

http://keith -hair.net / блог / 2008/08/04 / найти-пересечения-точка-в-двух линий-в-as3 /

Функция возвращает пересечение (если есть) между двумя строками в ActionScript. Вам нужно будет перебрать все свои линии друг против друга, чтобы получить их все.

Конечно, порядок точек будет значительным, если вы планируете их заполнить - это может быть сложнее!

Answer 3

В ActionScript вы можете использовать beginFill и endFill, например,

pen_mc.beginFill(0x000000,100);
pen_mc.lineTo(400,100);
pen_mc.lineTo(400,200);
pen_mc.lineTo(300,200);
pen_mc.lineTo(300,100);
pen_mc.endFill();

http://www.actionscript.org/resources/articles/212/1/Dynamic-Drawing-Using-ActionScript/Page1.html

В Flash CS4 также добавлена ​​поддержка путей:

http://www.flashandmath.com/basic/drawpathCS4/index.html

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