ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Victor Sotnikov                      2:5020/400     13 Aug 2002  19:29:37
 To : All
 Subject : Преобразование полигона с дырами в полигон без дыр.
 -------------------------------------------------------------------------------- 
 

 Hi All,
 Пусть у нас есть 'полигон с дырами'. Это множество полигонов Р={B, H0,H1,
 H2,...,HS}, где полигон B, содержащий Hi для всех i=0,...,S, называется
 внешним полигоном, а полигоны Hi, i=0,...,S со свойством Hi AND Hj = empty
 i,j=0..S, называются дырами. Точка является внутренней для полигона с дырой,
 если она принадлежит нечетному числу полигонов из Р. Более подробно о
 полигонах с дырами см. на http://alglib.chat.ru/paper/convpol.html.
 
 Hам нужно преобразовать такой полигон в полигон без дыр. Пример: пусть есть
 внешний полигон из точек A (0,0), B (4,0), C (4,4), D(0,4) и дыра, описываемая
 точками E (1,1), F (3,1), G(3,3), H(1,3). Тогда такой полигон с дырой можно
 преобразовать в полигон {A,B,F,E,H,G,F,B,C,D}, который дыр не имеет и равен по
 форме исходному полигону с дырой.
 
 Вопрос: какие известны алгоритмы для такого преобразования и какой из них
 самый быстрый?
 
 Hе обязательно, чтобы 'разрез' (отрезки B-F и F-B в вышеприведенном примере)
 обязательно проходил бы от вершины дыры к вершине внешнего полигона: он может
 идти от вершины дыры к любой точке на контуре внешнего полигона.
 
 Спасибо,
 Victor Sotnikov
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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