Fundamental FE Question

This is a question that has troubled many designers of advanced FE codes. The answer is: you need to set up some kind of global search algorithm such as a kdtree or octree. There is extensive literature on this subject and probably some open source codes, but generally speaking it's not trivial. Also consider the added difficulty of performing such a search in a distributed-memory parallel environment. I would be interested to know what you come up with.

Phil

A somewhat high-handed solution is to use quadtrees. This is useful if the search operation has to be repeated many times.

The idea is to identify (leaf)nodes in the tree that are intersected by triangles in the mesh. It suffices to do this approximately, using bounding boxes for example. This is a one time operation.

Then use the quadtree to localize which elements in the mesh to search.

If the loop over all elements is the primary question, then you could just use bounding boxes to find a certain area where your possible elements lie, and then either use point in polygon test, or use the element's natural coordinate system to check if the point actually lies in the element.

You can find the node closest to your point. Then you can find a patch of elements around that node. Now do a point in a polygon search to find which element from the patch contains your point.