Skip to content
Snippets Groups Projects
  1. Feb 20, 2018
    • Christian Engwer's avatar
      [prototype] reimplementation of the insert element algorithm · 1cc6254c
      Christian Engwer authored
      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 provides an alternative implementation of an onther O(N)
      algorithm, based on standard C++ data structures. To speed up the search
      we maintain a hash-map (i.e. unordere_map) from a face to an
      element. Faces are identified by a sorted list of their vertices. When
      we ancounter a face the first time we store the "inside" element in the
      map. When processing the neighbor element at a later stage, we detect
      that the hash-map already contains an entry for this face and
      this (previously inside) element is exactly the required neighbor. Now
      we can safely remove the entry from the map, as we know that a face can
      only the found twice.
      1cc6254c
  2. Feb 19, 2018
Loading