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

 [Algorithms] Polygon from point cloud and other from triangle list? From: Jose Marin - 2009-06-24 12:09:17 ```Hi. Do you know some algorithm to create a polygon from a 2D point cloud? Another task would be create a polygon from a bunch of triangles (not related to the above task). The resulting polygon may be non-convex. I have searched, but didn't find any good solution... Thanks. Jose Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ```

 [Algorithms] Polygon from point cloud and other from triangle list? From: Jose Marin - 2009-06-24 12:09:17 ```Hi. Do you know some algorithm to create a polygon from a 2D point cloud? Another task would be create a polygon from a bunch of triangles (not related to the above task). The resulting polygon may be non-convex. I have searched, but didn't find any good solution... Thanks. Jose Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ```
 Re: [Algorithms] Polygon from point cloud and other from triangle list? From: Richard Fabian - 2009-06-24 14:24:13 ```try finding the most "lonely" vertex (one furthest from the average position), then use that as a start point. from the start point, assume an initial direction vector of any non-picked point, then pick points adn compare to see if any of them point "futher out" (have a larger value when dot with outward direction vector (which is just the normalised position of the initial vertex)) once you have the lowest curvature, then continue to the next point, chosing a next vertex that is in the same direction and also low curvature (high dot in forwards (forwards = this point pos - last point pos) with high dot in out (again, just the normalised position of the vertex) once you have done this until the best next point is the initial position, you will have a convex shape that you can start adding the other vertices to. ad vertices one at a time, choose the unpicked vertex that is closest to a line, then add it as a split on that line. repeat until all unpicked vertices are gone. 2009/6/24 Jose Marin : > > Hi. > > Do you know some algorithm to create a polygon from a 2D point cloud? > > Another task would be create a polygon from a bunch of triangles (not related to the above task). > > The resulting polygon may be non-convex. > > I have searched, but didn't find any good solution... > > Thanks. > > Jose > > > >      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 > -- fabs(); Just because the world is full of people that think just like you, doesn't mean the other ones can't be right. ```
 Re: [Algorithms] Polygon from point cloud and other from triangle list? From: James Robertson - 2009-06-24 15:03:15 ```Something like a Voronoi diagram? http://en.wikipedia.org/wiki/Voronoi_diagram Jose Marin wrote: > Hi. > > Do you know some algorithm to create a polygon from a 2D point cloud? > > Another task would be create a polygon from a bunch of triangles (not related to the above task). > > The resulting polygon may be non-convex. > > I have searched, but didn't find any good solution... > > Thanks. > > Jose > > > > 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 > > ```
 Re: [Algorithms] Polygon from point cloud and other from triangle list? From: Rachel Blum - 2009-06-24 21:34:16 Attachments: Message as HTML ```What you are looking for is probably "Alpha Shapes". This PDF: http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf is a good starting point. (Sorry if that is a duplicate or even triplicate post - I just changed mailing addresses, and mailman mumbled something about "message being held for moderation"....) Rachel ```
 Re: [Algorithms] Polygon from point cloud and other from triangle list? From: Rachel Blum - 2009-06-24 21:37:10 Attachments: Message as HTML ```What you are looking for is probably "Alpha Shapes". This PDF: http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf is a good starting point. (Sorry if that is a duplicate or even triplicate post - I just changed mailing addresses, and mailman mumbled something about "message being held for moderation"....) Rachel ```