Common nodes in two FEM grids

Question

There are two independent tetrahedral FEM grids. Second grid is subset of the first. By subset, I mean: nodes from the second grid are exactly in the same positions as some nodes from the first grid. The numbering of nodes is completely different in both grids. I need to renumber nodes from the second grid according to nodes from first one to properly transfer the solution. To do it I need to create some kind of map between nodes ids. Most naive solution is to create a dictionary where the keys contain nodes positions and value is node 'id'. But using arrays of doubles as a keys is not a great idea due to floating point math (precision issue).

Answer 1

Hashing floating-point numbers can indeed lead to weird results, especially if the node positions can be perturbed by some small amount or if there are denormalized values.

You included the Python tag, so I assume that's what you're using and that you have scipy. A quick and dirty solution would be to construct a kd-tree of the fine grid points, then for each point in the coarse grid, compute its nearest neighbor in the fine grid. This will work in $O(n \log n)$ rather than the $O(n^2)$ of a naive nested loop, without the issues of floating-point weirdness. There may be a faster way to do the same thing, but in these applications you very often need a spatial tree data structure in the first place.