ตัวอย่างจุดที่กำหนดอย่างสุ่มในพื้นที่ 3 มิติโดยมีระยะห่างใกล้เพื่อนบ้านต่ำสุดและความหนาแน่นสูงสุด

Jan 10 2021

ฉันมีnคะแนนในพื้นที่ 3 มิติ ฉันต้องการที่จะ stochastically rลิ้มลองเซตของจุดที่มีทั้งหมดในระยะทางที่ใกล้ที่สุดเพื่อนบ้านขนาดใหญ่กว่า mไม่ทราบขนาดของชุดย่อยแต่ฉันต้องการให้จุดตัวอย่างมีความหนาแน่นมากที่สุด

มีคำถามที่คล้ายกัน แต่ทั้งหมดเกี่ยวกับการสร้างคะแนนมากกว่าการสุ่มตัวอย่างจากจุดที่กำหนด
สร้างจุดสุ่มในพื้นที่ 3 มิติโดยมีระยะห่างใกล้เพื่อนบ้านน้อยที่สุด

สร้างจุดสุ่ม 3 มิติโดยมีระยะห่างต่ำสุดระหว่างแต่ละจุด?

สมมติว่าฉันมีคะแนน 3 มิติแบบสุ่ม 300 คะแนน

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ทำให้ส่วนนั้นเร็วขึ้นได้ (จะพยายามถ้ามีเวลาในภายหลัง)