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

[Anne Archibald]

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

>> 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
>
> I think to make this list I would need to calculate which triangle edges intersect the cell edges. Not sure how expesive that will be. Second way would be to make a list of triangle nodes within a cell and then generate a list of elements that have any of those nodes as edges. If I did the second, I'd have to make the cells large enough to ensure that at least one node was present in each cell (ie cellsize > max triangle size) Looks like these general idea is called a structured auxiliary mesh algorithm.

If you build a kd-tree, it's not too hard to design a recursive algorithm:

build_kdtree(triangles):
    if len_triangles<min_len:
         # min_len should be at least the maximum number of triangles
that meet at a point
         return Leaf(triangles)
    else:
        choose an axis i and a point x from some triangle
        less = [t for t in triangles if at least one point y of t has
y[i]<=x[i]]
        greater = [t for t in triangles if at least one point y of t
has y[i]>=x[i]]
        return KDTree(i,x[i],build_kdtree(less),build_kdtree(greater))

Looking up a point is then easy: walk down the tree until you hit a
leaf, and test the point's membership in each triangle in that leaf.

It's probably not an ideal data structure, since many triangles may
cross the cut plane and therefore be in both subsets, but for
reasonable meshes it's probably fine.

If you want to use a grid, you can test whether a grid cell meets a
triangle reasonably easily: they meet if and only if either some grid
corner is inside the triangle or some triangle corner is in the grid
cell. If you are feeling devious you can possibly even use OpenGL
hardware acceleration to determine which grid cells a triangle falls
into.

Anne