CGAL users discussion list

Quoting "Ben Supnik" 
<>:

> Hi Efi,
>
> It took me a very long time to have even a 30% understanding of what  
> you  wrote here...eventually I found a real-time Minkowski sum  
> applet that let me visualize this.
>
> If I understand correctly, given a concave, "thin", "L"-shaped  
> polygon, the width of the polygon is going to be relatively, um, big.
>
> In the attached picture, the shortest distance from a side of the  
> minkowski sum to the origin is quite a bit longer than the short  
> sides of the L-shaped polygon.
>
> Does the attached diagram correctly visualize a polygon's "width"  
> using Minkowski sums?

Yes it does. It may not be what you are looking for, but this is what  
is called the (directional) width of a point set in comp. geometry.

> Thanks!
> Ben
>
>
>  wrote:
> > In CG there are these notions of width:
> > 1. The width of a set of points P ⊆ R^d is the minimum distance  
> > between parallel hyperplanes supporting the convex hull of P.
> > 2. Given a normalized vector v, the directional width is the  
> > distance between parallel hyperplanes supporting the convex hull of  
> > P and orthogonal to v.
> >
> > So the width (resp. the directional width) of P is the penetration  
> > depth (resp. the directional penetration depth) of P and a copy of P.
> >
> > width(P) = penetration-depth(P,P) = inf{|| t|| | t /∈ (P ⊕ −P), t ∈ R^d}
> >
> > In simple words the width of a polygon is the smallest distance of  
> > the origin from the boundary of the Minkowski sum of P and -P (P  
> > reflected about the origin). The directional width in the direction  
> > of a given vector v is the distance of the origin from the boundary  
> > of the Minkowski sum of P and -P in the direction of v.
> >
> > Quoting "Ben Supnik" 
> > <>:
> >
> > > 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.
> > >
> > > 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
>
> --
> 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