cgal-discuss - Re: [cgal-discuss] Problems with removing points from a triangulation,Take 3

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Problems with removing points from a triangulation,Take 3

From: Manuel Caroli <>
To:
Subject: Re: [cgal-discuss] Problems with removing points from a triangulation,Take 3
Date: Thu, 19 Nov 2009 18:25:34 +0100

Hi Josip,

your code seems ok. There might be a problem in your triangulation though. Do you do any modifications on the triangulation after its construction? To be sure that your triangulation is ok you might want to run the is_valid function on it right before the below piece of code.

Unfortunately, to be able to say anything more precise we would really need some compilable example that exhibits the problem you describe.

best

Manuel

Josip Dzolonga wrote:

I also forgot to note that I also check if c == 0.

On Thu, Nov 19, 2009 at 5:10 PM, Josip Dzolonga < <mailto:>> wrote:

Hello everyone again :),

I have started constructing a minimal counterexample and noticed
that the problem arises when I try to "dereference" a
Facet_circulator. Namely this piece of code

// current - edge, best - facet
Facet_circulator c = T.incident_facets(current, best);
Facet_circulator d(c);
std::list<Facet> candidates;

do {
std::cout << "1\n";
*c;
std::cout << "2\n";
} while(++c != d);

The 1 prints and then I get the assertion error described in the
previous e-mail. I couldn't find any preconditions that a
Facet_circulator has to satisfy before being dereferenced. Any
ideas? I am aware that this code piece does not provide enough
information for the problem, however I was just curious if this is a
common problem;

Best,
Josip

On Sun, Nov 15, 2009 at 10:30 PM, Josip Dzolonga

<

<mailto:>>
wrote:

is_valid() succeeds both before and after the loop. The kernel
is exactly that one,
Exact_predicates_inexact_constructions_kernel. I will try to
come up with a minimal (as minimal as possible) example that
crashes and post it.

Thank you all for the help,
Josip

On Sun, Nov 15, 2009 at 10:23 PM, Andreas Fabri

<

<mailto:>>
wrote:

ok, I missed the 'break'.

The code sniplet you show should be ok then, so my guess
is that you there is some bug earlier.

Just the usual question: Do uou use an
Exact_predicates_inexact_constructions_kernel
or something comparable ?

Add assert(T.is_valid()); right before the for loop.

andreas

Josip Dzolonga wrote:

I was referring to this

while(!seen.empty()) {
for(Finite_vertices_iterator vit =
T.finite_vertices_begin();
vit != T.finite_vertices_end(); ++vit) {
if(seen.find(vit->point()) != seen.end()) {
seen.erase(vit->point());
T.remove(vit);
break;
}
}
}

I break the loop after a point is removed. I also tried
the code that you provided, but that unfortunately did
not solve the problem.

Best,
Josip

On Sun, Nov 15, 2009 at 10:08 PM, Andreas Fabri

<

<mailto:>

<mailto:

<mailto:>>>
wrote:

Hi Josip,

I am not sure you understood my explanantion, but it
can also be
that I didn't understand yours.

It is a mistake to do the ++vit, AFTER having called
T.remove(vit),
and that is what your for loop does.

My version makes a copy of thr iterator, advances the
iterator
and only then removes the vertex.

andreas

Josip Dzolonga wrote:

Hi Andreas,

I corrected myself in my latest reply, but that
did not solve
the problem.

Josip

On Sun, Nov 15, 2009 at 9:07 PM, Andreas Fabri

<

<mailto:>

<mailto:

<mailto:>>

<mailto:

<mailto:>

<mailto:

<mailto:>>>>
wrote:

Hi Josip,

You shouldn't expect that ++vit works
correctly after that
you called
T.remove(vit).

You better write this

for(Finite_vertices_iterator vit =
T.finite_vertices_begin();
vit != T.finite_vertices_end();) {

if(seen.find(vit->point()) !=
seen.end()) {
seen.erase(vit->point());
Vertex_handle vh = vit;
++vit;
T.remove(vh);
break;
}
}

Note that the same would be true for a std::list.

andreas

Josip Dzolonga wrote:

Hi Nico,

I thought of that, but at no point I am
reusing old cell
handles/vertex handles. I thought that
while removing them, I
might be causing the problem - but even if
I change to
code to
the following, the problems remains

while(!seen.empty()) {
for(Finite_vertices_iterator vit =
T.finite_vertices_begin();
vit !=
T.finite_vertices_end(); ++vit) {
if(seen.find(vit->point())
!= seen.end()) {
seen.erase(vit->point());
T.remove(vit);
break;
}
}
}

That is, I am iterating again over all
vertices.

Thanks,
Josip

On Sun, Nov 15, 2009 at 8:42 PM, Nico Kruithof

<

<mailto:>

<mailto:

<mailto:>>

<mailto:

<mailto:>

<mailto:

<mailto:>>>

<mailto:

<mailto:>

<mailto:

<mailto:>>

<mailto:

<mailto:>

<mailto:

<mailto:>>>>>

wrote:

Hi Josip,

The assertion says that the vertex is
not contained in
the Cell.
When you remove vertices, cells get
removed and added when
re-triangulating. Internally, CGAL will
reuse the
memory of
deleted
cells for the new cells. This might be
the reason you
are getting
the assertion.
-- Nico

On Sun, Nov 15, 2009 at 6:26 PM, Josip
Dzolonga

<

<mailto:>

<mailto:

<mailto:>>

<mailto:

<mailto:>

<mailto:

<mailto:>>>

<mailto:

<mailto:>

<mailto:

<mailto:>>

<mailto:

<mailto:>

<mailto:

<mailto:>>>>>
wrote:

Hello everyone,

I am trying to remove some certain
points from the
Delaunay
triangulation. I had some problems
even before,
and got some
advice from here, but the problem
still pertains. The
problematic code follows

for(Finite_vertices_iterator vit =
T.finite_vertices_begin();
vit !=
T.finite_vertices_end(); ++vit) {
if(seen.find(vit->point()) !=
seen.end()) {
seen.erase(vit->point());
T.remove(vit);
}
}

Where seen is of type
std::set<Point> and has been
already
filled. Later on when I try to use the
triangulation, I
get the
following error

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
Aborted

Which comes from the function int
index(const
Vertex_handle&
v). I can not remove the same
vertex twice, since I am
iterating
over the finite vertices and this
is the only
place where
vertex
removal is taking place. Any ideas
would be highly
appreciated!

Best,
Josip

-- You are currently subscribed to
cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

-- You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

-- You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Re: [cgal-discuss] Problems with removing points from a triangulation,Take 3, (continued)

List archive

Re: [cgal-discuss] Problems with removing points from a triangulation,Take 3