Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Convert Alpha-Segments to an ordered Polygon

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Convert Alpha-Segments to an ordered Polygon


Chronological Thread 
  • From: Andreas Fabri <>
  • To:
  • Subject: Re: [cgal-discuss] Convert Alpha-Segments to an ordered Polygon
  • Date: Mon, 06 Jun 2011 16:34:01 +0200
  • Organization: GeometryFactory


Hi Markus,

Admittedly, the information you look for is hard to find.

Things are spread over several manual pages, and it is
not written in the reference manual page of the Alpha Shape
class that it publicly derives from the Delaunay_triangulation_2.

This class derives from the class Triangulation_2.
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2_ref/Class_Triangulation_2.html#Cross_link_anchor_1304

There you find the type

Triangulation_2<Traits,Tds>::Edge_circulator
circulator over all edges incident to a given vertex.




and the function

Edge_circulator t.incident_edges ( Vertex_handle v, Face_handle f)
const
Starts at the first edge of f incident to v, in counterclockwise order around v.
Precondition: Face f is incident to vertex v.


This allows you to traverse the circular list of edges.
For each such edge you call the classify function of
the Alpha shape.

andreas




On 06/06/2011 15:10, Markus Eich wrote:
Thank you Andreas,

So lets say I create my alpha shapes
================
// compute alpha shape
Alpha_shape_2 as(lp.begin(),lp.end());
================
than I get my first edge from the alpha_shape:

=======================
Dt::Edge edge,next_edge;
Alpha_shape_edges_iterator iter = as.alpha_shape_edges_begin();
edge = *iter;

==========================
And now I want to get the adjacent edge (say next_edge in clockwise
order). How can I get it? I might look stupid but I don't get it how to
circulate the edges of a alpha shape in a sorted order.

Mayby you can point me to an example?

Thank you

Markus







On 06.06.2011 14:07, Andreas Fabri wrote:

Edge is a std::pair<Face_handle,int>

From the face you can get the two vertices
with index different from the index in the pair.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/TDS_2_ref/Concept_TriangulationDSFaceBase_2.html#Cross_link_anchor_1316


andreas


On 06/06/2011 13:27, Markus Eich wrote:
Thank you for the input. My question is now how can I access the
neighbors of an edge using CGAL?

Is there an overridden function like as.segment(*it).get_neighbor() ?
The link

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/TDS_2_ref/Concept_TriangulationDSFaceBase_2.html#Cross_link_anchor_1316



doesn't tell me anything (sorry i am a CGA newbie). If I have the
segment A from the Alpha_shape_edges_iterator, how can I get the
adjactend Vertices. How can I extend my little example to get the two
adjacend edges?

////////////////////
for(Alpha_shape_edges_iterator it = as.alpha_shape_edges_begin();it !=
as.alpha_shape_edges_end(); ++it) {
segments.push_back(as.segment(*it));



}

////////////////////

Cheers,

Markus



On 06.06.2011 08:55, Sebastien Loriot (GeometryFactory) wrote:
Markus Eich wrote:
Dear all,

I am using CGAL in order the get one or more alpha polygons from a
shape. IN a first approach I assume there are no holes. I generate
the segements as follows:


Alpha_shape_2 as(lp.begin(),lp.end());

// find optimal alpha value

Alpha_iterator opt = as.find_optimal_alpha(1);
as.set_alpha((*opt)*2.0f);
as.set_mode(Alpha_shape_2::REGULARIZED);

std::vector<K::Segment_2> segments;
std::vector<K::Segment_2> sorted_segments;

for(Alpha_shape_edges_iterator it = as.alpha_shape_edges_begin();it
!= as.alpha_shape_edges_end(); ++it)
segments.push_back(as.segment(*it));

std::cout << segments.size() << " alpha shape edges" << std::endl;


This works fine an I get all the segments. My problem is that I need
a single polygon (in my example I only have one concave shape). If I
iterate over the std::vector<K::Segment_2> segments vector, the
segments are like E,A,V,D,C,F , instead of A,B,C,D,E,F. In need the
segments in an ordered way i.e. that the .target() of A is the
.source() of B, the .target() of B the source of C, and so on.

How can I achieve this using CGAL? Is there a way to sort the
segments directly?

There is nothing to do it directly in CGAL.

This is a simple graph problem: each edge has 2 vertices and two
adjacent edges share one identical vertex. In particular each such
vertex is adjacent to two other vertices. Starting from one vertex
and going from adjacent vertex to adjacent vertex you can reconstruct
the polygon.

You can use for example a
std::map<Vertex_handle,std::vector<Vertex_handle> >
to get the adjacency between vertices.

For the definition of an edge as std::pair<Face_handle,int>, see:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/TDS_2_ref/Concept_TriangulationDSFaceBase_2.html#Cross_link_anchor_1316






S.





Thank you and cheers,

Markus












--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912 skype: andreas.fabri



Archive powered by MHonArc 2.6.16.

Top of Page