Звездообразный многоугольник является многоугольной областью в плоскости , которая является звездой домена , то есть полигон , который содержит точку , из которой вся граница многоугольника видна .
Формально многоугольник Р находится в форме звезды , если существует точка г такая , что для каждой точки р из Р сегмента Zp целиком лежит внутри P . [1] Множество всех точек г с этим свойством (то есть множество точек , из которых все P видна) называется ядром из P .
Если звездообразный многоугольник является выпуклым , расстояние связи между любыми двумя его точками (минимальное количество последовательных сегментов линии, достаточное для соединения этих точек) равно 1, поэтому диаметр связи многоугольника (максимальное расстояние связи по всем парам точек) равно 1. Если звездообразный многоугольник не является выпуклым, расстояние связи между точкой в ядре и любой другой точкой многоугольника равно 1, в то время как расстояние связи между любыми двумя точками, которые находятся в многоугольнике, но за пределами ядро либо 1, либо 2; в этом случае максимальное расстояние связи равно 2.
Примеры [ править ]
Выпуклые многоугольники имеют форму звезды, а выпуклый многоугольник совпадает со своим ядром.
Правильные звездчатые многоугольники имеют звездообразную форму с центром всегда в ядре.
Антипараллелограммы и самопересекающиеся шестиугольники Лемуана имеют звездообразную форму, а ядро состоит из одной точки.
Полигоны видимости имеют звездообразную форму, поскольку каждая точка внутри них должна быть видна в центре по определению.
Алгоритмы [ править ]
Проверить, является ли многоугольник звездообразным, и найти единственную точку в ядре, можно за линейное время , сформулировав задачу в виде линейной программы и применив методы низкоразмерного линейного программирования (см. Http://www.inf .ethz.ch / personal / emo / PublFiles / SubexLinProg_ALG16_96.pdf , стр. 16).
Каждое ребро многоугольника определяет внутреннюю полуплоскость , полуплоскость, граница которой лежит на прямой, содержащей ребро, и которая содержит точки многоугольника в окрестности любой внутренней точки ребра. Ядро многоугольника - это пересечение всех его внутренних полуплоскостей. Пересечение произвольного набора из N полуплоскостей может быть найдено за Θ ( N log N ) времени, используя подход « разделяй и властвуй» . [1] Однако в случае ядер многоугольников возможен более быстрый метод: Lee & Preparata (1979) [2] представили алгоритм построения ядра за линейное время.
См. Также [ править ]
Ссылки [ править ]
- ^ a b Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . 1-е издание: ISBN 0-387-96131-3 ; 2-е издание, исправленное и расширенное, 1988: ISBN 3-540-96131-3 .
- ^ Ли, DT ; Препарата, FP (июль 1979), "Оптимальный алгоритм для нахождения ядра из Polygon" , Журнал ACM , 26 (3): 415-421, DOI : 10,1145 / 322139,322142 , ЛВП : 2142/74090
