Lấy mẫu các điểm đã cho một cách ngẫu nhiên trong không gian 3D với khoảng cách hàng xóm gần nhất tối thiểu và mật độ tối đa

Jan 10 2021

Tôi có nđiểm trong không gian 3D. Tôi muốn lấy mẫu ngẫu nhiên một tập hợp con các điểm với tất cả các khoảng cách lân cận gần nhất đều lớn hơn r. Kích thước của tập hợp con mlà không xác định, nhưng tôi muốn các điểm được lấy mẫu càng dày đặc càng tốt.

Có những câu hỏi tương tự, nhưng tất cả đều là về việc tạo ra các điểm, thay vì lấy mẫu từ các điểm đã cho.
Tạo các điểm ngẫu nhiên trong không gian 3D với khoảng cách hàng xóm gần nhất tối thiểu

Tạo các điểm ngẫu nhiên 3-d với khoảng cách giữa mỗi điểm là nhỏ nhất?

Giả sử tôi có 300 điểm 3D ngẫu nhiên,

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

Cách nhanh nhất để có được một tập hợp con các mđiểm với khoảng cách nhỏ nhất-láng giềng gần nhất r = 1trong khi tối đa hóa là mgì?

Trả lời

2 DavidEisenstat Jan 14 2021 at 08:00

Có thể có một lược đồ xấp xỉ nhị phân hiệu quả, nhưng tại sao phải bận tâm khi lập trình số nguyên trung bình quá nhanh?

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

Đây không phải là lớn tối ưu của một tập hợp con, nhưng phải gần trong khi không mất nhiều thời gian, sử dụng KDTreeđể tối ưu hóa các tính toán khoảng cách:

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

Loại bỏ lặp đi lặp lại nút được kết nối nhiều nhất không phải là tối ưu (giữ khoảng 200 trong số 300 điểm), nhưng có thể là thuật toán nhanh nhất gần với mức tối ưu (điều duy nhất nhanh hơn là chỉ xóa ngẫu nhiên). Bạn có thể @njit reduce_pairsthực hiện phần đó nhanh hơn (sẽ thử nếu tôi có thời gian sau).