Исключение прямоугольной области при выборе случайного значения на двумерной сетке

[Alex7wrt]

Есть прямоугольная область (x,y от нуля до некоторых значений), внутри которой еще одна прямоугольная область с известными координатами углов. Каким образом исключить ее из рассмотрения для того, чтобы с помощью генератора случайных чисел можно было относительно легко получить координаты произвольной точки?

 

То есть пусть например в исходной области макс. x. равен xmax, а макс. y ymax. Тогда, если бы не было внутренней области, можно было просто написать x=random(xmax+1), y=random(ymax+1). 

 

Лобовым решением является простое разделение оставшейся от вырезания области на 8 частей, каждая из которых прямоугольная и в ней обычным рандомом находить точку. Для выбора одной из 8-ми областей тоже использовать рандом.

 

Но вдруг есть более изящные и простые решения?

Изменено 28 апреля, 2015 пользователем Alex7wrt

[Вячеслав]

Как вариант, сначала сгенерируйте координаты, а потом проверьте их на вхождение в "запрещенную область". Если точка не попала в область, то все в порядке. Если попала, то генерируем новые координаты. У TRectangle даже готовый метод есть.

Правда, данный подход будет работать не самым оптимальным образом, особенно, если размер "запрещенной области" сопоставим с размером всей области возможных значений. Но при современных скоростях процессоров, это может быть вообще несущественно.

[Alex7wrt]

Спасибо, что откликнулись. Но Вы правильно написали, что это медленный вариант и использовать его не хочется. Так как размеры вырезаемой области могут составлять и 90% от исходной. 

Хотелось бы какой-нибудь способ, в котором процедура random использует что-то типа кусочного интервала.

Изменено 27 апреля, 2015 пользователем Alex7wrt

[Вячеслав]

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

Область значений Х состоит из двух областей (I) и (III). При этом Х может принимать значение либо из первой области, либо из второй [строчка (1)]

Определяем переменную FLAG, которая может быть только или нулем, или единицей [строчка (2)].

Теперь через нее нетрудно выразить уравнение для Х [строчка (3)]

 

Сейчас под рукой нет Delphi, поэтому проверить не могу. Но идея, надеюсь, понятна.

[Alex7wrt]

Большое спасибо! Наверное, это действительно лучший вариант, хоть и в двумерном случае придется вводить еще две случайных величины. Но это однозначно намного лучше деления области на 8 частей.

P.S. За мат. пример отдельное спасибо!!! Одновременно и стыдно за себя, и вдохновляет больше работать мозгами. ))

Изменено 27 апреля, 2015 пользователем Alex7wrt

[Вячеслав]

Всегда пожалуйста! Люблю такого рода задачки)

[Brovin Yaroslav]

Еще есть вариант на одномерном примере. 

 

Идея ввести параметр, который будет принимать случайное значение от 0 до суммы двух отрезков. Потом проверять, Если параметр попадает в первый отрезок по длине, то добавляем начальную координату отрезка. Если во второй, то добавляем начальную координату второй части. 

 

[Alex7wrt]

Тоже хороший вариант. Спасибо!

[Alex7wrt]

Итого для 2-мерного случая получаем следующее:

 

randomize;

a:=random(2); b:=random(3)+1;

x:=random(x2-x1+1)+x1; y:=random(ymax-ymin)+ymin;

 

case b of

    1: x:=random(x1-xmin)+xmin;

    2: y:=a*(random(y1-ymin)+ymin)+(1-a)*(random(ymax-y2)+y2+1);

    3: x:=random(xmax-x2)+x2+1;

end;

Изменено 28 апреля, 2015 пользователем Alex7wrt

[voytalexey]

Маленькое замечание: варианты Вячеслава от 01:45 и Alex7wrt от 23:42 дают неравномерное распределение.случайных точек. Вариант Brovin Yaroslav от 15:33 даёт равномерное распределение.

[Alex7wrt]

Маленькое замечание: варианты Вячеслава от 01:45 и Alex7wrt от 23:42 дают неравномерное распределение.случайных точек. Вариант Brovin Yaroslav от 15:33 даёт равномерное распределение.

Спасибо за замечание! Я так понимаю, это из-за разных размеров областей. То есть, чтобы использовать этот метод с равномерным распределением нужно указывать не равную вероятность для каждого случая, а как соотношение размеров этих областей?

Если я Вас правильно понял, то в целом для моих задач это не принципиально, но стоит иметь ввиду.

Изменено 28 апреля, 2015 пользователем Alex7wrt