Мне нужно создать n случайных точек в общем положении на плоскости, т.е. три точки не могут лежать на одной и той же линии. Точки должны иметь координаты, которые являются целыми числами и лежат внутри фиксированного квадрата m x m. Каким будет лучший алгоритм для решения такой проблемы?
Обновление: квадрат выровнен с осями.
Невозможно увидеть способ проверки каждой точки, когда вы ее добавляете, либо путем (а) пробега по всем возможным линиям, на которые она может быть, либо (б) устранением конфликтующих точек по мере продвижения, чтобы уменьшить возможное местоположения для следующего пункта. Из двух, (б) кажется, что это может дать вам лучшую производительность.
Поскольку они являются целыми числами в квадрате, рассматривайте их как точки в растровом изображении. Когда вы добавляете точку после первого, используйте алгоритм Брешенема, чтобы нарисовать все пиксели на каждой из строк, проходящих через новую точку, и одну из старых. Когда вам нужно добавить новую точку, найдите случайное местоположение и проверьте, очищено ли оно; в противном случае повторите попытку. Поскольку каждая пара пикселей дает новую строку и, таким образом, исключает до m-2 других пикселей, так как количество точек увеличивается, у вас будет несколько случайных вариантов, прежде чем вы найдете хороший. Преимущество подхода, который я предлагаю, заключается в том, что вы платите только стоимость прохождения всех строк, когда у вас есть хороший выбор, а отказ от плохого - очень быстрый тест.
(если вы хотите использовать другое определение строки, просто замените Bresenham на соответствующий алгоритм)
Как и для ответа @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.
Вы можете продолжить внешний цикл до тех пор, пока у вас не будет достаточно очков или не закончите их.
Это может сработать (хотя может быть немного ограничено случайностью). Найдите самый большой круг, который вы можете нарисовать в квадрате (это кажется очень выполнимым). Выберите любые n точек на круге, ни один из трех не будет коллинеарным:-).
Это должно быть достаточно простой задачей в коде. Скажем, что окружность центрирована по происхождению (поэтому что-то вида x ^ 2 + y ^ 2 = r ^ 2). Предполагая, что r фиксировано и x генерируется случайным образом, вы можете решить найти координаты y. Это дает вам две точки на окружности для каждого x, диаметрально противоположного. Надеюсь, это поможет.
Изменить: О, целые точки, только что заметил. Какая жалость. Я собираюсь сохранить это решение, хотя, поскольку мне нравится идея
Оба решения @LaC и @MizardX очень интересны, но вы можете комбинировать их, чтобы получить еще лучшее решение.
Проблема с решением @LaC заключается в том, что вы произвольно отклоняете выбор. Чем больше очков вы уже создали, тем сложнее получить новые. Если осталось только одно доступное положение, у вас есть небольшая вероятность случайного выбора его (1/(n * m)).
В решении @MizardX вы никогда не получаете отклоненные варианты, однако, если вы непосредственно реализуете "Удалить каждую точку из L, которая является линейной для P-Q". шаг вы получите худшую сложность (O (n ^ 5)).
Вместо этого было бы лучше использовать растровое изображение, чтобы найти, какие точки из L должны быть удалены. Растровое изображение будет содержать значение, указывающее, является ли точка свободной для использования, и каково ее местоположение в списке L или значение, указывающее, что эта точка уже вычеркнута. Таким образом, вы получаете наихудшую сложность O (n ^ 4), которая, вероятно, оптимальна.
EDIT:
Я только что нашел этот вопрос: Создать невырожденную точку в 2D - С++ Это очень похоже на это. Было бы неплохо использовать решение из этого ответа Создать невырожденный набор точек в 2D - С++. Изменив его немного, чтобы использовать сортировку радиуса или ведра и добавив сначала все n ^ 2 возможных точек в P, и перепутывая их, можно также получить худшую сложность O (n ^ 4) с гораздо более простым кодом. Более того, если пространство является проблемой, а решение @LaC нецелесообразно из-за требований к пространству, то этот алгоритм будет просто вписываться без изменений и обеспечить достойную сложность.
Вот документ, который может решить вашу проблему:
"POINT-SETS В ОБЩЕМ ПОЛОЖЕНИИ С МНОГИМ СХОДНЫЕ КОПИИ ИЗОБРАЖЕНИЯ "
by BERNARDO M. ABREGO AND SILVIA FERNANDEZ-MERCHANT
um, вы не укажете, какую плоскость... но просто сгенерируете 3 случайных числа и назначьте x, y и z
если "плоскость" произвольна, тогда задайте z = o каждый раз или что-то еще...
выполните проверку на x и y, чтобы увидеть, находятся ли они на вашей границе m,
сравните третью пару x, y, чтобы увидеть, находится ли она в той же строке, что и первые две... если она есть, а затем восстановить случайные значения.