|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Сгенерировать случайную точку, принадлежащую многоугольнику
Задание: сгенерировать случайную точку, которая бы лежала внутри многоугольника с заданными координатами (Xi,Yi).
Самое грубое, по-моему мнению, решение - кинуть случайную точку на всю область, проверить принадлежит ли эта точка многоугольнику, если да - задание решено, если нет - кидаем еще одну точку и так в цикле. Но это уж очень неоптимальный и ресурсоемкий способ. Подскажите, есть ли более интеллектуальные методы для решения подобного рода задач? |
#2
|
|||
|
|||
Ну, если многоугольник выпуклый, то можно расчитать радиус (и координаты центра) вписанной в него окружности и, таким образом, гарантированно сгенерировать точку внутри многоугольника. Для невыпуклого многоугольника такой вариант тоже прошел бы, но там сложнее найти эту окружность.
А в общем случае да, надо генерить точку и проверять ее на принадлежность многоугольнику. Т.О. получится лучшее покрытие по площади. Единственное, можно ограничить координаты генерации от Xmin до Xmax и Ymin до Ymax. |
Этот пользователь сказал Спасибо lmikle за это полезное сообщение: | ||
paxom22848 (07.01.2016)
|
#3
|
|||
|
|||
Ага, спасибо. Все-таки придется генерировать точку на всей области (конечно, ограниченной XYmin,max) и проверять на принадлежность.
Способ с окружностью хорош, но у меня такой случай, когда многоугольники могут состоять из нескольких сотен точек, а их форма будет очень неадекватна. |
#4
|
||||
|
||||
Just for lulz.
Ну, если принципиально не хочется генерировать рандомные точки наугад, можно попробовать еще такую наркоманию. 1) Генерируем рандомную точку в пределах описывающего квадрата Xmax, Ymax. 2) Если эта точка в многоугольнике - задача решена. 3) Иначе, берем фиксированную точку, 100% находящуюся внутри многоугольника, желательно как можно дальше от всех сторон. Можно определить ее заранее один раз. 4) Проводим прямую из фиксированной точки в рандомную и находим точки пересечения со сторонами многоугольника. Находим расстояние от нашей рандомной точки до ближайшей точки пересечения (т.е. до "входа" в многоугольник, если двигаться по прямой через фиксированную точку) и до следующей за ней (т.е. до "выхода"). После этого генерируем рандомную точку в этом диапазоне. Задача становится детерменированной - 2 вызова рандома и немного расчетов. Хотя я сам думаю, что это треш. jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 07.01.2016 в 18:02. |
Этот пользователь сказал Спасибо Bargest за это полезное сообщение: | ||
paxom22848 (09.01.2016)
|
#5
|
|||
|
|||
Еще вариант.
Генерируем случайно номер вершины многоугольника. Далее случайно генерируем точку внутри треугольника, образованного выбранной вершиной и соседними с ней. Хотя тут может возникать ошибка, если попадешь в вершину, которая является впадиной, т.е. надо еще проверить эти соседние вершины - куда "смотрит" этот треугольник. Короче, эвристик можно придумать много. |
Этот пользователь сказал Спасибо lmikle за это полезное сообщение: | ||
paxom22848 (09.01.2016)
|
#6
|
||||
|
||||
Тут еще одна ошибка может возникнуть. Если выбралась красная точка (которая не является "впадиной"), то синяя вполне удовлетворяет условию "находиться в треугольнике, образованном этой точкой и соседними", однако находится вне чёрного многоугольника.
А еще, например, в случае правильного 5-угольника, при таком методе сгенерированная точка никогда не попадет в крупную область в центре. И это не частный случай - таких фигур очень много. jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 07.01.2016 в 20:30. |
Этот пользователь сказал Спасибо Bargest за это полезное сообщение: | ||
paxom22848 (09.01.2016)
|
#7
|
||||
|
||||
Не е*ите мзги, товарищи.
http://314159.ru/belov/Yr_myg.htm — Как тебя понимать? — Понимать меня не обязательно. Обязательно меня любить и кормить вовремя. На Delphi, увы, больше не программирую. Рекомендуемая литература по программированию |
Этот пользователь сказал Спасибо M.A.D.M.A.N. за это полезное сообщение: | ||
paxom22848 (09.01.2016)
|