Блог

У меня есть начальная координата (x1, y1) и конечная координата (x2, y2). Я хочу сгенерировать ‘n’ случайных точек между начальными и конечными координатами без каких-либо дубликатов. Как это сделать с помощью Python?

Я знаю, что простым способом было бы сгенерировать ‘n’ значений x и ‘n’ значений y. Итак, мы получаем n * n пар, и я выбираю ‘n’ среди них без дубликатов. Таким образом, я не могу получить равномерное распределение случайных точек. Есть другой способ сделать это?

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

TL; DR:

 from random import uniform


def gen_coords(x1, y1, x2, y2, n):
    result = set()
    # loops for each addition, avoiding duplicates
    while len(result) < n:
        result.add((uniform(x1, x2), uniform(y1, y2)))
    return result
  

Возможно, практически:

 from random import uniform


def gen_coords(x1, y1, x2, y2, n):
    return [(uniform(x1, x2), uniform(y1, y2)) for _ in range(n)]
  

Учитывая, что вероятность столкновений невелика.

Предполагая, что «между начальными и конечными координатами» означает прямоугольное сечение между этими двумя углами в декартовой системе координат (т. Е. плоское, 2D).

И предполагая, что «равномерное распределение» достигается в достаточной степени, игнорируя неравномерное распределение значений с плавающей запятой. (т. Е. Не одинаковое количество значений с плавающей запятой на любом интервале равной длины и не постоянное расстояние между значениями с плавающей запятой в континууме)

В основном существует три способа обеспечения того, чтобы случайно сгенерированные точки не дублировались:

1. выберите их из набора возможных значений, удалив каждый выбор, чтобы избежать повторного выбора;
2. генерируйте значения в пределах допустимого пространства, сверяя каждый выбор с предыдущими выборками, чтобы избежать добавления дубликатов (и повторного выбора значений до тех пор, пока не будет сгенерировано новое).;
3. генерируйте значения и добавляйте к набору до достижения желаемого размера набора, удаляя дубликаты после генерации, если таковые имеются, и повторяя процесс до завершения.

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

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

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

В качестве варианта второго выбора вы могли бы выбрать целевую структуру данных, которая просто полностью исключает добавление дубликатов, полагаясь на язык / интерпретатор для выполнения проверки более эффективно, чем это мог бы сделать любой алгоритм, написанный на этом языке.

В Python это означает использование set вместо list , что является самым быстрым способом достижения результата и, вероятно, в любом случае будет способом проверки дубликатов в третьем варианте — так что вы можете использовать его сразу и перейти к варианту второго варианта.

Обратите внимание, что как 2-й, так и 3-й варианты имеют серьезный недостаток в случае, если вы пытаетесь создать набор в диапазоне функции выбора, который больше, чем домен функции выбора. Но для данной проблемы это маловероятно, за исключением чрезвычайно большого ‘n’.

Решение (противопоставление второго варианта третьему):

 from random import uniform
from timeit import timeit


def pick_coords_restricted(x1, y1, x2, y2, n):
    result = set()
    # loops for each addition, avoiding duplicates
    while len(result) < n:
        result.add((uniform(x1, x2), uniform(y1, y2)))
    return result


def pick_coords_checked(x1, y1, x2, y2, n):
    result = []
    # loops once for attempt, checking after each iteration
    while len(set(result)) < n:
        if len(result) > 0:
            result = list(set(result))
            result  = [(uniform(x1, x2), uniform(y1, y2)) for _ in range(n - len(result))]
        else:
            result = [(uniform(x1, x2), uniform(y1, y2)) for _ in range(n)]
    return result


print(timeit(lambda: pick_coords_restricted(0, 0, 1, 1, 1000), number=10000))
print(timeit(lambda: pick_coords_checked(0, 0, 1, 1, 1000), number=10000))
  

Результат (на моем оборудовании):

 4.3799341
3.9363368000000003
  

Я получаю последовательные, но незначительно лучшие результаты для pick_coords_checked функции — я бы предпочел ясность первой реализации.