Abstract
An algorithm for the point-location problem in 2D finite element meshes as a special case of plane straight-line graphs (PSLG) is presented. The element containing a given point P is determined combining a quadtree data structure to generate a quaternary search tree and a local search wave using adjacency information. The preprocessing construction of the search tree has a complexity of O(n · log(n)) and requires only pointer swap operations. The query time to locate a start element for local search is O(log(n)) and the final point search by 'point-in-polygon' tests is independent of the total number of elements in the mesh and thus determined in constant time. Although the theoretical efficiency estimates are only given for quasi-uniform meshes, it is shown in numerical examples, that the algorithm performs equally well for meshes with extreme local refinement.
Original language | English |
---|---|
Pages (from-to) | 49-62 |
Number of pages | 14 |
Journal | Computing (Vienna/New York) |
Volume | 57 |
Issue number | 1 |
DOIs | |
State | Published - 1996 |
Externally published | Yes |
Keywords
- Finite element
- PSLG
- Point location
- Quadtree
- Search wave