CGAL users discussion list

[Christian Brunschen <>]

On 19 Aug 2010, at 22:22, Ben Supnik wrote:

> Hi Y'all,
> 
> I'm looking for the right term for an algorithm to determine the largest 
> "width" of a polygon.  Colloquially, I want to identify how "thin" a 
> polygon is...in other words, I want to identify slivers and long thin 
> winding polygons vs. large round areas.
> 
> Naively I think I could do an inset using a minkowski sum and if my 
> resulting set is empty, I know that no point was "wider" than the 2x the 
> diamater of the shape I used for convolution.
> 
> Are there metrics or algorithms that compute this kind of value more 
> directly?  If anyone has a search term for the type of computational 
> geometry problem I'm looking at, a hint would be much appreciated.

Please bear with me - I am a complete layman, but for some reason think I 
have a couple of potentially useful ideas.

If you know that the polygons are going to mostly convex, then calculating 
the Convex Hull, and then finding the 'longest' and 'shortest' axes of the 
convex hull, and calculating the ratios of these longest and shortest axes, 
might be sufficient to differentiate between 'long&thin' and 'round' 
polygons, respectively.

For a more general case, it might help to calculate the Voronoi Diagram of 
the polygons in question, and at each Voronoi Vertex that lies inside the 
polygon you should then be able to calculate the distance from that Vertex to 
the nearest edges of the polygon. A longer, thinner polygon will have its 
voronoi vertices with smaller distances from the polygon's edges; a 'rounder' 
polygon will have more voronoi vertices with larger distances from the 
polygon's edges.

Another possibility, to calculate how 'winding' the polygon is, might be to 
calculate how often a line (one that crosses the polygon entirely) intersects 
the polygon's edges. The more 'winding' the polygon is, the more 
intersections there should be. 

My apologies if I'm just confusing matters.

Best wishes,

// Christian Brunschen



> 
> cheers
> Ben
> -- 
> Scenery Home Page: http://scenery.x-plane.com/
> Scenery blog: http://xplanescenery.blogspot.com/
> Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> X-Plane Wiki: http://wiki.x-plane.com/
> Scenery mailing list: 
> 
> Developer mailing list: 
> 
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>