[paxom22848]

Задание: сгенерировать случайную точку, которая бы лежала внутри многоугольника с заданными координатами (Xi,Yi).
Самое грубое, по-моему мнению, решение - кинуть случайную точку на всю область, проверить принадлежит ли эта точка многоугольнику, если да - задание решено, если нет - кидаем еще одну точку и так в цикле.
Но это уж очень неоптимальный и ресурсоемкий способ.
Подскажите, есть ли более интеллектуальные методы для решения подобного рода задач?

[lmikle]

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

А в общем случае да, надо генерить точку и проверять ее на принадлежность многоугольнику. Т.О. получится лучшее покрытие по площади. Единственное, можно ограничить координаты генерации от Xmin до Xmax и Ymin до Ymax.

[paxom22848]

Ага, спасибо. Все-таки придется генерировать точку на всей области (конечно, ограниченной XYmin,max) и проверять на принадлежность.
Способ с окружностью хорош, но у меня такой случай, когда многоугольники могут состоять из нескольких сотен точек, а их форма будет очень неадекватна.

[Bargest]

Just for lulz.
Ну, если принципиально не хочется генерировать рандомные точки наугад, можно попробовать еще такую наркоманию.
1) Генерируем рандомную точку в пределах описывающего квадрата Xmax, Ymax.
2) Если эта точка в многоугольнике - задача решена.
3) Иначе, берем фиксированную точку, 100% находящуюся внутри многоугольника, желательно как можно дальше от всех сторон. Можно определить ее заранее один раз.
4) Проводим прямую из фиксированной точки в рандомную и находим точки пересечения со сторонами многоугольника. Находим расстояние от нашей рандомной точки до ближайшей точки пересечения (т.е. до "входа" в многоугольник, если двигаться по прямой через фиксированную точку) и до следующей за ней (т.е. до "выхода"). После этого генерируем рандомную точку в этом диапазоне.

Задача становится детерменированной - 2 вызова рандома и немного расчетов. Хотя я сам думаю, что это треш.

[lmikle]

Еще вариант.
Генерируем случайно номер вершины многоугольника.
Далее случайно генерируем точку внутри треугольника, образованного выбранной вершиной и соседними с ней. Хотя тут может возникать ошибка, если попадешь в вершину, которая является впадиной, т.е. надо еще проверить эти соседние вершины - куда "смотрит" этот треугольник.

Короче, эвристик можно придумать много.

[Bargest]

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

А еще, например, в случае правильного 5-угольника, при таком методе сгенерированная точка никогда не попадет в крупную область в центре. И это не частный случай - таких фигур очень много.

[M.A.D.M.A.N.]

Не е*ите мзги, товарищи.
http://314159.ru/belov/Yr_myg.htm