Каморка

Старина Зотин писал(а):

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

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

не пройдет. распределение будет не uniform.

по правильному (как делается в cg методах, где требуется random
sampling) - строитcя bounding rectangle и выбирается random точка.
если она попала в полигон - done, если нет - то выбирается новая.
понятно, что чем ближе -гранник к прямоугольнику, тем меньше в
среднем будет итераций ..

Zy писал(а):

ПС. Куда бутылку нести?

Вот и общественность в моем лице это волнует: ты в Тороно, а он в Ванкувере.

А он адрес мне пришлёт почтовый

poneyhot писал(а):

Старина Зотин писал(а):

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

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

не пройдет. распределение будет не uniform.


по правильному (как делается в cg методах, где требуется random
sampling) - строитcя bounding rectangle и выбирается random точка.
если она попала в полигон - done, если нет - то выбирается новая.
понятно, что чем ближе -гранник к прямоугольнику, тем меньше в
среднем будет итераций ..

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

P[0] = {0, 0};
P[1] = {1, 1};
....
P[n] = {cXn, cYn};

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

по правильному (как делается в 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 писал(а): Ошибаешься. Он предложил правильное решение. Если считаешь, что решение неправильное, то приведи пример - дай координаты точек многоугольника, для которого бы это не работало, типа

P[0] = {0, 0};
P[1] = {1, 1};
....
P[n] = {cXn, cYn};

какие точки, товарищ ? ... даже Зотин понял

poneyhot писал(а):

vg писал(а): Ошибаешься. Он предложил правильное решение. Если считаешь, что решение неправильное, то приведи пример - дай координаты точек многоугольника, для которого бы это не работало, типа

P[0] = {0, 0};
P[1] = {1, 1};
....
P[n] = {cXn, cYn};

какие точки, товарищ ? ... даже Зотин понял

не пройдет. распределение будет не uniform.

какое распределение, товарищЪ?

vg писал(а):

не пройдет. распределение будет не uniform.

какое распределение, товарищЪ?

статистическое распределение точек, выбранных способом зотина, по площади полигона

poneyhot писал(а):

vg писал(а):

не пройдет. распределение будет не uniform.

какое распределение, товарищЪ?

статистическое распределение точек, выбранных способом зотина, по площади полигона

1. Отвечаю твоими же словами...

>>> какие точки, товарищ ? ... даже Зотин понял

Даже Зотин понял, что статистическое распределение здесь ни причём.

2. "Зотин" - пишется с большой буквы. Тем более, как видать из его и наших постов, он по-умней нас стабой будет, старина.

vg писал(а): Даже Зотин понял, что статистическое распределение здесь ни причём.

ecли нужна ровно одна точка на полигон, тогда - да, согласен, распределение без разницы. если же нужна случайная выборка, то зотинский метод не подходит.

2. "Зотин" - пишется с большой буквы. Тем более, как видать из его и наших постов, он по-умней нас стабой будет, старина.

ХАХАХА .. шутка года .. "стабой" - nice touch. писчи исчо.

poneyhot писал(а):

vg писал(а): Даже Зотин понял, что статистическое распределение здесь ни причём.

ecли нужна ровно одна точка на полигон, тогда - да, согласен, распределение без разницы. если же нужна случайная выборка, то зотинский метод не подходит.

2. "Зотин" - пишется с большой буквы. Тем более, как видать из его и наших постов, он по-умней нас стабой будет, старина.

ХАХАХА .. шутка года .. "стабой" - nice touch. писчи исчо.

Ок.
- Внимание ... вопрос
А вот скажи, можешь ли ты уточнить - в чём здесь был прикол

(Подсказка - я перечитываю (ред.) свои постинги перед тем, как запостить.)

ПС. Всё это, конечно же, шутка.

ППС. Касательно предмета топика, я уже говорил, что ты прав в части распределения результатов псевдослучайной последовательности.