Стохастическая выборка заданных точек в трехмерном пространстве с минимальным расстоянием до ближайшего соседа и максимальной плотностью

Jan 10 2021

У меня есть nточки в трехмерном пространстве. Я хочу стохастически выбрать подмножество точек со всеми расстояниями до ближайших соседей больше, чем r. Размер подмножества mнеизвестен, но я хочу, чтобы точки выборки были как можно более плотными.

Есть похожие вопросы, но все они касаются создания точек, а не выборки из заданных точек.
Создавайте случайные точки в трехмерном пространстве с минимальным расстоянием до ближайшего соседа

Создавать 3-х мерные случайные точки с минимальным расстоянием между каждой из них?

Скажем, у меня есть 300 случайных 3D-точек,

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

Каков самый быстрый способ получить подмножество mточек с минимальным расстоянием до ближайшего соседа r = 1при максимальном m?

Ответы

2 DavidEisenstat Jan 14 2021 at 08:00

Вероятно, существует эффективная схема аппроксимации бикритерией, но зачем беспокоиться, когда целочисленное программирование в среднем выполняется так быстро?

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

Это не оптимально большое подмножество, но должно быть близко, не занимая много времени, используя KDTreeдля оптимизации вычислений расстояния:

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

Итеративное удаление наиболее подключенного узла не является оптимальным (сохраняет около 200 из 300 точек), но, вероятно, это самый быстрый алгоритм, близкий к оптимальному (единственное, что быстрее - это просто случайное удаление). Вы могли @njit reduce_pairsбы сделать эту часть быстрее (попробую, если у меня будет время позже).