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

Question

我有 n 3D 空间中的点。我想对所有最近邻距离大于 r 的点的子集进行随机采样.子集的大小m未知，但我希望采样点尽可能密集，即最大化 m .
有类似的问题，但它们都是关于生成点，而不是从给定点采样。
Generate random points in 3D space with minimum nearest-neighbor distance
Generate 3-d random points with minimum distance between each of them?
假设我有 300 个随机 3D 点，

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

获取 m 子集的最快方法是什么？具有最小最近邻距离的点 r = 1同时最大化 m ?

Answer 1

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

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()]))