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

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

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

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

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

alexprey, я сейчас ее и юзаю (точнее ее часть). Это очень не дешево для поиска простой точки. Слишком жирно имхо.

Да и я написал что пробовал искать среднее (видимо некорректно описал). Это не работает, так как многоугольник самый что ни на есть произвольный.

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

alexprey, очень часто. Я потому и прошу максимально дешевое решение для гарантированного поиска точки. Наверняка ведь что-то такое есть. Может что-то минимаксное.

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

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

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

alexprey:

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

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

GeneralElConsul, ну просто

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

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

Mihahail:

Вот тут не понял. Типа (min.x, max.y)?

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

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

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

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

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

хм, надо подумать могу ли я их заранее "узнать". Хороший совет.
Mihahail, хорошее решение. Если не получится заранее определить многоугольник (там, где я их формировал) то наверное так и сделаю.

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

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

alexprey, Пока нет. Отложил задачу до понедельника.
Mihahail:

Такой способ не подходит, ибо угол, слишком близко к A может все попортить

На другой случай который ты предложил я таки смог найти контрпример где опять же нужно проверять пересечения.

Причем соль в том что такую картину можно сделать даже на выпуклом углу (от смежной точки можно создать пересечение отделяющее от ближайшей D)

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

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

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

Mihahail:

Зачем? :)

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

Mihahail, вот именно. Оно требует перебрать все пересечения на предмет наименьших, а там же еще и вычисление точки выходит, что не быстро. Даже по триангуляции быстрее перебрать, там хотя бы просто факт непересечения нужен, а не точка.

Devion,

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