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

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

GeneralElConsul, ну просто

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

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

Mihahail:

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

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

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

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

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

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

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

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

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

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

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

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