Существует ли эффективный алгоритм генерации случайных точек общего положения на плоскости?

Question

Мне нужно сгенерировать n случайных точек в общем положении на плоскости, то есть никакие три точки не могут лежать на одной прямой. Точки должны иметь координаты, которые являются целыми числами и лежат внутри фиксированного квадрата m x m. Какой будет лучший алгоритм для решения такой проблемы?

Обновление: квадрат выровнен по осям.

Answer 1

Поскольку они являются целыми числами в квадрате, рассматривайте их как точки в растровом изображении. Когда вы добавляете точку после первой, используйте алгоритм Брезенхэма, чтобы нарисовать все пиксели на каждой из линий, проходящих через новую точку и одну из старых. Когда вам нужно добавить новую точку, найдите случайное местоположение и проверьте, ясно ли оно; в противном случае попробуйте еще раз. Поскольку каждая пара пикселей дает новую строку и, таким образом, исключает до m-2 других пикселей, по мере увеличения количества точек у вас будет несколько случайных вариантов, прежде чем вы найдете подходящий. Преимущество подхода, который я предлагаю, заключается в том, что вы платите только за прохождение всех строк, когда у вас есть хороший выбор, а отказ от плохого - очень быстрый тест.

(если вы хотите использовать другое определение линии, просто замените Брезенхем соответствующим алгоритмом)

Answer 2

Аналогично ответу @ LaC.Если с памятью нет проблем, вы можете сделать это следующим образом:

Add all points on the plane to a list (L).
Shuffle the list.
For each point (P) in the list,
   For each point (Q) previously picked,
     Remove every point from L which are linear to P-Q.
   Add P to the picked list.

Вы можете продолжить внешний цикл, пока у вас не будет достаточно точек или не хватит их.

Answer 3

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

Answer 4

Это может просто сработать (хотя может быть немного ограничено случайностью).Найдите самый большой круг, который вы можете нарисовать в квадрате (это кажется очень выполнимым).Выберите любые n точек на окружности, никакие три не будут коллинеарными :-).

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

Редактировать: О, целые числа, только что заметил.Какая жалость.Я собираюсь продолжить это решение, хотя - так как мне нравится идея

Answer 5

Вот статья, которая может решить вашу проблему:

"Наборы точек в общем положении с множеством похожих копий рисунка"

. Автор: BERNARDO M. ABREGO, SILVIA FERNANDEZ-MERCHANT

Answer 6

Оба решения @ LaC и @ MizardX очень интересны, но вы можете объединить их, чтобы получить еще лучшее решение.

Проблема с решением @ LaC заключается в том, что вы получаете случайный выбор, отклоненный.Чем больше очков вы уже заработали, тем сложнее получить новые.Если остается только одна доступная позиция, у вас есть небольшая вероятность случайного выбора ее (1 / (n * m)).

В решении @ MizardX вы никогда не получите отклоненные варианты, однако, если вы непосредственно реализуете "Удалите все точки из L, которые являются линейными по отношению к PQ. "На шаге сложность ухудшится (O (n ^ 5)).

Вместо этого было бы лучше использовать растровое изображение, чтобы найти точки из L, которые нужно удалить.Растровое изображение будет содержать значение, указывающее, может ли точка свободно использоваться и каково ее расположение в списке L, или значение, указывающее, что эта точка уже вычеркнута.Таким образом, вы получите сложность O (n ^ 4) в худшем случае, которая, вероятно, является оптимальной.

РЕДАКТИРОВАТЬ:

Я только что нашел этот вопрос: Генерировать невырожденную точкуУстановить в 2D - C ++ Это очень похоже на это.Было бы хорошо использовать решение из этого ответа Создать невырожденный набор точек в 2D - C ++ .Немного изменив его для использования сортировки по осям или сегментам и добавив все n ^ 2 возможных точек к исходному множеству P и перетасовав его, можно также получить сложность O (n ^ 4) в худшем случае с гораздо более простым кодом.Более того, если пространство - это проблема, а решение @ LaC невозможно из-за требований к пространству, то этот алгоритм просто подойдет без изменений и предложит приличную сложность.

Answer 7

гм, вы не указываете, какую плоскость .., а просто сгенерируйте 3 случайных числа и присвойте x, y и z

если «плоскость» произвольна, то каждый раз устанавливать z = o или что-то в этом роде ...

проверьте x и y, чтобы увидеть, находятся ли они в вашей границе m,

сравните третью пару x, y, чтобы увидеть, находится ли она на той же строке, что и первые два ... если это так, то сгенерируйте случайные значения.