CGAL users discussion list

[Stefan Salewski <>]

On Sun, 2013-09-29 at 08:45 +0200, Michael Hoffmann wrote:
> If you label the vertices of your constrained polygons by
> component/polygon (i.e., the first by 1, the second by 2, etc.), you
> can just iterate over the edges of the triangulation and select those
> whose endpoints have the same label.
> 
> It sounds like you know those polygons because they are part of your
> input. If not, you might have to compute them via BFS/DFS or so.
> For the labels you can use the vertex_with_info classes.
> 

Thanks for your reply. So it seems that there is no direct support from
inside CGAL to that problem -- good to know that, so some 'manual' work
is necessary. Your proposal is similar to my own idea, but I am not sure
if your proposal really will work: If my first polygon is build from 4
constrained edges, I can label the corresponding 4 vertices all with
label "1":

1-----1
|   / |
| /   |
1-----1

So the 4 outer edges end at vertices labeled "1", but the inner diagonal
edge too.

My idea was: I mark all vertices which are part of constrained polygons,
i.e mark all with identical label "1". And I store all the vertices
which build by constrained polygons in a hash, where has key is the
tupel of the two endpoints (coordinates or vertices). I can iterate over
all vertices, and query for each vertex the neighbor vertices. If
current vertex and one neighbor vertex are both marked as "constraint
vertex" but are not contained in the has, then it is a inner edge, and I
can remove it.

Oh -- I see the problem: That may remove edges between distinct but
adjanced polygons. So indeed I have to label each polygon with a uniq
label, all outer vertices of first polygon "1", all vertices of second
polygon "2". Than I can remove edges between vertices with same label,
which are not in the hash.

Thanks,

Stefan Salewski