Преобразование полигона с дырами в полигон без дыр.

From

Victor Sotnikov ()

To

All

Date

2002-08-13T19:29:37Z

Area

RU.ALGORITHMS

From: "Victor Sotnikov" <victor@relsoft.by>

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.

Нам нужно преобразовать такой полигон в полигон без дыр. Пример: пусть есть
внешний полигон из точек 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}, который дыр не имеет и равен по
форме исходному полигону с дырой.

Вопрос: какие известны алгоритмы для такого преобразования и какой из них
самый быстрый?

Не обязательно, чтобы 'разрез' (отрезки B-F и F-B в вышеприведенном примере)
обязательно проходил бы от вершины дыры к вершине внешнего полигона: он может
идти от вершины дыры к любой точке на контуре внешнего полигона.

Спасибо,
Victor Sotnikov

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)