CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

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