Векторная заливка

From

Evgeny Goljakov (2:5020/2065.608)

To

All

Date

2003-01-13T15:39:56Z

Area

RU.ALGORITHMS

 Привет, All!

 Вот некоторые соображения по сабжу, возможно кто сталкивался
или просто поделится своими идеями.

 Имеется набор Линий, каждая Линия задана 2 или более Точками,
последовательно соединенными "по прямой". Каждая Точка описана
парой координат X,Y.

 Линии ориентированны произвольно.
 Пересекаясь, 2 линии "резали" друг-друга, образуя 4 новые.
 Как следствие, только из первой или последней точки линии  возможно разветвление.

 Необходимо из заданной Точки Т0 с любыми коорд. X,Y ,
"разлить" чернила по области, ограниченной имеющимися линиями (т.е. фактически последовательно заполнить массив точками, которые будут являться вершинами многоугольника-заливки).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 

      I. Первоначально решал "в лоб" - графически.

0.от Точки Т0 пускаем луч и берем первую подсеченную Линию L

1.у L берем 1-ую точку Т1 и соединяем с Т0, получаеm отрезок О   пренадлежащий центру заполняемой области (вспом. линия)

2.берем все линии Ls начинающиеся/заканч. Т1, вторую точку
  Т2 каждой линии соединяем с центром отрезка О = Onew
  (исключая L)

 a.и берем ту линию которая не пересекает других линий из Ls
   (включая L),    Т0 = центр Оnew

 b.а если таких нет (угол при Т1 >180 для всех) берем линию    пересекающюю  наибольшее число линий из Ls,
   Onew, продлеваем через Т1 (до пересечения с любой линией),
   Т0 = центр Оnew

прим. к п.1 при первой итерации Т1 берем произвольно,
 при последующих самую дальнюю от последней Т1.

 Выполняем 1-2 пока не замкнем,
или пока Ls>1 (т.е. нет "висячего" конца линии)

if(Ls=1) тогда откат на 1 цикл назад с исключением ее из Ls последующих итерации цикла

if откатились до стартовой линии и Ls=1, то замкнутых цепочек
воабще нет - EXIT
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
       II. Теперь нужно более быстро - математически.

 Необходимо выполнение усливия выбора в точке развилки Ls линии
с меньшим углом против направления обхода общего контура, что
будет соответствовать выбору фигуры с наименьшем перриметром.

След. появились вопросы которые необходимо решать однозначно:

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

2.Определить наименьший угол у развилки, (имея координаты:
    Т1(X,Y)-начало всех линий в месте развилки и
    Т2(X,Y)-вторыые точки, ломанных далее линий)
 по отношению к текущей линии контура, т.е. ее последней
 точки Т1 и предпоследней Т1-1, т.к. перед этим линейным  сегментом линия может быть ломанна.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 

 Возможно, вопросы здесь обсуждались, буду рад любой помощи.

Спасибо за внимание.

--- Spencer Winset >m>
 * Origin: Скептис присутствует (2:5020/2065.608)