Многоугольник в форме звезды - 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] представили алгоритм построения ядра за линейное время.

Смотрите также

Рекомендации

  1. ^ а б Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. 1-е издание: ISBN  0-387-96131-3; 2-е издание, исправленное и расширенное, 1988 г .: ISBN  3-540-96131-3.
  2. ^ Ли, Д. Т.; Препарата, Ф. (Июль 1979 г.), «Оптимальный алгоритм поиска ядра многоугольника», Журнал ACM, 26 (3): 415–421, Дои:10.1145/322139.322142, HDL:2142/74090