ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Georgy Udov                          2:5030/49.1    10 Apr 2003  13:06:04
 To : Evgeny Goljakov
 Subject : Векторная заливка в 2D
 -------------------------------------------------------------------------------- 
 

 Доброе время суток, Evgeny!
 Ты писАл to All on Sun, 06 Apr 03 01:29:28 +0400:
 
  EG>  Вот некоторые соображения по сабжу, возможно кто сталкивался или
  EG> просто поделится своими идеями.
 
 Hе очень разобрался в твоих идеях, но своими попробую поделиться.
 
  EG> Подобное как-то реализованно в автокаде или флэшке?
 
 Твой покорный слуга имел отношение к реализации данной функциональности в
 OpenDWG toolkit - альтернативе AutoDesk ObjectDBX, ядра автокада.
 
 В AutoCAD\ObejctDBX есть сущность hatch, которая может быть solid (это твой
 случай). Hо вообще hatch - это штриховка.
 
 Исходная (несколько упрощённая) постановка задачи - есть набор отрезков на
 плоскости и seed point. Требуется заштриховать (залить).
 
 Мы сначала делали штриховку, а потом - заливку, поэтому алгоритм заливки
 получился, возможно, не самый оптимальный.
 
 Суть метода - брали алгоритм заметающей прямой (есть такой хороший алгоритм
 нахождения всех пересечений кучи отрезков). Hаписано про него, например, в
 
 Препарата, Шеймос "Вычислительная геометрия: введение".
 
 Данный алгоритм тащит вертикальную заметающую прамую. В точках событий (это
 начала отрезков, концы, а также пересечения, которые он находит) мы смотрим
 на эту самую з. прямую (з. прямая - это структура данных, хранящая номера
 отрезков в отсортированном по очерёдностью пересечения с абсциссой события
 виде) и выкидываем набор трапеций (у трапеций параллельные стороны -
 вертикальные, вершины расчитываются исходя из информации об абсциссах
 текущего и предыдущего события, а также из номеров отрезков, хранящихся в з.
 прямой). Предполагается, что зная точки пересечения вертикальной прямой с
 заданным множеством отрезков, мы можем узнать, какие из вертикальных
 отрезков должны принадлежать залитой области (это делается из соображений
 чёт-нечет, etc).
 
  EG> Спасибо за внимание.
 
 Тебе тоже спасибо, за то, что хоть попытался понять, что я тут написал :-)
 
 Vale, Georgy Udov.  E-mail: udovgeorgy#SPAMOFFchat.ru
 --- ifmail v.2.15
  * Origin: http://news.kaa.ru (2:5030/49.1)
 
 

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

Тема:    Автор:    Дата:    Векторная заливка в 2D   Evgeny Goljakov   06 Apr 2003 02:29:28   Векторная заливка в 2D   Georgy Udov   10 Apr 2003 13:06:04