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

Subject: [ggl] Problem with sorting points in Polygon
From: Barend Gehrels (barend)
Date: 2011-05-24 21:02:41

Hi Markus,

Welcome to GGL and this list.

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

So you probably want to remove all internal edgjes.

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

The correct method is for orientation and closing the polygon. It will 
not rearrange it. There is a "dissolve" method in extensions, designed 
for doing this, but it only works for small artefacts are not for spider 
like polygons like this.

You might try "makeValid" of SQL Server or SqlGeometry (.NET), I've good 
experience with that. But it follows the winding rule and I don't know 
if you want that. See also
<http://barendgehrels.blogspot.com/2011/02/dissolving-pentagram.html>

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

Sure, it will do.

> I could of course apply the convex hull detection, but I want to 
> reconstruct the shape in a concave way.

I see. Then convex hull does not help you neither.

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

I'm not calling this "sorting", but understand what you will do. Just 
get the concave hull. Boost.Geometry cannot currently do this in a 
proper way.

Regards, Barend