使用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中添加了一个。