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

Ой. Я, кажется, решил :)
Находим крайнюю точку(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) времени на предобработку.

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