does it need 'boundary edges' ?

[zinuok]

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

[zinuok]

I've misunderstood the definition of "Constrained DT".
We need outer boundary edges which are easily found via Graham's scan algorithms.

So I close this issue.

[artem-ogre]

@zinuok
Yes, normal Delaunay triangulation without constraints is supported out of the box, there is no need to calculate boundary edges yourself.
Just use eraseSuperTriangle() instead of eraseOuterTriangles().
It is mentioned in the documentation under Triangulated convex-hull example, but please let me know if you think of a good way to improve the documentation to make it more obvious.

Please confirm if this works for you.

[artem-ogre]

* Edited post above: eraseOuterTriangles() -> eraseSuperTriangle()