Add functionality for fixing duplicate points

[artem-ogre]

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 https://github.com/artem-ogre/CDT/issues/2 by @KuDeSnik33ra

[artem-ogre]

@KuDeSnik33ra could you please try the branch remove-duplicates to test if the proposed functionality works for you?

[KuDeSnik33ra]

Hello! It is not working for not last vert - you need to move all indices in edges in such case. I fixed your code:

RemapEdges(std::vector<Edge>& edges, const IndexMapping& mapping)
{
    typedef std::vector<Edge>::iterator It;
    typedef IndexMapping::const_iterator MappingCit;
    for(It it = edges.begin(); it != edges.end(); ++it)
    {
        array<VertInd, 2> vv = {it->v1(), it->v2()};
        bool isRemapped = false;
        for(unsigned char i = 0; i < 2; ++i)
        {
            VertInd newInd = vv[i];
            for(auto mapIt = mapping.begin(); mapIt != mapping.end(); ++mapIt)
            {
                if(vv[i] > mapIt->first)
                {
                    newInd--;
                    isRemapped = true;
                }
                else if(vv[i] == mapIt->first)
                {
                    newInd = mapIt->second;
                    isRemapped = true;
                    break;
                }
            }
            vv[i] = newInd;
        }
        if(isRemapped)
            *it = Edge(vv[0], vv[1]);
    }
}

[KuDeSnik33ra]

Test code here:

    vertsCDT.push_back(CDT::V2d<double>::make(0, 0));
    vertsCDT.push_back(CDT::V2d<double>::make(1, 0));
    vertsCDT.push_back(CDT::V2d<double>::make(2, 1));
    vertsCDT.push_back(CDT::V2d<double>::make(3, 2));

    int start = vertsCDT.size();

    vertsCDT.push_back(CDT::V2d<double>::make(0, 0));
    vertsCDT.push_back(CDT::V2d<double>::make(4, 3));
    vertsCDT.push_back(CDT::V2d<double>::make(5, 4));
    vertsCDT.push_back(CDT::V2d<double>::make(6, 5));

    int start2 = vertsCDT.size();

    vertsCDT.push_back(CDT::V2d<double>::make(4, 3));
    vertsCDT.push_back(CDT::V2d<double>::make(7, 6));
    vertsCDT.push_back(CDT::V2d<double>::make(8, 7));
    vertsCDT.push_back(CDT::V2d<double>::make(9, 8));

    std::vector<CDT::Edge> edgesCDT;
    for(int i = 0; i < start - 1; i++)
        edgesCDT.push_back(CDT::Edge(i, i + 1));
    edgesCDT.push_back(CDT::Edge(0, start - 1));

    for(int i = start; i < start2 - 1; i++)
        edgesCDT.push_back(CDT::Edge(i, i + 1));
    edgesCDT.push_back(CDT::Edge(start, start2 - 1));

    for(int i = start2; i < vertsCDT.size() - 1; i++)
        edgesCDT.push_back(CDT::Edge(i, i + 1));
    edgesCDT.push_back(CDT::Edge(start2, vertsCDT.size() - 1));

    CDT::RemoveDuplicatesAndRemapEdges(vertsCDT, edgesCDT);

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

[artem-ogre]

Whoops... I did something silly when trying to optimize space usage :).

Fix is pushed: now full mapping as a vector of indices is calculated. For example if you have vertices [0,1,2,3] where 0 and 2 are same it will produce vertices [0,1,3] and a mapping [0,1,0,2]. Then each edge will be re-mapped.

[KuDeSnik33ra]

It works, thanks!