ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgeny Goljakov                      2:5020/2065.608 13 Jan 2003  16:39:56
 To : All
 Subject : Векторная заливка
 -------------------------------------------------------------------------------- 
 

 
  Вот некоторые соображения по сабжу, возможно кто сталкивался
 или просто поделится своими идеями.
 
  Имеется набор Линий, каждая Линия задана 2 или более Точками,
 последовательно соединенными "по прямой". Каждая Точка описана
 парой координат X,Y.
 
  Линии ориентированны произвольно.
  Пересекаясь, 2 линии "резали" друг-друга, образуя 4 новые.
  Как следствие, только из первой или последней точки линии  возможно
 разветвление.
 
  Hеобходимо из заданной Точки Т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. Теперь нужно более быстро - математически.
 
  Hеобходимо выполнение усливия выбора в точке развилки Ls линии
 с меньшим углом против направления обхода общего контура, что
 будет соответствовать выбору фигуры с наименьшем перриметром.
 
 След. появились вопросы которые необходимо решать однозначно:
 
 1.Как всегда начинать обход по час/против, ведь юзер может  поставить точку
 заливки произвольно, внутри будующего контура.   Осложняется тем, что линии
 слагающие будующий контур имеют
  различную направленность Точек.
 
 2.Определить наименьший угол у развилки, (имея координаты:
     Т1(X,Y)-начало всех линий в месте развилки и
     Т2(X,Y)-вторыые точки, ломанных далее линий)
  по отношению к текущей линии контура, т.е. ее последней
  точки Т1 и предпоследней Т1-1, т.к. перед этим линейным  сегментом линия может 
 быть ломанна.
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 
  Возможно, вопросы здесь обсуждались, буду рад любой помощи.
 
 Спасибо за внимание.
 
 --- Spencer Winset >m>
  * Origin: Скептис присутствует (2:5020/2065.608)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор