
Geometry : 
Subject: [ggl] Problem with sorting points in Polygon
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 20110524 16:04:12
It looks to me like you could use the delaunay triangulation of the point cloud and discard all edges that are greater than your alpha threshold then merge to compute the alpha shape in n log n time. I'm sure there must be a more direct way with smaller constant factor. Nearest neighbor query could be used based on a query tree.
Original Message
From: gglbounces_at_[hidden] [mailto:gglbounces_at_[hidden]] On Behalf Of Markus Eich
Sent: Tuesday, May 24, 2011 4:58 AM
To: ggl_at_[hidden]
Subject: [ggl] Problem with sorting points in Polygon
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 MarySomervilleStr. 9 28359 Bremen, Germany Phone: +49 (0)421 178454105 Fax: +49 (0)421 178454150 EMail: markus.eich_at_[hidden] Weitere Informationen: http://www.dfki.de/robotik  Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH Firmensitz: Trippstadter Stra?e 122, D67663 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) UStId.Nr.: DE 148646973 Steuernummer: 19/673/0060/3 
Geometry list run by mateusz at loskot.net