CGAL users discussion list

[iMunk <>]

Hi William,

Thanks you a lot for you answer, definitely the output of your code is exactly what I need. However I couldn't jump-start your function,

the main reason is that a newbie in CGAL, beside I do know how to  declare the  class "Polygon_with_holes_2" appropriately. 

I did try to put your function inside this code "doc.cgal.org/latest/Alpha_shapes_2/index.html" like  another function but does not work.

the error was:

aS.c:49:53: error: ‘Polygon_with_holes_2’ has not been declared

 inline void alpha_to_polygon(const Alpha_shape_2& A,Polygon_with_holes_2& out_poly) { 

I really appreciate if you can help me again, this time to implement correctly your function.

Thanks again. 

Victor,

On 10 May 2014 18:39, Thanh Nguyen [via cgal-discuss] <[hidden email]> wrote:

Hi iMunk,

> So, what means this output? if I think in points, that one correspond to the
> convex hull. Why 4 row? why 4 columns?

each row is one segment with 2 2D points (format: source.x source.y  
target.x target.y)
After googling intensively, I found out that there is no direct way to  
output polygon from Alpha shape 2D.
Here is one discussion about how to extract ordered polygon from alpha shape:
http://cgal-discuss.949826.n4.nabble.com/Convert-Alpha-Segments-to-an-ordered-Polygon-td3575098.html

However, that discussion only gives suggestions.

Below is my example code to compute general polygon  
(Polygon_with_holes_2) from alpha shape.
This code works for REGULARIZED alpha shape (meaning no isolated  
points or sub polygons).
Attached file is plot of an example output polygon.

// form polygons from alpha shape
inline void alpha_to_polygon(const Alpha_shape_2& A,  
Polygon_with_holes_2& out_poly) {
   typedef typename AlphaShape2::Vertex_handle Vertex_handle;
   typedef typename AlphaShape2::Edge Edge;
   typedef std::vector<Edge> EdgeVector;

   // form vertex to vertex map
   std::map<Vertex_handle, EdgeVector> v_edges_map;
   for (auto it = A.alpha_shape_edges_begin(); it != A.alpha_shape_edges_end();
        ++it) {
     auto edge = *it;  // edge <=> pair<face_handle, vertex id>
     const int vid = edge.second;
     auto v = edge.first->vertex((vid + 1) % 3);
     if (v_edges_map.count(v) == 0) v_edges_map[v] = EdgeVector();
     v_edges_map[v].push_back(edge);
   }

   // form all possible boundaries
   std::vector<Polygon_2> polies;
   std::vector<double> lengths;
   double max_length = 0;
   int max_id = 0;
   std::set<Edge> existing_edges;
   for (auto it = v_edges_map.begin(); it != v_edges_map.end(); ++it) {
     if (existing_edges.count((*it).second.front()))
       continue;

     auto begin_v = (*it).first;
     auto next_e = (*it).second.front();
     auto next_v = next_e.first->vertex((next_e.second + 2)%3);

     Polygon_2 poly;
     poly.push_back(next_v->point());

     existing_edges.insert(next_e);
     if (v_edges_map[begin_v].size() > 1)
       v_edges_map[begin_v].erase(v_edges_map[begin_v].begin());

     double length = CGAL::squared_distance(begin_v->point(), next_v->point());
     while (next_v != begin_v && v_edges_map.count(next_v) > 0) {
       next_e = v_edges_map[next_v].front();
       existing_edges.insert(next_e);
       if (v_edges_map[next_v].size() > 1)
         v_edges_map[next_v].erase(v_edges_map[next_v].begin());

       auto t_next_v = next_e.first->vertex((next_e.second + 2)%3);
       length += CGAL::squared_distance(next_v->point(), t_next_v->point());
       next_v = t_next_v;
       poly.push_back(next_v->point());
     }
     if (max_length < length) {
       max_length = length;
       max_id = polies.size();
     }
     polies.push_back(poly);
     lengths.push_back(length);
   }

   // build polygon with holes
   // the first one is outer boundary, the rest are holes
   Polygon_2 outer_poly = polies[max_id];
   polies.erase(polies.begin() + max_id);
   out_poly = Polygon_with_holes_2(outer_poly, polies.begin(), polies.end());
}


--
William

Quoting iMunk <[hidden email]>:

> Hi every body, I am a medium c++ programmer and I want to use the CGAL
> library to calculate the alpha shapes of a collection of points in a two
> dimension space. I have read the manual of this class and I've a specific
> question about the follow example
>
> doc.cgal.org/latest/Alpha_shapes_2/index.html.
>
> After copy that code in my computer and compile in the correct form in
> Ubuntu, I execute it successfully. However
>
> 1) Despite my points form a surface with cavities, for instance you can
> think in this set (0,2), (-0.5,1), (0,1), (0.5,1), (-2,0), (-1,0), (0,0),
> (1,0), (2,0), (-0.5,-1), (0,-1), (0.5,-1), (0,-2) of points, the output in
> before code coincide with the convex hull, I mean, the output is
>
> -2 0 0 -2
> 0 -2 2 0
> 0 2 -2 0
> 2 0 0 2
>
> So, what means this output? if I think in points, that one correspond to the
> convex hull. Why 4 row? why 4 columns?
>
> I wish a output for the previous set of points -->  (0,2), (-0.5,1),
> (0.5,1), (-2,0), (2,0), (-0.5,-1), (0.5,-1), (0-2) which I think coincide
> with the appropriate alpha shapes.
>
> Any one can help me?
>
> Thanks in advance.
>
>
>
>
>
> --
> View this message in context:  
> http://cgal-discuss.949826.n4.nabble.com/alpha-shapes-2D-tp4659269.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss

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

Screen Shot 2014-05-05 at 2.16.23 PM copy.png (71K) Download Attachment

---

If you reply to this email, your message will be added to the discussion below:

http://cgal-discuss.949826.n4.nabble.com/alpha-shapes-2D-tp4659269p4659270.html

To unsubscribe from alpha shapes 2D, click here.
NAML

--
Victor

---

View this message in context: Re: alpha shapes 2D
Sent from the cgal-discuss mailing list archive at Nabble.com.