Найти точку, гарантированно принадлежащую многоугольнику

Как тебе вариант с триангуляцией?

Сложить координаты Х всех точек многоугольника, сложить координаты У всех точек многоугольника. Разделить оба полученных числа на количество точек многоугольника.
Ну и с Z тоже самое.

GeneralElConsul, зачем всех то? Хватит двух любых вершин не на одной грани чтобы внутреннююю точку получить, вопрос то не про центр задан, вот только работает и то и другое исключительно для выпуклых многоугольников.

Расчет был на то, что есть только точки.
С выпуклым прав.
Кое-что нашел gd-stalking.blogspot.com/2011/05/blog-post.html?m=1

Devion, думаю стоит описать как часто меняются точки и их координаты

Devion, часто строятся произвольные многоугольники и нужно найти точку вхождения... хмм как то странно. А мб правило какое нибудь простое для построения? так проще будет сориентироваться

хммм, пробовал находить проекцию?
есть ли вероятность перекрученного многоугольника?
ох, короче засада(

А как ты будешь проверять это условие, взяв точку внутри наугад?

Ой. Я, кажется, решил :)
Находим крайнюю точку(min|max координата), берем её соседние две. Имеем три точки, треугольник. Его центр масс - искомая точка.

Я фигню написал. Прошу прощения, прошу забыть :)
Точнее не фигню, эта идея выше - всего лишь часть правильного метода.

Devion, я имел ввиду две смежные точки. Есть крайняя вершина А, а есть её смежные вершины В и С.
Я думал центр масс треугольника АВС подойдёт.
Контрпример легко придумать: вогнутый четырёхугольник.
Модифицировал слегка.

Рассуждения вообще вот такие: единственный быстрый способ не оказаться за многоугольником - выбрать крайнюю точку А и две смежных с ней В и С. Тогда внутри полученного угла ищем ближайшую к А точку D(которая может совпадать с В и С), проводим окружность с центром в А и радиусом AD. Любая точка внутри полученного сектора круга(серая область на рисунке) - подходит.

Хотя мб попробовать брать треугольник АPQ, где P и Q - точки на смежных А рёбрах, лежащие очень близко к А..? Ну, чтобы не тратиться на поиск ближайшей точки.

Devion, в чем проблема хранить породившие многоугольники?

Хм, если брать задачу в комментах, а не сабжевую, то я ничего не буду рекомендовать, ибо не знаю, что именно разрабатывается. Полную бы задачу услышать, но уповаю на то, что иного выхода, кроме того, что в посте - нет :)

Ну что в итоге то? Решение нашли?

Хм, ты прав.
Хотя, похоже, что это возможно лишь в тупом угле. Тогда можно просто искать острый.. Хотя не факт, что он есть:)
Можно попробовать проверять каждую грань на пересечение с отрезком AD(в моих обозначениях), но это вроде как долго. Ещё можно искать не крайнюю точку, а крайнее ребро, но пока это у меня поток мысли, без идей.
Узнал, что проверить принадлежность точки невыпуклому многоугольнику можно за линейное(aka полиноминальное) время. habrahabr.ru/post/161237
А вики утверждает следующее:

Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N-угольника эта задача может быть решена за время O(log2 N) с использованием O(N) памяти и O(N log N) времени на предобработку.

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

Ну, там вроде любят такое.. Решение и оптимизация сложной алгоритмической задачи, как-никак :)
На самом деле, можно было не страдать фигней и пулять произвольным лучом в этот многоугольник, считать его число пересечений с гранями, и брать любую точку меджду первым и вторым пересечением.
Но я так понимаю, классическое решение недостаточно быстрое?

Devion,

1. можешь подробнее объяснить чем принципиально не подходят точки на гранях и вершины?
2. какая вычислительная сложность сейчас у твоего алгоритма? не факт, что найдется идеальное решение, а вот более дешевое можно и поискать, но для этого нужен критерий сравнения.