jdugge / gridtotin Goto Github PK

Implement the quality improvement algorithm described in Shewchuk's Delaunay Refinement Algorithms
for Triangular Mesh Generation

• for each boundary edge (or, more generally, each input edge), check if it is encroached by a vertex (i.e. has a vertex inside its diametral circle)
  • if it does, split the edge in half
• for each triangle, check if it it is skinny (i.e. has a circumradius-to-shortest-edge ratio greater than B)
  • if it is, insert the off-center as a new vertex

• Scan boundary edges
• Check encroachment
• Split edge
• Calculate circumradius-to-shortest-edge ratio
• Find off-center
• Insert off-center

Instead of picking the point that has the greatest discretisation error for insertion, it might lead to better results to pick the point that, upon insertion, leads to the greatest overall improvement. This will be much slower.

• Update global error when inserting a point
• Implement global search for best candidate

Some edges such as shorelines or ridges should be manually enforced in the triangulation, instead of relying on the algorithm to find them.

Implement the algorithm from Shewchuk, J.R. and Brown, B.C., 2015. Fast segment insertion and incremental construction of constrained Delaunay triangulations. Computational Geometry, 48(8), pp.554-574.

The mesh improvement strategies implemented in issue #1 strictly improve the triangle quality, without paying any attention to the discretisation error. It would be desirable if the additional Steiner points could be placed at positions where they reduce the discretisation error in addition to improving the mesh quality.

Two strategies should be implemented:

1. Instead of splitting encroached edges at the midpoint, they should be split at the position along the edge that has the greatest discretisation error, while still eliminating the encroachment.
   • Find valid range along edge 61d8c5b
   • Find greatest discretisation error within valid range 61d8c5b
   • Split encroached edges at optimal point 61d8c5b
2. Steiner points for fixing bad triangles should be inserted at the position with the greatest discretisation error, while still fixing the bad triangle. We'll use the selection disk described in Chernikov and Chrisochoides (2006).
   • Find selection disk 0590702
   • Find greatest discretisation error within selection disk 0590702
   • Insert optimal point 0590702

Chernikov, A.N. and Chrisochoides, N.P., 2006. Generalized Delaunay mesh refinement: From scalar to parallel. In Proceedings of the 15th International Meshing Roundtable (pp. 563-580). Springer Berlin Heidelberg.