CDT_2d: Batch insertion does not delete duplicate vertices

[nervoussystem]

When using the batch insertion in CDT_2d, duplicates are not removed properly

nv_ is decremented but the duplicates are not removed

My fix was editing the batch insertion work similarly to single point insertion but using the reordering

void CDT2d::insert(
        index_t nb_points, const double* points, index_t* indices
    ) {
        CDT_LOG("Inserting " << nb_points << " points");
        debug_check_consistency();
        index_t v_offset = nv();
        point_.reserve(point_.size()+nb_points);
        v2T_.resize(v2T_.size()+nb_points, index_t(-1));
        vector<index_t> sorted_indices;
        compute_BRIO_order(nb_points, points, sorted_indices, 2, 2);
        index_t hint = index_t(-1);
        for(index_t i=0; i<nb_points; ++i) {
            point_.push_back(vec2(points+2*sorted_indices[i]));
            index_t v = CDTBase2d::insert(point_.size()-1, hint);
            if(point_.size() > nv()) {
                point_.pop_back();
            }
            if(indices != nullptr) {
                indices[sorted_indices[i]] = v;
            }
            hint = vT(v);
        }
        CDT_LOG("Inserted.");
        debug_check_consistency();        
  }

[BrunoLevy]

Hi Jesse,
I have just pushed a new version.
Note: since I wanted to keep the order of the points, it is a bit different from your code.
All the points are always copied into the points_ array, but the duplicated ones are simply not connected to any triangle.
I tested it with an example with duplicated constraint extremities, like what you have I think, and it seems to work.
Please tell me whether it is OK for you. If it's not OK, then I'll also include your version in the API.

[BrunoLevy]

Added a simple non-regression test for batch-insertion with duplicated points.
@nervoussystem if there are files you'd like to add to the testsuite please tell me.

[nervoussystem]

I'm not a fan of keeping unreferenced points in the resulting triangulation. Many operations won't like that so I think a lot of the time it will necessitate a cleanup step of removing and reindexing. But I can work with it either way. I prefer it make no naked vertices, since you can basically do it for free, but if not I would add a helper function like you did for remove_external_triangles, like a remove_unreferenced_vertices

[BrunoLevy]

OK, then I'm keeping both options then (the reason I'm keeping the other option is that when there is no duplicated point, I'd rather keep the order of user input unchanged).

I'm thinking of having a remove_unreferenced_vertices additional boolean argument to the batch-insert function to select the behavior, would it be OK for you ?

[nervoussystem]

Yeah, sounds good

[BrunoLevy]

Pushed new version. Non-regression tests pass (witout "remove_unreferenced_vertices" flag set). Would you test it and tell me what it gives ?

[nervoussystem]

Works well for me

[BrunoLevy]

Thank you for testing !
Do not hesitate to send more feedback / ask for more functionalities if need be
-- B
P.S. to facilitate writing different functions to select the triangles to be kept / to be deleted, I've separated remove_marked_triangles() from remove_external_triangles()