## Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list?

 Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? From: Sam Martin - 2009-06-26 08:44:36 ```> Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. I haven't come across alpha shapes before, but from the previous links this sounds like it's exactly an alpha shape? All alpha shapes are a subset of the delaunay triangulation of the point set. The alpha value just defines the particular subset. Or am I missing something? Ta, Sam From: Jon Watte [mailto:jwatte@...] Sent: 25 June 2009 01:54 To: Game Development Algorithms Subject: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? An alpha shape is not guaranteed to be a closed non-overlapping polygon, though, which I think that the original requester needs. Specifically, an alpha shape may create thin "bridges" of areas where two vertices are connected "both ways" and thus generate an infinitely thin connection. Non-convex hulls are a better fit, if you don't need to punch holes into your polygon (e g if there are no "lakes" in the middle that you want open/not covered). Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. To make it well defined, you probably want to remove the largest removable triangle from each pass of border triangle removal.. Sincerely, jw metanet software wrote: hi, you might also want to check out alpha shapes and non-convex hulls: http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html raigan --- On Wed, 6/24/09, Jose Marin wrote: From: Jose Marin Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? To: "Game Development Algorithms" Received: Wednesday, June 24, 2009, 3:03 PM Thanks for the ideas, Jon! If I find a good algorithm, I'll post it here, if someone is interested. Regards Jose ----- Mensagem original ---- De: Jon Watte Para: Game Development Algorithms Enviadas: Quarta-feira, 24 de Junho de 2009 15:31:56 Assunto: Re: [Algorithms] Res: Polygon from point cloud and other from triangle list? Jose Marin wrote: I need to find the outline polygon (may be non-convex, and will be on most of the times) defined by the resulting shape.   The problem is that "the outline polygon" is not well defined, if you allow it to be non-convex. If you can define what it means to be "the outline polygon," that would get you closer to an algorithm. Write down a number of cases on paper. Draw what you think should be the resulting polygon. Try to figure out what rule you, yourself, use to create that polygon. For example, you can start with the polygon that consists of all the shapes -- this is a polygon; it's just disjoint. Now, you probably want it to be connected. That's one requirement right there. How would you go about connecting those shapes? The answer to that question is not well defined, either, but it's a start. Sincerely, jw --   Revenge is the most pointless and damaging of human desires. ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list       Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list __________________________________________________________________ The new Internet Explorer® 8 - Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/ ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list -- Revenge is the most pointless and damaging of human desires. ```

 Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? From: metanet software - 2009-06-24 23:17:23 ```hi, you might also want to check out alpha shapes and non-convex hulls: http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html raigan --- On Wed, 6/24/09, Jose Marin wrote: > From: Jose Marin > Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? > To: "Game Development Algorithms" > Received: Wednesday, June 24, 2009, 3:03 PM > > Thanks for the ideas, Jon! > > If I find a good algorithm, I'll post it here, if someone > is interested. > > Regards > > Jose > > > > ----- Mensagem original ---- > De: Jon Watte > Para: Game Development Algorithms > Enviadas: Quarta-feira, 24 de Junho de 2009 15:31:56 > Assunto: Re: [Algorithms] Res: Polygon from point cloud and > other from triangle list? > > Jose Marin wrote: > > I need to find the outline polygon (may be non-convex, > and will be on most of the times) defined by the resulting > shape. > >  > > The problem is that "the outline polygon" is not well > defined, if you > allow it to be non-convex. > If you can define what it means to be "the outline > polygon," that would > get you closer to an algorithm. > Write down a number of cases on paper. Draw what you think > should be the > resulting polygon. Try to figure out what rule you, > yourself, use to > create that polygon. > > For example, you can start with the polygon that consists > of all the > shapes -- this is a polygon; it's just disjoint. Now, you > probably want > it to be connected. That's one requirement right there. How > would you go > about connecting those shapes? The answer to that question > is not well > defined, either, but it's a start. > > Sincerely, > > jw > > > -- > >   Revenge is the most pointless and damaging of human > desires. > > > ------------------------------------------------------------------------------ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > >       Veja quais são os assuntos do momento > no Yahoo! +Buscados > http://br.maisbuscados.yahoo.com > > ------------------------------------------------------------------------------ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > __________________________________________________________________ The new Internet Explorer® 8 - Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/ ```
 Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? From: Jon Watte - 2009-06-25 00:59:15 ``` An alpha shape is not guaranteed to be a closed non-overlapping polygon, though, which I think that the original requester needs. Specifically, an alpha shape may create thin "bridges" of areas where two vertices are connected "both ways" and thus generate an infinitely thin connection.

Non-convex hulls are a better fit, if you don't need to punch holes into your polygon (e g if there are no "lakes" in the middle that you want open/not covered).

Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. To make it well defined, you probably want to remove the largest removable triangle from each pass of border triangle removal..

Sincerely,

jw

metanet software wrote:
hi, you might also want to check out alpha shapes and non-convex hulls:   http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html; http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf; http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html;  raigan   --- On Wed, 6/24/09, Jose Marin <jose_marin2@...> wrote:
From: Jose Marin <jose_marin2@...> Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? To: "Game Development Algorithms" <gdalgorithms-list@...> Received: Wednesday, June 24, 2009, 3:03 PM  Thanks for the ideas, Jon!  If I find a good algorithm, I'll post it here, if someone is interested.  Regards  Jose    ----- Mensagem original ---- De: Jon Watte <jwatte@...> Para: Game Development Algorithms <gdalgorithms-list@...> Enviadas: Quarta-feira, 24 de Junho de 2009 15:31:56 Assunto: Re: [Algorithms] Res: Polygon from point cloud and other from triangle list?  Jose Marin wrote:
I need to find the outline polygon (may be non-convex,
and will be on most of the times) defined by the resulting shape.

The problem is that "the outline polygon" is not well defined, if you  allow it to be non-convex. If you can define what it means to be "the outline polygon," that would  get you closer to an algorithm. Write down a number of cases on paper. Draw what you think should be the  resulting polygon. Try to figure out what rule you, yourself, use to  create that polygon.  For example, you can start with the polygon that consists of all the  shapes -- this is a polygon; it's just disjoint. Now, you probably want  it to be connected. That's one requirement right there. How would you go  about connecting those shapes? The answer to that question is not well  defined, either, but it's a start.  Sincerely,  jw   --     Revenge is the most pointless and damaging of human desires.   ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list; Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list;          Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com;  ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list; Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list;
__________________________________________________________________ The new Internet Explorer® 8 - Faster, safer, easier.  Optimized for Yahoo!  Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/;  ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list; Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list;

--
Revenge is the most pointless and damaging of human desires.
```
 Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? From: Sam Martin - 2009-06-26 08:44:36 ```> Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. I haven't come across alpha shapes before, but from the previous links this sounds like it's exactly an alpha shape? All alpha shapes are a subset of the delaunay triangulation of the point set. The alpha value just defines the particular subset. Or am I missing something? Ta, Sam From: Jon Watte [mailto:jwatte@...] Sent: 25 June 2009 01:54 To: Game Development Algorithms Subject: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? An alpha shape is not guaranteed to be a closed non-overlapping polygon, though, which I think that the original requester needs. Specifically, an alpha shape may create thin "bridges" of areas where two vertices are connected "both ways" and thus generate an infinitely thin connection. Non-convex hulls are a better fit, if you don't need to punch holes into your polygon (e g if there are no "lakes" in the middle that you want open/not covered). Perhaps something reasonable could be had by calculating the Delaunay triangulation (which will give you the convex hull), and then removing triangles from the boundary iteratively until you can remove no more triangle without breaking whatever connectedness/area rule you want to enforce. To make it well defined, you probably want to remove the largest removable triangle from each pass of border triangle removal.. Sincerely, jw metanet software wrote: hi, you might also want to check out alpha shapes and non-convex hulls: http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html raigan --- On Wed, 6/24/09, Jose Marin wrote: From: Jose Marin Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? To: "Game Development Algorithms" Received: Wednesday, June 24, 2009, 3:03 PM Thanks for the ideas, Jon! If I find a good algorithm, I'll post it here, if someone is interested. Regards Jose ----- Mensagem original ---- De: Jon Watte Para: Game Development Algorithms Enviadas: Quarta-feira, 24 de Junho de 2009 15:31:56 Assunto: Re: [Algorithms] Res: Polygon from point cloud and other from triangle list? Jose Marin wrote: I need to find the outline polygon (may be non-convex, and will be on most of the times) defined by the resulting shape.   The problem is that "the outline polygon" is not well defined, if you allow it to be non-convex. If you can define what it means to be "the outline polygon," that would get you closer to an algorithm. Write down a number of cases on paper. Draw what you think should be the resulting polygon. Try to figure out what rule you, yourself, use to create that polygon. For example, you can start with the polygon that consists of all the shapes -- this is a polygon; it's just disjoint. Now, you probably want it to be connected. That's one requirement right there. How would you go about connecting those shapes? The answer to that question is not well defined, either, but it's a start. Sincerely, jw --   Revenge is the most pointless and damaging of human desires. ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list       Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list __________________________________________________________________ The new Internet Explorer® 8 - Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/ ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list -- Revenge is the most pointless and damaging of human desires. ```