Skip to content

reimplementation of the insert element algorithm

Christian Engwer requested to merge feature/prototype-insert-element into master

during element insertion it is necessary to find all face-neighbors of the element. There was an old O(N^2) algorithm which just looped through all exisiting element to find the neighbors. This is prohibitively expensive for large grids. There was an O(N) algorithm which stored a lot of information in some helper data structures to speed up the neighbor search. I didn't understand in detail what it is doing, but I have the impression that it somehow stores the vertex-element relation for all vertices which might still be needed...

This patch implements a prototype of an onther O(N) algorithm, which we can implement in simple way using C++ data structures. To speed up the search we maintain a map from a face to an element. Faces are identified by a sorted list of their vertices. When I ancounter a face the first time I store the "inside" element in the map. When processing the neighbor at a later stage, I detect that the map contains an entry for this face and this (previously inside) element is exactly the required neighbor. Now I can safely remove the entry from the map, as I know that a face can only the found twice.

The current implementation is still not optimal, as we also add boundary faces and these will never be removed from the map. But this doesn't break the algorithm and can be fixed in a proper implementation.

Edited by Christian Engwer

Merge request reports