CGAL users discussion list

[Andreas Fabri <>]

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