时间戳

首页 > 解决方案 > 在 3D 空间中以最小最近邻距离和最大密度随机采样给定点

python - 在 3D 空间中以最小最近邻距离和最大密度随机采样给定点

问题描述

我n在 3D 空间中有点。我想随机采样所有最近邻距离大于的点的子集r。子集的大小m未知，但我希望采样点尽可能密集，即最大化m。

有类似的问题，但它们都是关于生成点，而不是从给定点采样。
在 3D 空间中生成具有最小最近邻距离的随机点

生成每个点之间距离最小的 3-d 随机点？

假设我有 300 个随机 3D 点，

import numpy as np
n = 300
points = np.random.uniform(0, 10, size=(n, 3))

在最大化时获得m最近邻距离最小的点子集的最快方法是什么？r = 1m

标签： pythonalgorithmnumpyrandomnearest-neighbor

解决方案

可能有一个有效的双准则近似方案，但是当整数规划平均速度如此之快时，为什么还要麻烦呢？

import numpy as np

n = 300
points = np.random.uniform(0, 10, size=(n, 3))

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("SCIP")
variables = [solver.BoolVar("x[{}]".format(i)) for i in range(n)]
solver.Maximize(sum(variables))
for j, q in enumerate(points):
    for i, p in enumerate(points[:j]):
        if np.linalg.norm(p - q) <= 1:
            solver.Add(variables[i] + variables[j] <= 1)
solver.EnableOutput()
solver.Solve()
print(len([i for (i, variable) in enumerate(variables) if variable.SolutionValue()]))

推荐阅读