Probieren Sie gegebene Punkte stochastisch in einem 3D-Raum mit minimalem Abstand zum nächsten Nachbarn und maximaler Dichte aus

Jan 10 2021

Ich habe nPunkte in einem 3D-Raum. Ich möchte eine Teilmenge von Punkten stochastisch abtasten, wobei alle Abstände zum nächsten Nachbarn größer als sind r. Die Größe der Teilmenge mist unbekannt, aber ich möchte, dass die abgetasteten Punkte so dicht wie möglich sind.

Es gibt ähnliche Fragen, aber es geht nur darum, Punkte zu generieren, anstatt aus bestimmten Punkten zu stichproben.
Generieren Sie zufällige Punkte im 3D-Raum mit minimalem Abstand zum nächsten Nachbarn

3D-Zufallspunkte mit minimalem Abstand zwischen ihnen generieren?

Angenommen, ich habe 300 zufällige 3D-Punkte.

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

Was ist der schnellste Weg, um eine Teilmenge von mPunkten mit minimalem Abstand zum nächsten Nachbarn zu erhalten und r = 1gleichzeitig zu maximieren m?

Antworten

2 DavidEisenstat Jan 14 2021 at 08:00

Es gibt wahrscheinlich ein effizientes Bicriteria-Approximationsschema, aber warum sollte man sich die Mühe machen, wenn die Ganzzahlprogrammierung im Durchschnitt so schnell ist?

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

Dies ist nicht optimal groß für eine Teilmenge, sollte aber nahe sein, ohne sehr lange zu dauern KDTree, um die Entfernungsberechnungen zu optimieren:

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

Das iterative Entfernen des am meisten verbundenen Knotens ist nicht optimal (behält ungefähr 200 der 300 Punkte bei), ist jedoch wahrscheinlich der schnellste Algorithmus, der nahezu optimal ist (das einzige, was schneller ist, ist das zufällige Entfernen). Sie könnten @njit reduce_pairsdiesen Teil möglicherweise schneller machen (werde es versuchen, wenn ich später Zeit habe).