Многоугольник в форме звезды - Star-shaped polygon
А звездообразный многоугольник это полигональная область в самолете, который звездный домен, то есть многоугольник, содержащий точку, от которой начинается вся граница многоугольника. видимый.
Формально многоугольник п имеет форму звезды, если существует точка z так что для каждой точки п из п сегмент zp полностью лежит внутри п.[1] Набор всех точек z с этим свойством (то есть набор точек, из которых все п видна) называется ядро из п.
Если многоугольник в форме звезды выпуклый, то расстояние связи между любыми двумя его точками (минимальное количество последовательных линейных сегментов, достаточных для соединения этих точек) - 1, поэтому диаметр звена многоугольника (максимальное расстояние звена по всем парам точек) равен 1. Если звездообразный многоугольник равен не выпуклый, расстояние связи между точкой в ядре и любой другой точкой в многоугольнике равно 1, в то время как расстояние связи между любыми двумя точками, которые находятся в многоугольнике, но вне ядра, равно 1 или 2; в этом случае максимальное расстояние связи равно 2.
Примеры
Выпуклые многоугольники имеют форму звезды, а выпуклый многоугольник совпадает со своим ядром.
Обычный звездные многоугольники имеют звездообразную форму, с центром всегда в ядре.
Антипараллелограммы и самопересекающиеся Шестиугольники Лемуана имеют звездообразную форму с ядром, состоящим из одной точки.
Полигоны видимости имеют форму звезды, так как каждая точка внутри них должна быть видна в центре по определению.
Алгоритмы
Проверить, является ли многоугольник звездообразным, и найти единственную точку в ядре, можно в линейное время формулируя проблему как линейная программа и применение методов низкоразмерного линейного программирования (см. http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, стр.16).
Каждый край многоугольника определяет интерьер полуплоскость, полуплоскость, граница которой лежит на прямой, содержащей ребро, и которая содержит точки многоугольника в район любой внутренней точки края. Ядро многоугольника - это пересечение всех его внутренних полуплоскостей. Пересечение произвольного множества N полуплоскости можно найти в Θ (N бревно N) время с помощью разделяй и властвуй подход.[1] Однако для ядер полигонов возможен более быстрый метод: Ли и Препарата (1979)[2] представили алгоритм построения ядра за линейное время.
Смотрите также
Рекомендации
- ^ а б Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. 1-е издание: ISBN 0-387-96131-3; 2-е издание, исправленное и расширенное, 1988 г .: ISBN 3-540-96131-3.
- ^ Ли, Д. Т.; Препарата, Ф. (Июль 1979 г.), «Оптимальный алгоритм поиска ядра многоугольника», Журнал ACM, 26 (3): 415–421, Дои:10.1145/322139.322142, HDL:2142/74090