CGAL users discussion list

[Thanh Quoc Nguyen <>]

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 
<>:

> 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

Attachment: Screen Shot 2014-05-05 at 2.16.23 PM copy.png
Description: PNG image