根据距离连接到 2d numpy 数组中的随机点

Question

我有一个 2d numpy 数组和 select 一个随机坐标位置（比如说 10x10 数组，从位置 2,3 开始）。我想随机连接到 2d 数组中其他点的 40%，有效地生成一个元组列表 [(x1, y1), (x2, y2) ...]，其中列表是其他坐标的 40%。
然而，另一个约束是目标是降低连接概率，点之间的距离越远（因此点 2,3 比 9, 8 更有可能连接到 2,2 但仍然是随机的，所以有连接到 9、8 的机会虽然很小）。

我认为我需要创建某种以 2,3 为中心的高斯函数并将其用于 select 点，但我创建的任何高斯函数都会生成非整数值 - 还需要额外的逻辑as 提出了需要分别处理 x 和 y 维度的问题。

目前，我正在尝试将 np.meshgrid 与高斯 = np.exp(-(dst2 / (2.0 * sigma2)))

是否有更简单的方法或有人可能推荐的不同方法？

Answer 1

这个问题很适合rejection sampling。基本上你随机选择一个点，然后 select 是否应该根据定义的概率建立连接。你必须考虑到在更远的距离比#更近的距离有更多的点（它的数量随着半径增加），所以你可能必须在概率函数中引入额外的权重。在这种情况下，我选择使用指数衰减概率。

这段代码在速度方面不是最优的，特别是对于更高的连接百分比，但这种方式更好地表达了想法：请参阅下文以获得更好的选择。

import numpy as np
from numpy.random import default_rng

rng = default_rng()
board = np.zeros((100, 100), dtype=bool)
percent_connected = 4
N_points = round((board.size - 1) * percent_connected/100)
center = np.array((20, 30))
board[tuple(center)] = True # remove the center point from the pool
dist_char = 35  # characteristic distance where probability decays to 1/e

endpoints = []
while N_points:
    point = rng.integers(board.shape)
    if not board[tuple(point)]:
        dist = np.sqrt(np.sum((center-point)**2))
        P = np.exp(-dist / dist_char)
        if rng.random() < P:
            board[tuple(point)] = True
            endpoints.append(point)
            N_points -= 1
board[tuple(center)] = False # clear the center point

# Graphical test
import matplotlib.pyplot as plt

plt.figure()
for ep in endpoints:
    plt.plot(*zip(center, ep), c="blue")

稍微快一点的方法在更高的连接性下更快：

rng = default_rng()
board = np.zeros((100, 100), dtype=bool)
percent_connected = 4
N_points = round((board.size - 1) * percent_connected/100)
center = np.array((20, 30))
board[tuple(center)] = True # remove the center point from the pool
dist_char = 35  # characteristic distance where probability decays to 1/e
flat_board = board.ravel()
endpoints = []
while N_points:
    idx = rng.integers(flat_board.size)
    while flat_board[idx]:
        idx += 1
        if idx >= flat_board.size:
            idx = 0
    if not flat_board[idx]:
        point = np.array((idx // board.shape[0], idx % board.shape[0]))
        dist = np.sqrt(np.sum((center-point)**2))
        P = np.exp(-dist / dist_char)
        if rng.random() < P:
            flat_board[idx] = True
            endpoints.append(point)
            N_points -= 1
board[tuple(center)] = False # clear the center point


plt.figure()
for ep in endpoints:
    plt.plot(*zip(center, ep), c="blue")

根据距离连接到 2d numpy 数组中的随机点

Connecting to random points in a 2d numpy array based on distance

python

arrays

random

numpy