Многоугольник в форме звезды
- Звездообразный многоугольник – многоугольная область на плоскости, содержащая точку, из которой видна вся граница.
- Формально многоугольник P имеет форму звезды, если существует точка z, такая, что для каждой точки p из P отрезок zp полностью находится в пределах P.
- Множество всех точек z, обладающих этим свойством, называется ядром P.
- Если многоугольник в форме звезды выпуклый, то расстояние между любыми двумя его точками равно 1, и, следовательно, диаметр многоугольника равен 1.
- Если звездообразный многоугольник не является выпуклым, расстояние между точкой в ядре и любой другой точкой многоугольника равно 1, в то время как расстояние между любыми двумя точками, которые находятся в многоугольнике, но вне ядра, равно 1 или 2.
- Проверка того, имеет ли многоугольник звездообразную форму, и поиск единственной точки в ядре могут быть решены за линейное время.
- Ядро многоугольника – это точка пересечения всех его внутренних полуплоскостей.
Полный текст статьи: