CGAL users discussion list

[iMunk <>]

Many thanks William, the code works perfect.

Amazing post.

Cheers.

On 12 May 2014 22:17, Thanh Nguyen [via cgal-discuss] <[hidden email]> wrote:

Sorry, i should have sent you an example how it is used.

Attached file include example code, matlab file to plot result polygon, and example result output file.

cheers,

William

attached file is example output of Polygon_with_holes_2

On 12 May 2014, at 21:05, iMunk <[hidden email]> wrote:

The function compile without any change And I have several more questions :)

 what is the second argument in the function alpha_to_polygon? 

A is the first input and contain the information of point whose contour we want to know.

the output is out poly?

where the alpha value can be change?  for sure the number of point in the contour depend on

alpha value.

cheers,

Victor

 

On 12 May 2014 16:50, Thanh Nguyen [via cgal-discuss] <<a href=""x-msg://2/user/SendEmail.jtp?type=node&amp;node=4659297&amp;i=0"" target="_top" rel="nofollow" link="external">[hidden email]> wrote:

Hi Victor,

"auto" is C++11 standard features (https://en.wikipedia.org/wiki/C++11), formerly called C++0x standard

It is useful because i don't need to explicitly declare type of variable.

For example:

Instead of writing this in old C++ standard:

for (typename AlphaShape2::Alpha_shape_edges_iterator it = A.alpha_shape_edges_begin(); it != A.alpha_shape_edges_end(); ++it)

i can write in C++ 11 standard:

for (auto it = A.alpha_shape_edges_begin(); it != A.alpha_shape_edges_end(); ++it)

In order to tell your compiler to enable C++11, you can add this c++ flag 

"-std=c++11" for GNU gcc compiler

or "-std=c++11 -stdlib=libc++"  for clang.

In CMake, you can do this: 

set(CMAKE_CXX_FLAGS  "-std=c++11").

However, you need to check whether your compiler supports C++11 standard features (http://wiki.apache.org/stdcxx/C++0xCompilerSupport)

Otherwise, you need to replace all "auto" with appropriate type declaration :(

cheers,

William

On 12 May 2014, at 14:34, iMunk <[hidden email]> wrote:

Hi William, thanks for your answer.

I can compile one part of your function now, but still I have problems with it.

Specifically with the class "auto" that you use to iterate over the edges among other thing. This class has a members "first, second..." I think that class isn't a standard class in CGAL, where you define it?

I hope you can  continue helping me.

Victor

On 12 May 2014 13:47, Thanh Nguyen [via cgal-discuss] <<a href=""<a" href=""x-msg://6/user/SendEmail.jtp?type=node&amp;amp;node=4659286&amp;amp;i=0">x-msg://6/user/SendEmail.jtp?type=node&amp;node=4659286&amp;i=0"" target="_top" rel="nofollow" link="external">[hidden email]> wrote:

Hi Victor,

I used these types

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;

typedef CGAL::Polygon_2<Kernel> Polygon_2;

typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;

but the types declared in the example  (you mentioned) of boolean set operations also work

http://doc.cgal.org/latest/Boolean_set_operations_2/Boolean_set_operations_2_2connect_polygon_8cpp-example.html#_a4

/usr/bin/ld: /tmp/cc49mLSJ.o: undefined reference to symbol '_ZN5boost6detail12get_tss_dataEPKv'

//usr/lib/x86_64-linux-gnu/libboost_thread.so.1.54.0: error adding symbols: DSO missing from command line

collect2: error: ld returned 1 exit status

this means you didn't link your binary target to libboost_thread (-lboost_thread).

If you use CMake, you better look at examples folder from CGAL source code (CGAL/examples/Boolean_set_operations_2) to see how dependencies are linked.

hope it helps!

--

William

On 12 May 2014, at 10:17, iMunk <[hidden email]> wrote:

Also I check the discussion that you recommended and check this program too

http://doc.cgal.org/latest/Boolean_set_operations_2/Boolean_set_operations_2_2connect_polygon_8cpp-example.html#_a4

This program do not compile and the error is

/usr/bin/ld: /tmp/cc49mLSJ.o: undefined reference to symbol '_ZN5boost6detail12get_tss_dataEPKv'

//usr/lib/x86_64-linux-gnu/libboost_thread.so.1.54.0: error adding symbols: DSO missing from command line

collect2: error: ld returned 1 exit status

Victor

On 12 May 2014 10:07, Victor Rodríguez <<a href=""<a" href=""<a" href=""x-msg://4/user/SendEmail.jtp?type=node&amp;amp;amp;node=4659279&amp;amp;amp;i=0">x-msg://4/user/SendEmail.jtp?type=node&amp;amp;node=4659279&amp;amp;i=0"><a" href=""x-msg://4/user/SendEmail.jtp?type=node&amp;amp;node=4659279&amp;amp;i=0">x-msg://4/user/SendEmail.jtp?type=node&amp;node=4659279&amp;i=0"" target="_top" rel="nofollow" link="external">[hidden email]> wrote:

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] <<a href=""<a" href=""<a" href=""x-msg://4/user/SendEmail.jtp?type=node&amp;amp;amp;node=4659279&amp;amp;amp;i=1">x-msg://4/user/SendEmail.jtp?type=node&amp;amp;node=4659279&amp;amp;i=1"><a" href=""x-msg://4/user/SendEmail.jtp?type=node&amp;amp;node=4659279&amp;amp;i=1">x-msg://4/user/SendEmail.jtp?type=node&amp;node=4659279&amp;i=1"" target="_top" rel="nofollow" link="external">[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

--
Victor

---

View this message in context: Re: alpha shapes 2D

Sent from the cgal-discuss mailing list archive at Nabble.com.

---

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-tp4659269p4659285.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.

---

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-tp4659269p4659291.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.

example.zip (4K) 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-tp4659269p4659298.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.