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

[Dharhas Pothina]

> 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.

The mesh is conforming, has certain quality constraints and the size of the triangles changes gradually so the nearest neighbour approach will probably work most of the time but after sketching some diagrams I can think of cases in which it will not find parent the element. 

> 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. 

I found a paper that summarizes some methods :

http://www.mie.utoronto.ca/labs/bsl/pubs/confpapers/miccai2003_geometricsearch.pdf

- dharhas


>>> "Anne Archibald" <aarchiba at physics.mcgill.ca> 12/5/2008 1:30 PM >>>
2008/12/5 Dharhas Pothina <Dharhas.Pothina at 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.

Anne
_______________________________________________
SciPy-user mailing list
SciPy-user at scipy.org 
http://projects.scipy.org/mailman/listinfo/scipy-user