Насколько я понял, нужно найти точку внутри, а не определить, является ли данная точка внутри
Ну так, это примерно то же самое.
Например, берем первые две вершины. Проводим произвольную вертикальную прямую между ними. Считаем количество пересечений, как описано ранее. Ставим произвольную между самым верхним(нижним) и следующим сверху (снизу) пересечением. Она заведомо принадлежит.
Причем, не важно, выпуклая фигура, вогнутая, с дырками, без дырок..
не пройдет. распределение будет не uniform.
по правильному (как делается в cg методах, где требуется random
sampling) - строитcя bounding rectangle и выбирается random точка.
если она попала в полигон - done, если нет - то выбирается новая.
понятно, что чем ближе -гранник к прямоугольнику, тем меньше в
среднем будет итераций ..
Насколько я понял, нужно найти точку внутри, а не определить, является ли данная точка внутри
Ну так, это примерно то же самое.
Например, берем первые две вершины. Проводим произвольную вертикальную прямую между ними. Считаем количество пересечений, как описано ранее. Ставим произвольную между самым верхним(нижним) и следующим сверху (снизу) пересечением. Она заведомо принадлежит.
Причем, не важно, выпуклая фигура, вогнутая, с дырками, без дырок..
не пройдет. распределение будет не uniform.
по правильному (как делается в cg методах, где требуется random
sampling) - строитcя bounding rectangle и выбирается random точка.
если она попала в полигон - done, если нет - то выбирается новая.
понятно, что чем ближе -гранник к прямоугольнику, тем меньше в
среднем будет итераций ..
Ошибаешься. Он предложил правильное решение. Если считаешь, что решение неправильное, то приведи пример - дай координаты точек многоугольника, для которого бы это не работало, типа
ПС. Ну а про распределение (вероятности или плотности вероятностей) точек псевдослучайной последовательности ... ты прав здесь на сто процентов. Но это другой класс задач (кстати для меня лично - более интересный, чем графика), например, некоторых задач поиска экстемума (-мумов) для невыпуклых непараметрических ненепрерывных целевых функций со сложными ограничениями и сложной областью определения переменных функции цели. Но и здесь кое-какие идеи можно использовать
по правильному (как делается в cg методах, где требуется random sampling) - строитcя bounding rectangle и выбирается random точка. если она попала в полигон - done, если нет - то выбирается новая
Задачу равновероятности никто не ставил.
Но если уж на то пошло, то этот способ будет крайне фигово работать в случае звезды с узкими и длинными лучами.
по правильному (как делается в cg методах, где требуется random sampling) - строитcя bounding rectangle и выбирается random точка. если она попала в полигон - done, если нет - то выбирается новая
Задачу равновероятности никто не ставил.
Но если уж на то пошло, то этот способ будет крайне фигово работать в случае звезды с узкими и длинными лучами.
Он говорит об этом, что будет плохо работать.
Но, вообще-то эффективность того алгоритма нисколько не зависит от формы фигуры. Хотя звезда - хороший пример. Эффективность "попадания" внутрь в алгоритме зависит только от соотношения площадей байндинг-бокс Sbox и фигуры Sshape. При любой форме вероятность попадания "внутрь" V = Sshape / Sbox. Если для звезды V = 0.1 - то это означает, что в среднем в статистическом большинстве случаев, мы будем за пределами фигуры в 90 раз из 100. Поэтому и эффективность генерации внутренней точки будет крайне низка. Если на это дело накинуть, что с усложнением фигуры увеличивается число рёбер (с которыми надо будет искать пересечения, чтоб определиться а был ли мальчик) , то алгоритм - вообще труба для таких фигур.
vg писал(а):
Ошибаешься. Он предложил правильное решение. Если считаешь, что решение неправильное, то приведи пример - дай координаты точек многоугольника, для которого бы это не работало, типа
vg писал(а):
Ошибаешься. Он предложил правильное решение. Если считаешь, что решение неправильное, то приведи пример - дай координаты точек многоугольника, для которого бы это не работало, типа
vg писал(а):
Даже Зотин понял, что статистическое распределение здесь ни причём.
ecли нужна ровно одна точка на полигон, тогда - да, согласен, распределение без разницы. если же нужна случайная выборка, то зотинский метод не подходит.
2. "Зотин" - пишется с большой буквы. Тем более, как видать из его и наших постов, он по-умней нас стабой будет, старина.
vg писал(а):
Даже Зотин понял, что статистическое распределение здесь ни причём.
ecли нужна ровно одна точка на полигон, тогда - да, согласен, распределение без разницы. если же нужна случайная выборка, то зотинский метод не подходит.
2. "Зотин" - пишется с большой буквы. Тем более, как видать из его и наших постов, он по-умней нас стабой будет, старина.
