Loading...
Searching...
No Matches
cdt.hpp File Reference

Constrained Delaunay triangulation kernel (workplans/MESH_OVERHAUL_PLAN_2026-09-29.md Stage 4). More...

#include "meshkit/detail/storage.hpp"
#include "meshkit/terrainpolicy.hpp"
#include "meshkit/progress.hpp"
#include <functional>
#include <limits>
Include dependency graph for cdt.hpp:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  meshkit::BasicConstrainedDelaunay< Storage >
 Constrained Delaunay triangulation kernel with quality and terrain refinement and optional coarsening (see the file comment for the algorithms). More...
 
struct  meshkit::BasicConstrainedDelaunay< Storage >::Triangle
 One triangle slot of triangles(). More...
 
struct  meshkit::BasicConstrainedDelaunay< Storage >::QualityOptions
 Options for refineQuality(). More...
 
struct  meshkit::BasicConstrainedDelaunay< Storage >::QualityReport
 Counters and diagnostics of one refineQuality() call. More...
 

Namespaces

namespace  meshkit
 The Qt-free MeshKit library: job events and progress (meshkit::runtime), the neutral mesh model, meshing jobs, the constrained Delaunay kernel and terrain surfaces (meshkit::core), and the MKB and SMS 2DM codecs (meshkit::io).
 

Typedefs

using meshkit::ConstrainedDelaunay = BasicConstrainedDelaunay<detail::StandardStorage>
 Kernel instantiated with standard C++ storage (Point2, Box2, std::string, std::vector-based containers).
 

Detailed Description

Constrained Delaunay triangulation kernel (workplans/MESH_OVERHAUL_PLAN_2026-09-29.md Stage 4).

Author
Caleb Buahin caleb.nosp@m..bua.nosp@m.hin@g.nosp@m.mail.nosp@m..com
Date
2026
License
Apache-2.0

Constrained Delaunay triangulation kernel (workplans/MESH_OVERHAUL_PLAN_2026-09-29.md Stage 4). Replaces Triangle for the mesh generator and for the natural-neighbour interpolator's Delaunay.

  • Incremental insertion in Morton order with walking point location; Lawson flips restore the Delaunay property. Orientation and in-circle tests are Shewchuk's adaptive exact predicates (vendor/predicates), so collinear and cocircular inputs are handled, not guessed.
  • Constraint edges are recovered by flipping the edges that cross them (Sloan 1993); a vertex lying exactly on a constraint splits it there.
  • Regions are the connected components of triangles bounded by constrained edges; removeExterior() drops the component touching the bounding super-triangle, removeRegionAt() drops the one containing a point (a hole seed, a core cell centre).
  • refineQuality() is Delaunay refinement with Ruppert's and Shewchuk's rules (workplans/MESH_TRIANGLE_ENGINE_PLAN_2026-09-30.md ยง4): encroached subsegments are split (concentric shells at acute input corners), bad triangles receive an off-centre or circumcentre, and a point that would encroach a subsegment splits the subsegment instead. The target can remain unmet because of resource caps, numeric limits, fixed edges or the wedge of two segments meeting at a small input angle and next to fixed (unsplittable) edges.

Exact-coordinate duplicate input points map to one vertex; signed zeros coalesce. Vertex ids are stable: input point i is vertex i (after dedup mapping).