ISSN:
1436-5057
Keywords:
68P10
;
Point location
;
quadtree
;
search wave
;
finite element
;
PSLG
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Es wird ein Algorithmus zur Punktlokation in einem 2D Finite-Element-Netz als Spezialfall eines ebenen straight-line Graphen (PSLG) vorgestellt. Das einen gegebenen Punkt P enthaltende Element wird durch die Kombination einer Quadtree-Suche und einer lokalen Suchwelle unter Berücksichtigung von Nachbarschaftsinformationen gefunden. Die Komplexität des Aufbaus des Suchbaums istO(n· log(n)) und benötigt nur Pointer-Swap-Operationen. Die Query-Zeit zur Identifikation des Startelements für die lokale Suche istO(log(n)) und die abschließende Punkt-Suche mit ‘Punkt-in-Polygon-Tests’ ist unabhängig von der Gesamtzahl der Elemente und damit in konstanter Zeit durchzuführen. Obwohl die theoretischen Effizienzabschätzungen nur für quasi-uniforme Netze gegeben werden, wird an numerischen Beispielen gezeigt, daß der Algorithmus ebenso effektiv bei Netzen mit extremer lokaler Verfeinerung arbeitet.
Notes:
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 ofO(n·log(n)) and requires only pointer swap operations. The query time to locate a start element for local search isO(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 refenement.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238357
Permalink
