Geometry Boost List: [ggl] Problem with sorting points in Polygon

Subject: [ggl] Problem with sorting points in Polygon
From: Markus Eich (markus.eich)
Date: 2011-05-24 11:42:58

Dear all

I am trying to recover the "concave" shape of a point cloud. For this I 
use a method called Alpha Shapes (in CGAL) or Pivoting Ball Algroithm. 
The shape is not convex (but could be).
The problem of th algorithm is that the points are not "ordered". For 
instance, if I take a rectangular shape it looks like the screenshot 
attached.

I though that using boost geometry would help. I filled the polygon_2d 
structure and applied the "correct" method,

After filling the polygon Struct and applying the correct method, the 
shape looks still like a spiderweb, not like a propper square, as it should.
I could of course apply the convex hull detection, but I want to 
reconstruct the shape in a concave way.

Do you have any clues? Does the correct method really sort my points in 
the polygon? What other sorting options to I have?

I am new go Boost::geometry

Cheers,

Markus

Here is my code snipped:

======================================================================

     boost::geometry::polygon_2d sorted_poly;

     //get points from the CGAL in an unorganized way

     for(Vertice_iterator it = as.alpha_shape_vertices_begin(); it != 
as.alpha_shape_vertices_end(); it++){
         Alpha_shape_2::Vertex_handle vh = *it;
         boost::geometry::append(sorted_poly, 
boost::geometry::make<boost::geometry::point_2d>(vh->point().x(),vh->point().y()));
     }

     boost::geometry::correct(sorted_poly);

     std::size_t numPoints=boost::geometry::num_points (sorted_poly);

     boost::geometry::linear_ring<boost::geometry::point_2d> outer= 
sorted_poly.outer();

     //Reproject points and fill PC structure
     for (size_t i=0;i<numPoints;i++)
     {
         Eigen::Vector3f pbbx;
         //take first and second dimension of the outer polygon ring

         pbbx=boost::geometry::get<0>(outer[i])*u;
         pbbx+=boost::geometry::get<1>(outer[i])*v;
         pbbx+=p0;
         alpha_shape.push_back(pcl::PointXYZ(pbbx[0],pbbx[1],pbbx[2]));
     }

    }

======================================================================

-- 
Dipl. Inf. Markus Eich
Researcher
DFKI Bremen
Robotics Innovation Center
Mary-Somerville-Str. 9
28359 Bremen, Germany
Phone: [phone]
Fax:   [phone]
E-Mail: markus.eich_at_[hidden]
Weitere Informationen: http://www.dfki.de/robotik
-----------------------------------------------------------------------
Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
Firmensitz: Trippstadter Stra?e 122, D-67663 Kaiserslautern
Geschaeftsfuehrung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
(Vorsitzender) Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
Sitz der Gesellschaft: Kaiserslautern (HRB 2313)
USt-Id.Nr.:    DE 148646973
Steuernummer:  19/673/0060/3
-----------------------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Bildschirmfoto.png
Type: image/png
Size: 34682 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/ggl/attachments/20110524/2b138857/Bildschirmfoto-0001.png