[SciPy-user] Efficient way of finding the parent element ofapoint in an unstructured triangular

Anne Archibald aarchiba@physics.mcgill...
Fri Dec 5 13:30:02 CST 2008

2008/12/5 Dharhas Pothina <Dharhas.Pothina@twdb.state.tx.us>:

> This is an interesting algorithm, do you have a name or reference for it? One question I have is how you would decide what to use for the size of the uniform grid cells(i.e. dx & dy). I can see that a larger cell size would involve searching through more elements but a cell size which is too small would have the problem of cells that don't contain any nodes.

Actually, I think the idea is, for each cell, you make a list of
triangles that meet the cell. Thus for any point, if you look up the
cell containing that point you get a list of triangles that might
contain it. That way the only time you get an empty list is when your
point is not in any triangle. More generally, you can apply this idea
to any spatial data structure, including kd-trees. Grids have the
advantage that they are simple to implement and quite fast, but
deciding on the grid size can be tricky, and they can suffer badly
from the "teapot in a stadium" problem (where a few big triangles
force big grid cells, but many if the triangles are small and
contained in a single cell). I would recommend using a kd-tree, though
I'm afraid the  ones in scipy.spatial will not be of much use to you.

I should point out that partial as I am to the nearest-neighbor code,
it's not as simple to use for your problem as it seems: the three
vertices of the triangle containing a point need not be the nearest
points in the mesh. In fact there can be as many other mesh points as
you like nearer to your query point than the corners of its triangle.


More information about the SciPy-user mailing list