Определить полигон с указанным свойством

Question

Я создаю графический проект, в котором я должен найти в какой-то момент времени, что если существует точка x внутри многоугольника, такая, что, если я присоединяю эту точку ко всем вершинам этого многоугольника, то все отрезки линиисоединение вершин, и эта точка x полностью лежит внутри многоугольника.

Интересно, есть ли какой-нибудь известный алгоритм для этого или кто-нибудь из вас может описать алгоритм для этого.

Я ищу алгоритм линейного времени.

Answer 1

Вы спрашиваете, как вычислить ядро ​​многоугольника в форме звезды.Эта проблема была решена в 1979 году Ли и Препаратой в статье под названием Оптимальный алгоритм нахождения ядра многоугольника .Из их аннотации:

Ядро K(P) простого многоугольника P с n вершинами является местоположением точек, внутренних по P, из которых все вершины Pравнозначно, K(P) - это пересечение соответствующих полуплоскостей, определяемых ребрами многоугольника.Хотя известно, что для нахождения пересечения n общих полуплоскостей требуется время O(n log n), мы показываем, что можно использовать упорядочение полуплоскостей, соответствующих последовательности ребер многоугольника, чтобы получить алгоритм поиска ядракоторый работает во времени O(n) и поэтому является оптимальным.