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

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

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

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

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

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

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

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

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

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

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

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

Devion,

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

Уповая на то, что арифметика(+, -, *) быстрая, буду считать только if'ы/сравнение и деление, как самые затратные операции.
Поиск грани, пересекающей (пусть вертикальную)прямую, имеет линейную сложность(2*N проверок). Координаты точки пересечения, если известно, что оно есть - определяются сразу по формуле, тут 1 деление(т.к. прямая вертикальная).
После каждого пересечения для поиска минимакса делаются ещё от одной до двух проверок. Пересечений не более N-1, значит, не более 2*(N-1) дополнительных проверок.
Итого около 4*N операций.

Куда ещё лучше-то?
И плюсую prog у, особенно за второй вопрос.

от N*3 до (N^2)*3 при разных случаях

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

Например, если алгоритм проверки проверяет стороны от точки вправо - то только правые ребра будут детектить принадлежность препятствию, а левые наоборот. (точнее не правые/левые, а "слева направо" относительно горизонтального луча, это немного другое). Эта неоднозначность в выборе направления проверки и заставляла искать решение получше.

Однако в сути при обходе справа можно взять правую грань, причем сделать это можно достаточно быстро, если все многоугольники развернуты по часовой стрелке - это будет первая сторона, у которой p1.y > p2.y. Даже если не развернуты то ориентацию тоже можно быстро просчитать через сумму углов многоугольника.

А вообще нет, я не прав. Ребро таки нельзя. Почему? Да потому что флоат, потому что погрешность - и пересечение существует лишь иногда, нестабильно. Таки нужно искать точку внутри :С