... | ... | @@ -327,7 +327,7 @@ panel.display("Delaunay triangulation"); |
|
|
Given a triangular unstructured 2D mesh and a point p, a very important operation in computational geometry is to find the face f which contains it.
|
|
|
Every following algorithm uses this basic operation multiple times.
|
|
|
A fast implementation is key for fast unstructured mesh generation.
|
|
|
To solve the point location problem different walking strategies, described in [devillers-2001], are implemented:
|
|
|
To solve the point location problem different walking strategies, described in [Devillers et al., 2001](https://hal.inria.fr/inria-00072509/document), are implemented:
|
|
|
|
|
|
- straight walk (default)
|
|
|
- orthogonal walk
|
... | ... | @@ -337,9 +337,9 @@ To solve the point location problem different walking strategies, described in [ |
|
|
|
|
|
Furthermore we implemented different point localization algorithms and data structures:
|
|
|
|
|
|
- Jump and Walk (default) [devroye-2004]
|
|
|
- Delaunay-Tree [guibas-1992]
|
|
|
- Delaunay-Hierarchy [devillers-2002]
|
|
|
- Jump and Walk (default) [Devroye et al., 2004](http://www.sciencedirect.com/science/article/pii/S0925772104000288)
|
|
|
- Delaunay-Tree [Guibas et al., 1992](https://link.springer.com/article/10.1007/BF01758770)
|
|
|
- Delaunay-Hierarchy [Devillers, 2002](https://hal.inria.fr/inria-00166711/document)
|
|
|
- plain walk (no additional strategy),
|
|
|
|
|
|
For a random insertion order of n points, using the Delaunay-Tree or the Delaunay-Hierarchy leads to a time complexity of
|
... | ... | @@ -393,8 +393,8 @@ var triangulation = dT.generate(); |
|
|
|
|
|
### Point removal
|
|
|
|
|
|
The next code snippet removes the first point $p$ of the face located at q = (5.0, 5.0).
|
|
|
We implemented the algorithm presented by Devillers. The following images visualizes the triangulation before and after the removal.
|
|
|
The next code snippet removes the first point p of the face located at q = (5.0, 5.0).
|
|
|
We implemented the algorithm presented by Devillers in [Devillers, 2002](https://hal.inria.fr/inria-00167201/document). The following images visualizes the triangulation before and after the removal.
|
|
|
|
|
|
![tri_removal](uploads/da17611f4915a1dc88a28842b69d6531/tri_removal.png)
|
|
|
|
... | ... | @@ -412,7 +412,7 @@ for example defined by a planar straight line graph (PSLG), have to be part of t |
|
|
We call CDT(V) a constrained Delaunay triangulation of V.
|
|
|
|
|
|
The algorithm we implemented was presented by Sloan: In the first step we compute the Delaunay triangulation for the PSLG G.
|
|
|
In the second step we restore edges of G by edge flips. For more details we refer to [sloan-1993].
|
|
|
In the second step we restore edges of G by edge flips. For more details we refer to [Sloan, 1993](https://doi.org/10.1016/0045-7949(93)90239-A).
|
|
|
|
|
|
## The confirming Delaunay triangulation
|
|
|
|
... | ... | |