Échantillonner des points donnés de manière stochastique dans un espace 3D avec une distance minimale du plus proche voisin et une densité maximale

Jan 10 2021

J'ai des npoints dans un espace 3D. Je veux échantillonner de manière stochastique un sous-ensemble de points avec toutes les distances du plus proche voisin supérieures à r. La taille du sous m- ensemble est inconnue, mais je veux que les points échantillonnés soient aussi denses que possible.

Il y a des questions similaires, mais elles concernent toutes la génération de points, plutôt que l'échantillonnage à partir de points donnés.
Générez des points aléatoires dans l'espace 3D avec une distance minimale du plus proche voisin

Générer des points aléatoires en 3D avec une distance minimale entre chacun d'eux?

Disons que j'ai 300 points 3D aléatoires,

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

Quel est le moyen le plus rapide d'obtenir un sous-ensemble de mpoints avec une distance minimale du voisin le plus proche r = 1tout en maximisant m?

Réponses

2 DavidEisenstat Jan 14 2021 at 08:00

Il existe probablement un schéma d'approximation bicritère efficace, mais pourquoi s'embêter quand la programmation en nombres entiers est si rapide en moyenne?

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

1 DanielF Jan 18 2021 at 16:16

Ce n'est pas la taille optimale d'un sous-ensemble, mais devrait être proche sans prendre beaucoup de temps, en utilisant KDTreepour optimiser les calculs de distance:

from scipy.spatial import KDTree
import numpy as np

def space_sample(n = 300, low = 0, high = 10, dist = 1):
    points = np.random.uniform(low, high, size=(n, 3))
    k = KDTree(points)
    pairs = np.array(list(k.query_pairs(dist)))
    
    def reduce_pairs(pairs, remove = []):  #iteratively remove the most connected node
        p = pairs[~np.isin(pairs, remove).any(1)]
        if p.size >0:
            count = np.bincount(p.flatten(), minlength = n)
            r = remove + [count.argmax()]
            return reduce_pairs(p, r)
        else:
            return remove
    
    return np.array([p for i, p in enumerate(points) if not(i in reduce_pairs(pairs))])

subset = space_sample()

La suppression itérative du nœud le plus connecté n'est pas optimale (conserve environ 200 des 300 points), mais c'est probablement l'algorithme le plus rapide qui est proche de l'optimum (la seule chose plus rapide étant simplement de supprimer au hasard). Vous pourriez éventuellement @njit reduce_pairsrendre cette partie plus rapide (j'essaierai si j'ai le temps plus tard).