artem-ogre / cdt Goto Github PK

I'm very happy with a stability and overall performance of CDT, great job!
The only one pitfall I'm suffering from is a performance of eraseSuperTriangle().
Looks like its time complexity grows quadratically with number of triangles it actually has to remove.
I think it's worth looking into it for optimization possibilities.

Please find below my experiment results:
My 'malicious' data set is many many points spread along X axis (x=[+1..-1], y=0), and 1 point just tiny bit above them all (x=0, y=1.E-15).

100K points:

• triangulation: 0.7s,
• eraseSuperTriangle: 0.9s

1M points:

• triangulation: 3.4s,
• eraseSuperTriangle: 125s !

10M points:

• triangulation: 35s,
• eraseSuperTriangle: 10200s !!!

Please, leave a contact in order to obtain a license on your code in commercial purposes.

Discussed in #54

Trying to do this sample:

std::vector<CDT::V2d<float>> verticies = { { 0, 0 }, { 100, 0 }, { 100, 100 }, { 50, 50 }, { 0, 100 } };
std::vector<CDT::Edge> edges = { { 0, 4 }, { 0, 1 }, { 1, 2 }, { 3, 4 } };

CDT::Triangulation<float> triangulation(CDT::VertexInsertionOrder::AsProvided);
triangulation.insertVertices(verticies);
triangulation.insertEdges(edges);
triangulation.eraseOuterTriangles();

Expecting something like this

 __
|  |
|/\|

And getting empty triangles list... What's wrong? Please help :)

The current random shuffling that's enabled by default declares a static mt19937 randGenerator(9001) in Triangulation.h. By declaring the variable as static, this has two main effects:

1. The variable will be shared across threads. This means that performing multiple Delaunay operations across different threads will interfere with the shuffling, and in worst case could break the random number distribution in the generator as the state is updated unsafely.
2. A separate instance will be created in each .cpp file that includes Triangulation.h. If this happens in multiple .cpp files in a library, I'm not quite sure what would happen when the linker removes duplicate template instantiations that refer to the randGenerator object.

One option is to avoid a global object and create a stack object instead. Given that you're re-seeding randGenerator each time this would have the same performance. randGenerator will be ~2.5 KB for its internal state, but this cost could be mitigated by moving the instance to the random_shuffle() function so it's popped off the stack before any recursive operations occur.

A couple other things worth noting:

• The usage of randGenerator() % (i + 1) introduces bias. For this usage it probably doesn't really matter, but uniform_int_distribution would avoid any biasing. The implementation may change between systems, though, so an argument could be made to leave it as-is if you wish to keep the behavior truly repeatable. (or use one of these simple implementations, the "Debiased Modulo (Once)" method seems to be a good compromise between simplicity and speed)
• Initializing Mersenne twister is quite expensive. I could see this constant cost becoming a factor for someone performing Delaunay on many small meshes. The available list of generators in the STL is unfortunately a bit behind the times, but today it's possible to have a non-garbage generator without the massive state of Mersenne twister. Some options are analyzed on this page, and given that you're only using a single seed for one operation SplitMix64 would be trivial to integrate and should have well distributed results while only using a single 64-bit number.

I'm having an issue with processing a shape that contains a single hole - The shape and hole have defined edges. However, when I proceed to insertEdges I get a runtime error at the close of intersectedTriangle

code:

Triangulation cdt = Triangulation(CDT::FindingClosestPoint::ClosestRandom, 10);
cdt.insertVertices(edgeVertsF[i]);
cdt.insertEdges(edges[i]);
cdt.eraseOuterTrianglesAndHoles();

data:
https://pastebin.com/aq4eXVA8

I've ensured that there are no duplicate points, and the edges reference the appropriate points. The only thing I haven't done is order/separate the outer and inner edges.

Using Visual Studio 2019 and CDT as header only.

Looks like something has gone wrong when generating the docs.

Ciao, the attached file fails to remove the outer boundary.
CDTTessellationBoundsNotScaled (2).txt

Such a cool library, unfortunately only for 2D. Can't be generalized to 3D easily?

Hi,

Can you add some checks for the function that use random shuffling dependent on C++ version? The one you use is only compatible till C++14.

Hello, I successfully created CDT using the following methods, but there are many bad triangles in result (flat triangle),
which cause an error " In initialize: Triangulation is invalid" when I use "LinearTriInterpolator" method from python matploblib library.

So, my question is, how can I remove the bad shape triangles in CDT?

cdt.insertVertices(vertices);
cdt.insertEdges(edges);
CDT::RemoveDuplicatesAndRemapEdges(vertices, edges); // remove duplicate
cdt.eraseSuperTriangle(); 

When using the code.

#include "CDT.h"
CDT::Triangulation cdt;
cdt.insertVertices(/* points /);
cdt.eraseSuperTriangle();
/ access triangles / = cdt.triangles;
/ access vertices / = cdt.vertices;
/ access boundary edges */ = cdt.edges;

edges is not a member of CDT::Triangulation.

For few not so trivial cases (actually pretty extreme ones), I'm getting stack overflow exception from insertEdge() call.
There are many many CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::triangulatePseudopolygon
calls on the stack causing this. That would be great if refactoring this recursion into a pseudo-recursion loop would be possible.
I'm on Win10, VS22. Problem should be reproducible with something like:

#include <random>
#include "CDT.h"

#define POINTS 1000000
#define EDGES 10000
std::random_device rd{};
std::mt19937_64 gen{rd()};
std::gamma_distribution<double> d(0.1,2.0);
std::vector<CDT::V2d<double>> verts;
for (int i = 0; i < POINTS; i++)
{
  CDT::V2d<double> v;
  v.x = d(gen) - 5.0;
  v.y = d(gen) - 5.0;
  verts.push_back(v);
}

std::vector<CDT::Edge> edges;
for (int c = 0; c < EDGES; c++)
{
  int from = rand()%POINTS;
  int to = (from + 1 + rand() % (POINTS - 1)) % POINTS;
  CDT::Edge e{ (size_t)from, (size_t)to };
  edges.push_back(e);
}

CDT::RemoveDuplicatesAndRemapEdges(verts,edges);

CDT::Triangulation<double> cdt;
cdt.insertVertices(verts);
cdt.insertEdges(edges);  // here it occurs
cdt.eraseSuperTriangle();

EDIT: Enlarging stack reserve size in linker (from a default of 1MB) to 10MB resolves the issue (for 1M verts and 10K edges).

Hello,

This is an elevated Delaunay triangulation (also called 2.5D Delaunay triangulation):

It would be nice to have this feature. I personally do it by performing a 2D Delaunay triangulation of the (x,y)-coordinates of the points and then I add the z-coordinate, but it's possible that better strategies exist.

thanks for providing really great library!

I tried several things to figure out how to use it.
However, I found that your library can't generate any triangle if at least one outer boundary edge (surrounding each point) is missing.
For example, in the below example, if I remove one of the edges, there's no triangle anymore..

Then my question is,

Q1. Does your library not support creating a mesh with only points?

Q2. If your library needs all the boundary edges, how do we know in advance?

(refered from #5 (comment))

#include <iostream>
#include "CDT.h"
#include "VerifyTopology.h"
#include "CDTUtils.h"

using Triangulation = CDT::Triangulation<float>;
typedef CDT::V2d<double> Vertex;
typedef CDT::Edge Edge;


int main() {
    std::cout << "Hello, World!" << std::endl;

   
    CDT::Triangulation<double> cdt;
    std::vector< Vertex > vertices;
    std::vector<Edge> edges;


    //point0
    vertices.push_back({-1,0});
    //point1
    vertices.push_back({1,0});
    //point2
    vertices.push_back({1,1});
    //point3
    vertices.push_back({0.5,1});
    //point4
    vertices.push_back({0.5,2});
    //point5
    vertices.push_back({-0.5,2});
    //point6
    vertices.push_back({-0.5,1});
    //point7
    vertices.push_back({-1,1});
    //point8
    vertices.push_back({0.75,0.5});


    cdt.insertVertices(pts);



    edges.push_back(Edge(0, 1));
    edges.push_back(Edge(1, 2));
    edges.push_back(Edge(2, 3));
    edges.push_back(Edge(3, 4));
    edges.push_back(Edge(4, 5));
    edges.push_back(Edge(5, 6));
    edges.push_back(Edge(6, 7));
    edges.push_back(Edge(7, 0));
    cdt.insertEdges(edges);
    cdt.eraseOuterTriangles();


    std::cout<<cdt.triangles.size()<<std::endl;

    return 0;
}

https://user-images.githubusercontent.com/7488293/79947196-d0f35400-8471-11ea-9c17-0400d289bfbf.png

Recently I have been evaluating constrained Delaunay triangulation libraries and have stumbled onto this gem. During my testing of this tool I have encountered one triangulation where I believe is not the desired output but due to having the super-triangle being too small for the point cloud. Here is the point cloud that causes the issue also attached you can find the visualization of the triangulation including the super-triangle and missing edge in red.

PointCloudTriangulation.pdf

VERTICES
0.15147567518991,-5.144230291488,0
0.10442,-5.06098,0
0.1228735248885,-5.12897066233,0
0.1322969035965,-5.141286788425,0
0.115882234089,-5.115648852375,0
0.13262891777369,-5.119598039304,0
0.11311813200326,-5.138343285364,0
0.111139345548,-5.09040217055,0
0.121648346645,-5.09478239621,0
0.1152696449675,-5.098554719315,0
0.1303134549875,-5.106097900345,0
0.10889094329024,-5.1023270424231,0
0.142052296482,-5.131914165395,0
0.154751587595,-5.127544895745,0
0.1484019420385,-5.129729530575,0
0.1389785633305,-5.117413404475,0
0.1563895437975,-5.119202197875,0
0.150039898241,-5.1213868327,0
0.140515429906,-5.12466378494,0
0.145328208887,-5.11522876965,0
0.1516778544435,-5.113044134825,0
0.1580275,-5.1108595,0
0.107779672774,-5.075691085275,0
0.112085873903,-5.07104664934,0
0.1514750401785,-5.061655309135,0
0.13440575,-5.08723775,0
0.110784,-5.063616,0
0.11338774780615,-5.078477298681,0
0.1682004187975,-5.131013072875,0
0.18164925,-5.13448125,0
0.1921660803575,-5.05969461827,0
0.1750967901785,-5.085277059135,0
0.221046245536,-5.045923052405,0
0.31820357142857,-4.9298217230895,0
0.2499264107145,-5.032151486545,0
0.284064991072,-4.980986604815,0

I see that with commit 14a66c766a0bf397300d55b39b7954c5f52895d0 the library now enhanches the support of conforming Delaunay triangulation , adding more point if needed.

It is not clear to me if the points will be added only if edges are overlapping/intersecting.
If it is not the case, I suggest to make this functionality optional.
This to allow a "relaxed" result that is conformant to the input data.

Sometime you simply need it, at the cost of a not fully conforming Delaunay triangulation.

Suppose to expect to obtain a closed solid out of tessellations, the flux is (more or less) the following

1. tessellate the common boundaries in 2d
2. create the area trimming loops out of common boundaries
3. tessellate the single area providing the obtained loops
4. obtain a 3d tessellation out of the 2d one
5. merge all 3d tessellation in a single mesh

If new points are added on boundaries, then the resulting solid will be opened: there will be an "empty" boundary at the edge where the "additional" point has been inserted.

To obtain a closed solid, if new points are added, then the user should re-process all surrounding areas inserting the additional points and re-tessellate from scratch.
This process must be recursive, because then the neighbor areas might need additional points, etc...

Making it optional will ensure that there are no failures.
The library is great (actually was, now) also because of its conformance to the input data.

@artem-ogre These numbers are only meant to be a rough measurement. Note that not all these libraries are reliable or support general constrained Delaunay triangulation.


std::vector<std::pair<double, double>> vertices;
for(size_t i = 0; i < 1000; ++i)
{
    for(size_t j = 0; j < 1000; ++j)
    {
        vertices.emplace_back(i*1e-5, j*1e-5);
    }
}


10x10

Elapsed time poly2Tri: 0.00012235 s
Elapsed time CDT: 0.000653747 s
Elapsed time CGAL: 0.000221772 s
Elapsed time Delaunator: 6.9119e-05 s
Elapsed time Triangle: 0.000959387 s

20x20

Elapsed time poly2Tri: 0.000755585 s
Elapsed time CDT: 0.00217176 s
Elapsed time CGAL: 0.000819186 s
Elapsed time Delaunator: 0.000294325 s
Elapsed time Triangle: 0.00246849 s


100x100

Elapsed time poly2Tri: 0.0116399 s
Elapsed time CDT: 0.113256 s
Elapsed time CGAL: 0.0159775 s
Elapsed time Delaunator: 0.00511762 s
Elapsed time Triangle: 0.0100751 s

100x1000

Elapsed time poly2Tri: 0.106778 s
Elapsed time CDT: 8.49504 s
Elapsed time CGAL: 0.158438 s
Elapsed time Delaunator: 0.0808353 s
Elapsed time Triangle: 0.127281 s

1000x1000

Elapsed time poly2Tri: 1.1229 s
Elapsed time CDT: 84.6357 s
Elapsed time CGAL: 1.6105 s
Elapsed time Delaunator: 0.964066 s
Elapsed time Triangle: 1.69101 s




srand (time(NULL));
std::vector<std::pair<double, double>> vertices;
for(size_t i = 0; i < 10; ++i)
{
    for(size_t j = 0; j < 10; ++j)
    {
        bool inserted = false;
        while(!inserted)
        {
            size_t x = (rand() % 10000);
            size_t y = (rand() % 10000);
            auto it = std::find_if(vertices.begin(), vertices.end(), [&](const auto& xy){return x-xy.first < 1e-5 && y-xy.second < 1e-5;});
            if(it == vertices.end())
            {
                vertices.emplace_back(x*1e-5, y*1e-5);
                inserted = true;
            }
        }
    }
}

10x10

Elapsed time poly2Tri: 0.000154201 s
Elapsed time CDT: 0.000439808 s
Elapsed time CGAL: 9.577e-05 s
Elapsed time Delaunator: 6.046e-05 s
Elapsed time Triangle: 0.000652088 s



100x100

Elapsed time poly2Tri: 0.0123536 s
Elapsed time CDT: 0.0613802 s
Elapsed time CGAL: 0.00735314 s
Elapsed time Delaunator: 0.00525829 s
Elapsed time Triangle: 0.0123408 s


100x1000

Elapsed time poly2Tri: 0.168798 s
Elapsed time CDT: 1.06543 s
Elapsed time CGAL: 0.0847132 s
Elapsed time Delaunator: 0.0803343 s
Elapsed time Triangle: 0.191198 s


500x500

Elapsed time poly2Tri: 0.448719 s
Elapsed time CDT: 3.0024 s
Elapsed time CGAL: 0.213624 s
Elapsed time Delaunator: 0.238802 s
Elapsed time Triangle: 0.560273 s

Originally posted by @AndreFecteau in #37 (comment)

Hello,

As I understand, the constraint edges are given in cdt.fixedEdges. But the constraint edges are those that the user inserts in cdt, so he already knows them. Am I missing a case where fixedEdges is useful?

Theese functions should be marked inline - otherwise, compiling projects with multiple cpp files, including CDT, will fail.
CDTUtils.hpp,99

Edge::Edge(VertInd iV1, VertInd iV2)
    : m_vertices(
          iV1 < iV2 ? std::make_pair(iV1, iV2) : std::make_pair(iV2, iV1))
{}

bool Edge::operator==(const Edge& other) const
{
    return m_vertices == other.m_vertices;
}

VertInd Edge::v1() const
{
    return m_vertices.first;
}

VertInd Edge::v2() const
{
    return m_vertices.second;
}

const std::pair<VertInd, VertInd>& Edge::verts() const
{
    return m_vertices;
}

Sometimes it happens that edge loops are (self) intersecting, due to various description errors.
Now the library fails to remove the outer loops, returning no triangles.
It could be interesting to get a result, even if wrong in this case.

Hello,

Is there a built-in way to get the boundary edges? Otherwise I can do it myself, by taking the edges of all the triangles and then the boundary edges are those which are unique. Maybe there's a better way?

I have a large project I'm testing CDT in, and there happens to be a class in the project named KDTree which causes CDT to generate all kinds of unrelated errors during compilation due to the naming conflict between the KDTree class and CDT's KDTree namespace.

Nesting the KDTree namespace of the CDT library inside the CDT namespace solves the problem. It probably makes sense to have all CDT classes/namespaces nested inside the CDT namespace....KDTree is the only one I see outside of it.

Discussed in #99

// example where adaptive differs from exact predicate
// adaptive seams to be wrong (I think rising xxx_errbound could fix this)

ax	-1.4048103911580639e-11	const double
ay	5.3534412196824579e-12	const double
bx	1.4048103911580639e-11	const double
by	-5.3534412196824579e-12	const double
cx	-1.4048103911580639e-11	const double
cy	-5.3534412196824579e-12	const double
dx	-5.3534412196824579e-12	const double
dy	-1.4048103911580639e-11	const double

predicates::adaptive::incircle<double> returned	1.5785423408550432e-75	double
predicates::exact::incircle<double> returned	0.0000000000000000	double
crude_xa::incircle<double> returned 		0.0000000000000000	double

// ---------------------------------------------------
// example where adaptive & exact predicates seams to be both wrong!

ax	-9.1428964336885931e-10	const double
ay	-5.2844166345548637e-19	const double
bx	-5.2844166345548637e-19	const double
by	-9.1428964336885931e-10	const double
cx	5.2844166345548637e-19	const double
cy	-9.1428964336885931e-10	const double
dx	-5.2844166345548637e-19	const double
dy	9.1428964336885931e-10	const double

predicates::adaptive::incircle<double> returned	1.2392294127517818e-119	double
predicates::exact::incircle<double> returned	1.2392294127517818e-119	double
crude_xa::incircle<double> returned 		0.0000000000000000	double

	double ax = -1.00;
	double ay = -0.01;
	double bx = -0.01;
	double by = -1.00;
	double cx =  0.01;
	double cy = -1.00;
	double dx = -0.01;
	double dy =  1.00;

Hi,
I am currently trying to figure out how to use processed triangle and vertices to draw them as triangles,
but i get weird results. Are the indices and vertices ready to use or do i have to go through neighbors or something?
Can you show an example how you to access the processed data?

CDT::Triangulation<double> cdt;
cdt.insertVertices(
    points.begin(),
    points.end(),
    [](const CDT::V2d<double>& p) { return p.x; },
    [](const CDT::V2d<double>& p) { return p.y; }
);
cdt.insertEdges(
    edges.begin(),
    edges.end(),
    [](const CDT::Edge& e) { return e.v1(); },
    [](const CDT::Edge& e) { return e.v2(); }
);

cdt.eraseOuterTrianglesAndHoles();

for (uint64_t i = 0; i < cdt.vertices.size(); ++i)
{
    CDT::V2d vertex = cdt.vertices[i];
    double height = 0.0;
    geometryData.positions.push_back(glm::vec3(vertex.x, vertex.y, height));
}

for (uint64_t i = 0; i < cdt.triangles.size(); ++i)
{
    CDT::Triangle triangle = cdt.triangles[i];
    CDT::VerticesArr3 vertices = triangle.vertices;
    for (uint8_t j = 0; j < vertices.size(); ++j)
    {
        geometryData.indices.push_back(vertices[j]);
    }
    geometryData.indices.push_back(globals::restartIndex);
}

Ciao,

With the enclosed grid of points the kdtree insertion fails (FYI, the "old" boost::rtree was working perfectly)
CDTTessellationGrid.grid (1).txt
It runs to an infinite loop in KDTree::insert, in the while(true) loop at row 117.

To load this file you can use the visualizer modified here:
main.zip

according to paper,in insert edge step, there might be duplicate points of left point and right point. say we have a edge[1, 2], after eliminate triangle, we have [3, 4, 5, 4, 6] in left points, and we have a two triangle not tie right neighbor(of edge [4, 5]), so we must fix their neighbor after we do two triangulatePseudoPolygon.

since i'm not familiar with cpp, i could not give a merge request, sorry about that.

Hello,

I inputted the four vertices of a square as vertices and the two diagonals of this square as constraint edges. Then the output I got is the triangulation with no triangle, no edge, and four fixed edges: the segments which join the center of the square to the vertices. Is it normal? I expected to get four triangles.

Ciao,

I implemented the usage of custom geometry initialization and I have seen that the library is not correctly handling the case.
The vertex ordering was not correctly maintained after a call to eraseOuterTriangles or eraseOuterTrianglesAndHoles, thus making impossible to remap correctly the indexes.
I found 2 points where I had to change the code in order to correctly execute:

• void Triangulation::eraseSuperTriangleVertices(): I had to check if the geometry is custom, and if it is, the function should do nothing.
• void Triangulation::eraseSuperTriangle(): same as previous one.
• void Triangulation::initializedWithCustomSuperGeometry(): I need to add the line m_superGeomType = SuperGeometryType::Enum::Custom;

I didn't check other locations, maybe you will see some other areas where to take a look.
Enclosed here the changed file.

CDT.zip

Hi 👋 , I just stumbled upon this library. Looks like a very nice project. Thanks for providing this 👍
I tried using custom point types with lambda function accessors but get this compile error:

./CDT/CDTUtils.hpp:44:35: error: no viable conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double>'
        box.min.x = std::min(getX(*first), box.min.x);
                                  ^~~~~~
./CDT/CDT.h:394:26: note: in instantiation of function template specialization 'CDT::envelopBox<double, std::__1::__wrap_iter<std::__1::array<double, 3> *>, const double &(*)(const
      CDT::V2d<double> &)>' requested here
        addSuperTriangle(envelopBox<T>(first, last, getX_V2d<T>, getY_V2d<T>));
                         ^
main.cpp:49:9: note: in instantiation of function template specialization 'CDT::Triangulation<double>::insertVertices<std::__1::__wrap_iter<std::__1::array<double, 3> *>, double
      (*)(const std::__1::array<double, 3> &), double (*)(const std::__1::array<double, 3> &)>' requested here
    cdt.insertVertices(pts.begin(), pts.end(), get_x, get_y);
        ^
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double> &'
      for 1st argument
struct CDT_EXPORT V2d
                  ^
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'CDT::V2d<double> &&' for
      1st argument
In file included from main.cpp:1:
In file included from ./CDT/CDT.h:13:
In file included from ./CDT/CDTUtils.h:363:
./CDT/CDTUtils.hpp:45:35: error: no viable conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double>'
        box.max.x = std::max(getX(*first), box.max.x);
                                  ^~~~~~
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double> &'
      for 1st argument
struct CDT_EXPORT V2d
                  ^
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'CDT::V2d<double> &&' for
      1st argument
In file included from main.cpp:1:
In file included from ./CDT/CDT.h:13:
In file included from ./CDT/CDTUtils.h:363:
./CDT/CDTUtils.hpp:46:35: error: no viable conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double>'
        box.min.y = std::min(getY(*first), box.min.y);
                                  ^~~~~~
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double> &'
      for 1st argument
struct CDT_EXPORT V2d
                  ^
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'CDT::V2d<double> &&' for
      1st argument
In file included from main.cpp:1:
In file included from ./CDT/CDT.h:13:
In file included from ./CDT/CDTUtils.h:363:
./CDT/CDTUtils.hpp:47:35: error: no viable conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double>'
        box.max.y = std::max(getY(*first), box.max.y);
                                  ^~~~~~
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'const CDT::V2d<double> &'
      for 1st argument
struct CDT_EXPORT V2d
                  ^
./CDT/CDTUtils.h:96:19: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'std::__1::array<double, 3>' to 'CDT::V2d<double> &&' for
      1st argument
In file included from main.cpp:1:
./CDT/CDT.h:394:26: error: no matching function for call to 'envelopBox'
        addSuperTriangle(envelopBox<T>(first, last, getX_V2d<T>, getY_V2d<T>));
                         ^~~~~~~~~~~~~
main.cpp:50:9: note: in instantiation of function template specialization 'CDT::Triangulation<double>::insertVertices<std::__1::__wrap_iter<std::__1::array<double, 3> *>,
      (lambda at main.cpp:51:33), (lambda at main.cpp:51:83)>' requested here
    cdt.insertVertices(
        ^
./CDT/CDTUtils.hpp:34:10: note: candidate template ignored: substitution failure [with T = double, TVertexIter = std::__1::__wrap_iter<std::__1::array<double, 3> *>, TGetVertexCoord
      = const double &(*)(const CDT::V2d<double> &)]
Box2d<T> envelopBox(
         ^
./CDT/CDTUtils.hpp:53:10: note: candidate function template not viable: requires single argument 'vertices', but 4 arguments were provided
Box2d<T> envelopBox(const std::vector<V2d<T> >& vertices)
         ^
5 errors generated.

I am using the library in header-only mode and compiling with g++ -std=c++14 -o main main.cpp

#include "CDT/CDT.h"

#include <array>
#include <vector>

int main(void)
{
    std::vector<std::array<double, 3>> pts{
        {1, 1, 1},
        {3, 1, 1},
        {1, 2, 1}};

    CDT::Triangulation<double> cdt = CDT::Triangulation<double>(CDT::FindingClosestPoint::ClosestRandom, 10);
    cdt.insertVertices(
        pts.begin(), pts.end(), [](const std::array<double, 3> &p) -> double { return p.at(0); }, [](const std::array<double, 3> &p) -> double { return p.at(1); });

    return 0;
}

Hello,

Here is my code:

typedef CDT::V2d<double> Vertex;
typedef CDT::Edge Edge;
typedef CDT::Triangulation<double> Triangulation;

arma::umat Rcpp_delaunay(const arma::mat & points){
  Triangulation cdt(CDT::VertexInsertionOrder::AsProvided);
  size_t npoints = points.n_rows;
  std::vector<Vertex> vertices(npoints);
  for (size_t i = 0; i < npoints; ++i) {
    const arma::rowvec row_i = points.row(i);
    vertices[i] = Vertex::make(row_i(0), row_i(1));
  }
  cdt.insertVertices(vertices);
  cdt.eraseSuperTriangle();
  const CDT::TriangleVec triangles = cdt.triangles;
  arma::umat out(triangles.size(), 3);
  for(size_t i = 0; i < triangles.size(); ++i){
    const CDT::VerticesArr3 trgl = triangles[i].vertices;
    out(i, 0) = trgl[0];
    out(i, 1) = trgl[1];
    out(i, 2) = trgl[2];
  }
  return out;
}

arma::umat Rcpp_constrained_delaunay(
    const arma::mat & points, const arma::umat & edges
){
  Triangulation cdt(CDT::VertexInsertionOrder::AsProvided);
  size_t npoints = points.n_rows;
  std::vector<Vertex> vertices(npoints);
  for (size_t i = 0; i < npoints; ++i) {
    const arma::rowvec row_i = points.row(i);
    vertices[i] = Vertex::make(row_i(0), row_i(1));
  }
  size_t nedges = edges.n_rows;
  std::vector<Edge> Edges(nedges);
  for (size_t i = 0; i < nedges; ++i) {
    const arma::urowvec row_i = edges.row(i);
    Edge edge = Edge(row_i(0), row_i(1));
    Edges[i] = edge;
  }
  cdt.insertVertices(vertices);
  cdt.insertEdges(Edges);
  cdt.eraseOuterTrianglesAndHoles();
  const CDT::TriangleVec triangles = cdt.triangles;
  arma::umat out(triangles.size(), 3);
  for(size_t i = 0; i < triangles.size(); ++i){
    const CDT::VerticesArr3 trgl = triangles[i].vertices;
    out(i, 0) = trgl[0];
    out(i, 1) = trgl[1];
    out(i, 2) = trgl[2];
  }
  return out;
}

The first function works fine. But the compilation of the second function throws this error: no matching function for call to CDT::Edge::Edge().

Your search algorithm (crossing the dividing edge) requires triangulation to be delaunay (not constrained delaunay). But you can use stochastic walk instead of using data structure to store visitted.

I encountered a possible bug while computing a constrained triangulation. Here is a plot of the constraints:

Here is a plot of the triangulation generated by CDT:

The problem is that the three vertices on the upper-right side are put into a single element. Here are the angles of each element

triangle 0 has angles 104.51, 32.0194, 43.4705
triangle 1 has angles 29.3741, 51.7046, 98.9213
triangle 2 has angles 8.53774e-07, 0, 180
triangle 3 has angles 70.2043, 70.6423, 39.1533
triangle 4 has angles 73.9633, 65.8872, 40.1495
triangle 5 has angles 29.7778, 50.5047, 99.7174
triangle 6 has angles 64.009, 78.8855, 37.1055
triangle 7 has angles 97.3523, 51.7375, 30.9102
triangle 8 has angles 1.20742e-06, 8.53774e-07, 180

Notice the angles of triangle 2 (listed in degrees).

A minimal reproduce-able example is attached. It contains

• mesh_constraints_verts.txt : the coordinates of the vertices
• mesh_constraints_edges.txt : the indices of vertices that form constrained edges
• test4.cc : source file that loads the above two files, used CDT to compute the triangulation, computes the edge angle, and writes triangulation files mesh_output_verts.txt and mesh_output_triangles.txt
• fout: output from running test4 (including the edge angles shown above)
• the plots shown above

To compile test4.cc, it only needs to find the CDT include directory.
cdt.tar.gz

I've noticed that sometimes an infinite loop can occur in insertVertex. If I print out the triStack size it increases indefinitely. It seems that `isFlipNeeded is returning true and constantly pushing new elements.

I'm using your library for my game and it's procedurally generated so this occurs every now and again so I'm struggling to create test data for this. Is this likely something to do with me inserting incorrect data or a bug?

Here is my code for triangulation. The calculated polygon is a vector containing doubles.

CDT::Triangulation<double> cdt;
std::vector<CustomPoint2D> points;

for (int i = 0; i < calculatedPolygon.size(); i += 2) {
    points.push_back({calculatedPolygon[i], calculatedPolygon[i + 1]});
}

cdt.insertVertices(
        points.begin(),
        points.end(),
        [](const CustomPoint2D &p) { return p.data[0]; },
        [](const CustomPoint2D &p) { return p.data[1]; }
);

std::vector<CustomEdge> edges;

for(int i = 0; i < points.size()-1; i++){

    CustomEdge customEdge;
    customEdge.vertices.first = i;
    customEdge.vertices.second = i+1;
    edges.push_back(customEdge);
}

cdt.insertEdges(
        edges.begin(),
        edges.end(),
        [](const CustomEdge &e) { return e.vertices.first; },
        [](const CustomEdge &e) { return e.vertices.second; }
);

cdt.eraseOuterTrianglesAndHoles();

delaunator::Delaunator d(calculatedPolygon);

All source files located outside "\include" folder are referring to the library without explicitly set the relative path (it expects that "cdt.h" it is in the include search path).
This forces to add the incldue folder as additional include directory (I'm using vs2019).

I think it is better to use the relative path to keep consistent with the installation.

I.e. in CDT\extras\InitializeWithGrid.h replace

#include "CDT.h"
#include "CDTUtils.h"

with

#include "../include/CDT.h"
#include "../include/CDTUtils.h"

In case it is wanted, I think it is better to use the <> instead of the "" to clarify that the included file must be available at the root of the search path.

#include <CDT.h>
#include <CDTUtils.h>

Hello, I'm using following commands,

CDT::RemoveDuplicatesAndRemapEdges(vertices, edges); // remove duplicate
cdt.eraseSuperTriangle( ); // make mesh in the case the outer boundary edges don't exist

However, the result triangles sometimes cross over, making ill-shaped mesh
But this does not always happen. (also, I found that this does not happen at all if only a point is used, but if a line is added, this case occurs quite a bit.)
Are there any tips or methods to prevent this??

Hello! I am trying to triangulate poly, but I get assert on adding edges:

#include "cdt/CDT.h"
using Triangulation = CDT::Triangulation<double>;

int main(void)
{
	std::vector<CDT::V2d<double>> vertsCDT;
	vertsCDT.push_back(CDT::V2d<double>::make(2646.483004, 4635.168252));
	vertsCDT.push_back(CDT::V2d<double>::make(2940.454821, 4768.453360));
	vertsCDT.push_back(CDT::V2d<double>::make(2956.371323, 4741.992504));
	vertsCDT.push_back(CDT::V2d<double>::make(2919.866354, 4733.151108));
	vertsCDT.push_back(CDT::V2d<double>::make(2907.399464, 4714.272492));
	vertsCDT.push_back(CDT::V2d<double>::make(2860.306798, 4697.221008));
	vertsCDT.push_back(CDT::V2d<double>::make(2780.158799, 4650.778860));
	vertsCDT.push_back(CDT::V2d<double>::make(2265.225986, 4403.916563));
	vertsCDT.push_back(CDT::V2d<double>::make(2182.209600, 4365.631781));
	vertsCDT.push_back(CDT::V2d<double>::make(2173.947532, 4397.984430));
	vertsCDT.push_back(CDT::V2d<double>::make(2232.832254, 4409.193994));
	vertsCDT.push_back(CDT::V2d<double>::make(2145.628913, 4499.153591));
	vertsCDT.push_back(CDT::V2d<double>::make(2066.116789, 4531.471540));
	vertsCDT.push_back(CDT::V2d<double>::make(2107.904595, 4569.142974));
	vertsCDT.push_back(CDT::V2d<double>::make(2173.586631, 4545.401212));
	vertsCDT.push_back(CDT::V2d<double>::make(2245.979345, 4504.443379));
	vertsCDT.push_back(CDT::V2d<double>::make(2329.936334, 4536.309812));
	vertsCDT.push_back(CDT::V2d<double>::make(2382.950861, 4505.163464));
	vertsCDT.push_back(CDT::V2d<double>::make(2414.148222, 4533.413655));
	vertsCDT.push_back(CDT::V2d<double>::make(2420.020403, 4567.534854));
	vertsCDT.push_back(CDT::V2d<double>::make(2469.472407, 4591.682871));
	vertsCDT.push_back(CDT::V2d<double>::make(2538.962717, 4586.428933));
	vertsCDT.push_back(CDT::V2d<double>::make(2606.040217, 4616.841854));
	vertsCDT.push_back(CDT::V2d<double>::make(2595.426630, 4630.277520));
	vertsCDT.push_back(CDT::V2d<double>::make(2568.937784, 4646.133540));
	vertsCDT.push_back(CDT::V2d<double>::make(2554.361486, 4663.323147));
	vertsCDT.push_back(CDT::V2d<double>::make(2552.593887, 4672.138585));
	vertsCDT.push_back(CDT::V2d<double>::make(2564.495713, 4691.093858));
	vertsCDT.push_back(CDT::V2d<double>::make(2583.462998, 4703.889658));
	vertsCDT.push_back(CDT::V2d<double>::make(2583.911492, 4693.312373));
	vertsCDT.push_back(CDT::V2d<double>::make(2590.975244, 4690.229175));
	vertsCDT.push_back(CDT::V2d<double>::make(2608.631592, 4687.598233));
	vertsCDT.push_back(CDT::V2d<double>::make(2615.241370, 4693.777127));
	vertsCDT.push_back(CDT::V2d<double>::make(2615.239494, 4696.864568));
	vertsCDT.push_back(CDT::V2d<double>::make(2594.057935, 4700.373892));
	vertsCDT.push_back(CDT::V2d<double>::make(2580.785697, 4755.025906));
	vertsCDT.push_back(CDT::V2d<double>::make(2570.185110, 4768.249869));
	vertsCDT.push_back(CDT::V2d<double>::make(2570.174324, 4786.317531));
	vertsCDT.push_back(CDT::V2d<double>::make(2587.819934, 4800.873632));
	vertsCDT.push_back(CDT::V2d<double>::make(2593.997380, 4800.877349));
	vertsCDT.push_back(CDT::V2d<double>::make(2590.474213, 4788.090764));
	vertsCDT.push_back(CDT::V2d<double>::make(2586.503055, 4785.012080));
	vertsCDT.push_back(CDT::V2d<double>::make(2591.805134, 4780.601452));
	vertsCDT.push_back(CDT::V2d<double>::make(2593.577019, 4764.730612));
	vertsCDT.push_back(CDT::V2d<double>::make(2601.971607, 4754.158121));
	vertsCDT.push_back(CDT::V2d<double>::make(2614.770649, 4751.078432));
	vertsCDT.push_back(CDT::V2d<double>::make(2614.796616, 4708.322388));
	vertsCDT.push_back(CDT::V2d<double>::make(2618.328357, 4706.998159));
	vertsCDT.push_back(CDT::V2d<double>::make(2627.147740, 4714.939484));
	vertsCDT.push_back(CDT::V2d<double>::make(2646.567444, 4710.548705));
	vertsCDT.push_back(CDT::V2d<double>::make(2657.148030, 4720.252242));
	vertsCDT.push_back(CDT::V2d<double>::make(2653.172499, 4734.349482));
	vertsCDT.push_back(CDT::V2d<double>::make(2635.514965, 4739.187149));
	vertsCDT.push_back(CDT::V2d<double>::make(2631.101149, 4747.120403));
	vertsCDT.push_back(CDT::V2d<double>::make(2620.062813, 4752.842717));
	vertsCDT.push_back(CDT::V2d<double>::make(2605.929343, 4769.151887));
	vertsCDT.push_back(CDT::V2d<double>::make(2605.926408, 4774.000396));
	vertsCDT.push_back(CDT::V2d<double>::make(2612.545497, 4774.884941));
	vertsCDT.push_back(CDT::V2d<double>::make(2616.957172, 4780.616664));
	vertsCDT.push_back(CDT::V2d<double>::make(2621.371786, 4781.499884));
	vertsCDT.push_back(CDT::V2d<double>::make(2624.025906, 4769.162877));
	vertsCDT.push_back(CDT::V2d<double>::make(2629.322080, 4764.317597));
	vertsCDT.push_back(CDT::V2d<double>::make(2641.231696, 4769.608090));
	vertsCDT.push_back(CDT::V2d<double>::make(2648.729638, 4779.309717));
	vertsCDT.push_back(CDT::V2d<double>::make(2663.295551, 4778.884008));
	vertsCDT.push_back(CDT::V2d<double>::make(2666.828119, 4766.101730));
	vertsCDT.push_back(CDT::V2d<double>::make(2690.222871, 4758.180330));
	vertsCDT.push_back(CDT::V2d<double>::make(2706.114874, 4748.493266));
	vertsCDT.push_back(CDT::V2d<double>::make(2710.977196, 4740.560372));
	vertsCDT.push_back(CDT::V2d<double>::make(2710.115392, 4704.848041));
	vertsCDT.push_back(CDT::V2d<double>::make(2688.487237, 4715.423185));
	vertsCDT.push_back(CDT::V2d<double>::make(2670.390725, 4714.966084));
	vertsCDT.push_back(CDT::V2d<double>::make(2665.102357, 4707.026855));
	vertsCDT.push_back(CDT::V2d<double>::make(2639.960968, 4688.943700));
	vertsCDT.push_back(CDT::V2d<double>::make(2619.221169, 4682.756151));
	vertsCDT.push_back(CDT::V2d<double>::make(2604.677698, 4655.852030));
	vertsCDT.push_back(CDT::V2d<double>::make(2615.271092, 4644.846203));
	vertsCDT.push_back(CDT::V2d<double>::make(2635.574060, 4642.651673));
	vertsCDT.push_back(CDT::V2d<double>::make(2646.483004, 4635.168252));

	std::vector<CDT::Edge> edgesCDT;
	CDT::VertInd vertIndex = 0;
	for(auto& vert : vertsCDT)
	{
		if((vertIndex + 1) == vertsCDT.size())
			edgesCDT.push_back(CDT::Edge(vertIndex, 0));
		else
			edgesCDT.push_back(CDT::Edge(vertIndex, vertIndex + 1));

		vertIndex++;
	}

	Triangulation cdt =
		Triangulation(CDT::FindingClosestPoint::BoostRTree);
	cdt.insertVertices(vertsCDT);
	cdt.insertEdges(edgesCDT);
	cdt.eraseOuterTrianglesAndHoles();

	return 0;
}

Is this my mistake or bug, maybe?

Hi,

Maybe this is amateur question. But why in "\CDT\include" there are files with the same names e.g. CDT.h and CDT.hpp ?
Wont they be conflicting while linking?

I really have problem that I cannot solve for days.
If I #include <CDT.h> to precompiled headers it always produces the error below:

I download CDT with cmake in the build folder like this:

  #######################################################################
  # CDT
  ####################################################################### 
  ExternalProject_Add(cdt
      URL https://github.com/artem-ogre/CDT/archive/refs/tags/1.1.2.zip
      CMAKE_ARGS
        -DCMAKE_BUILD_TYPE=${CMAKE_BUILD_TYPE}
        -DCMAKE_CXX_COMPILER=${CMAKE_CXX_COMPILER}
        #-DCMAKE_INSTALL_PREFIX:PATH="${CMAKE_BINARY_DIR}/install"
      SOURCE_DIR   "${CMAKE_BINARY_DIR}/install/cdt"
        #INSTALL_DIR   "${CMAKE_INSTALL_PREFIX}/install"
      CONFIGURE_COMMAND "" #do not configure
      BUILD_COMMAND "" #do not buld
      INSTALL_COMMAND "" #installer for now is empty
  )

main.obj : error LNK2005: "class std::vector<unsigned short,class std::allocator<unsigned short> > __cdecl CDT::
CalculateTriangleDepths(unsigned int,class std::vector<struct CDT::Triangle,class std::allocator<struct CDT::Tri
angle> > const &,class std::unordered_set<struct CDT::Edge,struct std::hash<struct CDT::Edge>,struct std::equal_
to<struct CDT::Edge>,class std::allocator<struct CDT::Edge> > const &,class std::unordered_map<struct CDT::Edge,
unsigned short,struct std::hash<struct CDT::Edge>,struct std::equal_to<struct CDT::Edge>,class std::allocator<st
ruct std::pair<struct CDT::Edge const ,unsigned short> > > const &)" (?CalculateTriangleDepths@CDT@@YA?AV?$vecto
r@GV?$allocator@G@std@@@std@@IAEBV?$vector@UTriangle@CDT@@V?$allocator@UTriangle@CDT@@@std@@@3@AEBV?$unordered_s 
et@UEdge@CDT@@U?$hash@UEdge@CDT@@@std@@U?$equal_to@UEdge@CDT@@@4@V?$allocator@UEdge@CDT@@@4@@3@AEBV?$unordered_m 
ap@UEdge@CDT@@GU?$hash@UEdge@CDT@@@std@@U?$equal_to@UEdge@CDT@@@4@V?$allocator@U?$pair@$$CBUEdge@CDT@@G@std@@@4@ 
@3@@Z) already defined in cmake_pch.obj [C:\IBOIS57\_Code\Software\CPP\CMAKE\super_build\compas_wood\build_win\c 
ompas_wood.vcxproj]
C:\IBOIS57\_Code\Software\CPP\CMAKE\super_build\compas_wood\build_win\Release\compas_wood.exe : fatal error LNK1
169: one or more multiply defined symbols found [C:\IBOIS57\_Code\Software\CPP\CMAKE\super_build\compas_wood\bui 
ld_win\compas_wood.vcxproj]

Hi, I am looking for alternative and more modern delaunay triangulation library instead of Triangle. It is awesome and extremely fast. I have been using it for a while but it's kind of old now and the memory management is still 32bit.
I found this CDT project and everything looks promising. Yet I could not find any parameter/function that allows insertion of Steiner Points/Quality control during triangulation. Could you guide me out?

I founded this library very promising.
Well done and reasonably stable.
I see two problems, to use it effectively in everyday tessellation.
In the tessellation algorithms, often is useful to prepare a grid of points and superimpose on it the edge loops.
Now all the points are inserted in the same way, regardless if they have a "regular" distribution or they are unorganized.
It will be really cool to create an "initVertexGrid" function that initialize the data structure from a grid of vertices (vector<vector<>>?) and apply a predefined pattern to the grid of points in input.

Hello,

I did a R package wrapping CDT. When submitting a R package for publication, it is tested with multiple OS. A unit test fails on Mac. The results of a constrained Delaunay triangulation are not the same as the ones obtained on Windows and Unix (the edges are not the same). Does it make sense? The constrained Delaunay triangulation is not unique, is it? But how is it possible to get different results depending on the OS? The algorithm is deterministic, isn't it?

Algorithm is not supporting duplicate points. But it is a common case when input contains duplicated points (exactly same X and Y coordinates). Add functionality to perform fixing input data so that duplicates could be handles.

Requested in issue #2 by @KuDeSnik33ra

Hi,

First, thanks a lot for this useful implementation!

I was playing around with a simple example of a unconstrained triangulation of 3 points (that should always give a single triangle) but found it to yield inconsistent results for specific inputs and when called several times:

#include <iostream> 
#include "CDT.h"

int main(int argc, char *argv[])
{

  std::vector<CDT::V2d<float> > points;  
  points.push_back(CDT::V2d<float>::make(  1. , 0.   ));
  points.push_back(CDT::V2d<float>::make(  0 , 0.251 ));
  points.push_back(CDT::V2d<float>::make( -1. , 0.   )); 

  for (int i=0 ; i < 4; ++i) {
    
    CDT::Triangulation<float> cdt;  
    cdt.insertVertices(points);
    cdt.eraseSuperTriangle();
  
    std::cout << "found " << cdt.triangles.size() << " triangles" << std::endl;
  }
  
  return 0;
}

with the output

found 1 triangles
found 0 triangles
found 0 triangles
found 1 triangles

Is there something fundamentally wrong with how I am using CDT? Note that changing the y value of the second point from 0.251 to something larger eg 0.252 yields the expected result:

found 1 triangles
found 1 triangles
found 1 triangles
found 1 triangles

how should we call RemoveDuplicatesAndRemapEdges() ?
second parameter accepts only type std::vector&
but there is no such member. We only have EdgeUSet fixedEdges.

Now, to use the library, it is necessary to create the Vt2d<> vector.
It should be interesting to allow the caller to use a different point type (i.e.: boost::geometry), to avoid useless data transfer.
It will be interesting, as it is done in boost::geometry to allow the definition of a wrapper that doesn't rely on "x" and "y" fields directly, but mediated, allowing also to simple types like this to be used directly:

struct pt{
  double c[2];
};

I'm sorry I haven't used QT！Please introduce the installation environment and version of QT,and how to use your code in QT?Thank you!

I don't know how to specify the correct input to CDT for below's examples:

The left problem is a box with a hole aligned to the left side of the box (no shared points).
The right problem is a box with a hole inside that occupies the left half of the box.

The expected result in the right case is just 2 triangles, but I get 4 (the hole is kept as well):

0, 1, 4
2, 3, 4
4, 3, 5
4, 5, 0

For the left part the hole is also not detected:

What am I doing wrong?

Below is my test code. Mind the rotated x,y coordinate system when looking at the test coordinates below!

Test code:

#include "CDT/CDT.h"
#include <iostream>

int main() {

	std::vector<CDT::V2d<double> > points;
	std::vector<CDT::Edge> edges;

	// a box with a hole aligned to the left side
#if 1
	points.push_back( CDT::V2d<double>::make(0,0));
	points.push_back( CDT::V2d<double>::make(2,0));
	points.push_back( CDT::V2d<double>::make(2,3));
	points.push_back( CDT::V2d<double>::make(0,3));
	points.push_back( CDT::V2d<double>::make(0.5,0));
	points.push_back( CDT::V2d<double>::make(1.5,0));
	points.push_back( CDT::V2d<double>::make(1.5,1));
	points.push_back( CDT::V2d<double>::make(0.5,1));

	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 2));
	edges.push_back(CDT::Edge(2, 3));
	edges.push_back(CDT::Edge(3, 0));
	edges.push_back(CDT::Edge(4, 5));
	edges.push_back(CDT::Edge(5, 6));
	edges.push_back(CDT::Edge(6, 7));
	edges.push_back(CDT::Edge(7, 4));
#endif

	// a box with a hole that covers the left part of the box
#if 0
	points.push_back( CDT::V2d<double>::make(0,0));
	points.push_back( CDT::V2d<double>::make(2,0));
	points.push_back( CDT::V2d<double>::make(2,3));
	points.push_back( CDT::V2d<double>::make(0,3));
	points.push_back( CDT::V2d<double>::make(2,1));
	points.push_back( CDT::V2d<double>::make(0,1));

	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 2));
	edges.push_back(CDT::Edge(2, 3));
	edges.push_back(CDT::Edge(3, 0));
	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 4));
	edges.push_back(CDT::Edge(4, 5));
	edges.push_back(CDT::Edge(5, 0));
#endif

	CDT::Triangulation<double> cdt(CDT::FindingClosestPoint::ClosestRandom); // Note: we don't want to use boost

	cdt.insertVertices(points);
	cdt.insertEdges(edges);
	cdt.eraseOuterTrianglesAndHoles();

	for (auto tri : cdt.triangles)
		std::cout << tri.vertices[0] << ", " << tri.vertices[1] << ", " << tri.vertices[2] << std::endl;
}

Is there any possibility to detect, if triangles are inner - this is common scenario in gis triangulation, for example, boost::geometry::model::polygon can have one outer vertex ring and multiple inner vertex rings - for gaps in it. I tried to add inner vertex and boundaries to CDT - it produced triangles in the gaps. Is there any posiibility to remove them?

I think, the easy way to add such functionality is to mark verts as inner on adding them, and then remove triangles, containing only inner verts.