0

The task is to calculate the intersection of two bodys in FEM (Cartesian coordinates, i.e. 3D). This translates to the question of finding the minimum distance of all nods (of the mesh) of the first body to all nods (of the mesh) of the second body. Now the problem is that bos are extremely large (find the minimum distance of 80k points in a cloud of 10mio points). The points do not have to be unique.

The brute force approach using the vector-power of numpy would be as follows

import numpy as np
# create random points for bodys A & B
XYZ_A = np.random.rand(4,3)
XYZ_B = np.random.rand(10,3)
LstMinAB = []
for xyz in XYZ_A:
    # calculate distance
    dst = np.linalg.norm(XYZ_B-xyz,axis=1)
    # get minimum index
    idx = np.unravel_index(dst.argmin(), dst.shape)
    # add element to list
    LstMinAB.append( idx[0] )

I read about k-nearest-neighbor (k = 1, in matlab it would be knnsearch) -- but this should still be the brute force approach in a single algorithm. My questions are:

  1. are there more efficient implementations of the brute-force approach, e.g. kNN
  2. is there a way to parallelize this problem?
  3. is there a smarter way to tackle this problem and make use of the fact, that its two solid bodys so the points within one cloud/body are relatively close to each other.

I was checking this post but I am more looking for an practical hints rather than theoretical discussions.

max
  • 3,915
  • 2
  • 9
  • 25
  • What about [`scipy.spatial.KDTree`](https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html)? – Péter Leéh Dec 19 '19 at 08:17
  • You can use Cython implementation of KDtree for performance : `cKDTree`. Implementation details - https://stackoverflow.com/questions/52364222/. – Divakar Dec 19 '19 at 08:19
  • 1
    Also, `scikit` allows parallel jobs with argument `n_jobs` for nearest neighbour. More info - https://scikit-learn.org/stable/modules/neighbors.html#kdtree-and-balltree-classes. scikit one is also listed in the same Q&A. – Divakar Dec 19 '19 at 08:23
  • I was using KDTree just to find nearest neighbors in a matrix and not between two matrices, right? – max Dec 19 '19 at 08:30
  • 1
    You can first build a KDTree for body A. Then for each point in body B, you can query the KDTree for the nearest neighbor in body B. Each query only takes O(logN) time, so the whole thing will take O(NlogN) time. – 9mat Dec 19 '19 at 08:34

0 Answers0