CGAL users discussion list

[Manuel Caroli <>]

Hi Josip,

Josip Dzolonga wrote:
> Hello everyone,
>
> After I perform some operations on the Delaunay data structure, I want 
> to remove certain vertices from it and then continue with the 
> processing. To avoid removing the same vertex more than once, I compare 
> the points, i.e.
The problem is caused by a call to the function index(Vertex_handle v) 
in a cell that does not contain v as a vertex. From the code snipped you 
provide below it is not clear where the problem comes from. Could you 
please provide a minimal example that can be compiled and that shows the 
problem.

By the way, I don't understand why you need the set seen but anyway this 
should not cause the problem.
> std::set<Vertex_handle> toRemove;
> std::set<Point> seen;
> for(std::list<Facet>::iterator iter = grown->facets->begin();
>         iter != grown->facets->end(); ++iter) {
>
>        Cell_handle c = (*iter).first;
>    int index = (*iter).second;
>    Point p1 = c->vertex((index+1)%4)->point();
>    Point p2 = c->vertex((index+2)%4)->point();
>             Point p3 = c->vertex((index+3)%4)->point();
>
>    // Do not remove points already removed from a neighboring cell
>    if(seen.insert(p1).second) {
>    toRemove.insert(c->vertex((index+1)%4));
>    }
>    if(seen.insert(p2).second) {
>    toRemove.insert(c->vertex((index+2)%4));
>    }
>    if(seen.insert(p3).second) {
>    toRemove.insert(c->vertex((index+3)%4));
>    }
>
> }
>
> T.remove(toRemove.begin(), toRemove.end());
>
>
> However, I get the same error as before (but is_valid() returns true :/):
>
> CGAL error: assertion violation!
> Expr: v == V[3]
> File: /usr/include/CGAL/Triangulation_ds_cell_base_3.h
> Line: 98
> terminate called after throwing an instance of 'std::logic_error'
>   what():  basic_string::_S_construct NULL not valid
>
> Then, I wanted to reconstruct the whole triangulation from scratch after 
> every cycle of the algorithm (not practical, but in desperate times need 
> desperate measures), and then this part causes trouble
>
> if(T.is_infinite(*iter)) { continue; } Triangle triangle = 
> T.triangle(*iter); if(triangle.is_degenerate() || 
> TrigPerimeter(triangle) < 0.1) { continue; } Point circumcenter = 
> CGAL::circumcenter(triangle);
What exactly does it mean that the call to circumcenter "fails"? The 
only issue I see right now would be that the triangle is very flat. Then 
you might get a division by 0 or an overflow because the circumcenter is 
very far away...
Could you check how the triangle looks like, for which circumcenter fails ?

best

Manuel

> The call to the circumcenter functions fails, and I suppose that this is 
> because I'm using an inexact_constructions kernel. Is there any trick 
> around this, i.e. some condition/heuristic that will skip these 
> triangles? Changing the kernel itself is of course a possibility, 
> however it will introduce a lot of changes in the whole project (because 
> it is assumed in most of the code that some CGAL functions return 
> something castable to double).
>
> Thank you very much,
> Josip