使用CGAL python綁定查詢三角形上的最近點

Question

這個CGAL python binding example非常適合展示如何使用AABB樹來獲得三角湯上最近的點。不幸的是，它只返回最近三角形上的單個最近點。

我正在尋找一個函數，我可以提供一個查詢點（s），一個三角形數組，然後得到每個三角形的最近點作爲返回。

我發現做到這一點的唯一方法是通過遍歷一次三角形之一，做出AABB_tree_Triangle_3_soup每個和查詢......這感覺非常低效的，特別是因爲example顯然可以處理的數組三角形一次。

爲了說明這一點，這裏有一個像我正在尋找：

紅點查詢點，每個藍點是三角形的頂點，綠點是最接近因爲它是投影，因此每條線都有點。

這是我想出的代碼。代碼有效，但不是很漂亮。

# Imports 
import time 
import numpy as np 
from scipy.spatial import cKDTree 

from CGAL.CGAL_Kernel import Point_3 
from CGAL.CGAL_Kernel import Triangle_3 
from CGAL.CGAL_AABB_tree import AABB_tree_Triangle_3_soup 

# Setup the source data 
# --------------------- 

# Create large numpy array of triangles 
N_TRIANGLES = 100000 #100K triangles 
np_triangles = np.random.random_sample((N_TRIANGLES,3,3,)) # lets make a random array for this example 

# Create a random query point 
np_query = np.random.random_sample((3,)) * 100 # lets use a random point for this example 

# Convert the data so we can use CGAL 
cgal_triangles = [] 
for p in np_triangles: 
    a = Point_3(p[0][0],p[0][1],p[0][2]) 
    b = Point_3(p[1][0],p[1][1],p[1][2]) 
    c = Point_3(p[2][0],p[2][1],p[2][2]) 
    cgal_triangles.append(Triangle_3(a,b,c)) 

cgal_query = Point_3(np_query[0],np_query[1],np_query[2]) 



# Test begins! 
# ------------ 

# If all i care for is to find THE closest point on all the given triangles to the query point, it's easy: 
def simple_closest(): 
    tree = AABB_tree_Triangle_3_soup(cgal_triangles) 
    cp = tree.closest_point(cgal_query) 
    return np.array([cp.x(),cp.y(),cp.z()]) 

simple_closest_result = simple_closest() 


# Unfortunately, what i want is a return value for all given triangles, which i could sort in the future for N closest if need be 
# The only way i found to do this is to make an AABB tree per triangle, which sounds silly, and is the focus of my question 
def all_closest(): 
    cp = [] 
    for t in cgal_triangles: 
     tree = AABB_tree_Triangle_3_soup([t]) 
     p = tree.closest_point(cgal_query) 
     cp.append([p.x(),p.y(),p.z()]) 

    return np.array(cp) 

all_closest_result = all_closest() 


# From here, if i wish to sort the results to get all the points from closest to furthest, i can do that 
N = 8 # Lets say i want the 8 closest triangles to the query point 
n = max(min(N, N_TRIANGLES), 1) # clamp n <= tri count 


def n_closest(): 
    kdTree = cKDTree(all_closest_result) 
    q = kdTree.query(np_query,k=n) 
    return all_closest_result[q[1]], q[0], q[1] 

n_closest_result = n_closest() 


print '' 
print 'Does the closest item match: %s'%np.allclose(n_closest_result[0][0],simple_closest_result) 
print 'Closest Simple:\n%s'%simple_closest_result 
print '%s closest'%n 
print n_closest_result[0] 

這個例子顯示了我必須一次遍歷三角形。爲每個三角形創建一個AABB_tree_Triangle_3_soup，然後查詢。這聽起來非常低效。特別是在處理許多許多查詢時，例如100萬個三角形列表的100k查詢。

所以，我正在尋找的是比我的迭代方法更好的方法。希望一個命令，如：

樹= AABB_tree_Triangle_3_soup（三角形） tree.all_points（查詢）＃返回未排序的最接近點 tree.all_closest（查詢，N = 56）＃返回56個最近點

Answer 1

您需要使用其他軟件包（Spatial searching）。我注意到在綁定中使用這個包的唯一例子是java。我在python中添加了一個。