Найти любую точку внутри многоугольника

Question

Вопрос:

Как найти любую точки внутри многоугольника, причем эта точка будет по крайней мере, расстояние epsilon от края (чтобы избежать численных проблем).

Объяснение:

Проблема, которую я хочу, чтобы найти решение отличается от обычного точка внутри многоугольника проблемы. Я предполагаю, что это может быть проще или построено на ответе на в алгоритме polygon (например, для лучевого каста).

Процесс может начаться с выбора псевдо-средней точки многоугольника (мин + макс)/2. Эта точка может быть проверена лучей или что-то подобное. Если точка не находится внутри другой точки, случайным образом выбирается где-то между мин. и max каждой оси.

Полигоны, о которых мы говорим, имеют неправильную форму, определяемую десятками до ста вершин. Не было бы самопересечений. Я беспокоюсь о числовых проблемах, если я выбираю точку вблизи краев многоугольника, поэтому необходимо добавить точку не очень близко к краю. Это не должно быть особенно эффективным с точки зрения вычислительной эффективности, просто не безумным неэффективным.

Возможно ли это решить простым, элегантным способом?

Я использую Lua.

Answer 1

Выберите точку на многоугольнике, которая является крайней в каком-либо направлении, например. точка с наибольшей координатой y. Переместите небольшое расстояние в направлении линии, делящей пополам линии от этой точки до точек по обе стороны от нее. Убедитесь, что вы находитесь в многоугольнике, и если не уменьшите пройденное расстояние.

Если есть связи, и точки, расположенные по обе стороны от нее, имеют одинаковую координату, вам придется попробовать контрольные точки с обеих сторон.