ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgeny Goljakov                      2:5020/2065.608 09 Apr 2003  05:03:20
 To : Georgy Udov
 Subject : Векторная заливка в 2D
 -------------------------------------------------------------------------------- 
 

 ...
 
 GU> Твой покорный слуга имел отношение к реализации данной
 GU> функциональности в
 GU> OpenDWG toolkit - альтернативе AutoDesk ObjectDBX, ядра
 GU> автокада.
 
 воможно где то лежит с описанием?
 
 GU> В AutoCAD\ObejctDBX есть сущность hatch, которая может быть
 GU> solid (это твой случай). Hо вообще hatch - это штриховка
 
 полигон с определенным стилем заливки(?), то что я назвал многоугольник-заливка.
 Данная сущность может иметь дыру/дыры
 внутри? И как это описывается?
 
 GU> Исходная (несколько упрощённая) постановка задачи - есть
 GU> набор отрезков на плоскости и seed point. Требуется
 GU> заштриховать (залить).
 
 А отрезки пересекаются?
 Образуют общюю точку или рвутся как уменя?
 
 GU> Суть метода - брали алгоритм заметающей прямой (есть такой
 GU> Препарата, Шеймос "Вычислительная геометрия: введение".
 
 попробую найти, в твоем изложении очень напоминает стековую заливку растра, я
 отношу данный способ решения к графическому и сам поначалу вытворял так, а потом
 ниже следующее:
 
 Task:
  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 пока не замкнем на первую линию (->polygon make)
 или пока Ls>1 (т.е. нет "висячего" конца линии)
 
 if(Ls=1) тогда откат на 1 цикл назад с исключением ее из Ls
 последующих итерации цикла
 
 if откатились до стартовой линии и Ls=1, то замкнутых цепочек
 воабще нет - EXIT
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
   Polygon make:
 
 1. Потом толкаем узлы выбранных линий в массив,
    контролируя последовательный порядок узлов
 2. удаляем дублирующиеся узлы (начало одной линии=конец другой)
 3. преобразуем массив в полигон
 ННННННННН
 
 Кто врубится в описание без зарисовок на бумаге-гений, я когда изобретал,
 рисовал 2 месяца.   Впоследствии от него пришлось отказаться в пользу
 математического способа "развилок", который
 оказался быстрее в 5 раз на 10 000 линиях. Описанный в прошлом
 письме.
 
 GU> Тебе тоже спасибо, за то, что хоть попытался понять, что я
 GU> тут написал :-)
 
 попытался, почти понял :)
 
 Спасибо за внимание.
 
 --- Spencer Winset >m>
  * Origin: Отдел не заметил потери pc (2:5020/2065.608)
 
 

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