From: Simon Fenney <simon.fenney@po...>  20090624 14:32:46

Jose Marin wrote: > Hi. > > Do you know some algorithm to create a polygon from a 2D point cloud? > The resulting polygon may be nonconvex. What other constraints are required? If none then, AFAICS, given N points you could create (N1)!/2 different (potentially selfintersecting) polygons. Simon 
From: Simon Fenney <simon.fenney@po...>  20090624 14:32:46

Jose Marin wrote: > Hi. > > Do you know some algorithm to create a polygon from a 2D point cloud? > The resulting polygon may be nonconvex. What other constraints are required? If none then, AFAICS, given N points you could create (N1)!/2 different (potentially selfintersecting) polygons. Simon 
From: Jose Marin <jose_marin2@ya...>  20090624 14:57:53

Hmm, really, its a very generic question, I should be more detailed. I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape. Something like a tangram shape, that is formed by smaller shapes. I need to find the outline polygon (may be nonconvex, and will be on most of the times) defined by the resulting shape.  Mensagem original  De: Simon Fenney <simon.fenney@...> Para: Game Development Algorithms <gdalgorithmslist@...> Enviadas: Quartafeira, 24 de Junho de 2009 10:28:23 Assunto: Re: [Algorithms] Polygon from point cloud and other from triangle list? Jose Marin wrote: > Hi. > > Do you know some algorithm to create a polygon from a 2D point cloud? > The resulting polygon may be nonconvex. What other constraints are required? If none then, AFAICS, given N points you could create (N1)!/2 different (potentially selfintersecting) polygons. Simon  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com 
From: Richard Fabian <raspo1@gm...>  20090625 09:28:41

this is a completely different problem, this is just a polygon union function isn't it? 2009/6/24 Jose Marin <jose_marin2@...>: > > Hmm, really, its a very generic question, I should be more detailed. > > I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape. > > Something like a tangram shape, that is formed by smaller shapes. > > I need to find the outline polygon (may be nonconvex, and will be on most of the times) defined by the resulting shape. >  fabs(); Just because the world is full of people that think just like you, doesn't mean the other ones can't be right. 
From: Jose Marin <jose_marin2@ya...>  20090625 11:16:23

Yes, polygon union! I should have done more research before posting, so the description of the problem would be more clear. I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library. Thanks  Mensagem original  De: Richard Fabian <raspo1@...> Para: Game Development Algorithms <gdalgorithmslist@...> Enviadas: Quintafeira, 25 de Junho de 2009 6:28:18 Assunto: Re: [Algorithms] Res: Polygon from point cloud and other from triangle list? this is a completely different problem, this is just a polygon union function isn't it? 2009/6/24 Jose Marin <jose_marin2@...>: > > Hmm, really, its a very generic question, I should be more detailed. > > I have some shapes, grouped together, and would like to create a polygon that represents the resulting shape. > > Something like a tangram shape, that is formed by smaller shapes. > > I need to find the outline polygon (may be nonconvex, and will be on most of the times) defined by the resulting shape. >  fabs(); Just because the world is full of people that think just like you, doesn't mean the other ones can't be right.  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com 
From: Jon Watte <jwatte@gm...>  20090625 20:26:49

Jose Marin wrote: > Yes, polygon union! > > I should have done more research before posting, so the description of the problem would be more clear. > > I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library. > > Are your polygons already overlapping, and all you need to do is ensure no selfoverlap in the output? Or do you not need the final union to be fully connected using nondegenerate faces? Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Jose Marin <jose_marin2@ya...>  20090626 13:17:17

Think on a Tangram game. The pieces aren't overlapping. They are all convex, but the resulting image can be nonconvex. I need to determinate the union of the shapes, creating a polygon of the resulting image. For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle. If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit.  Mensagem original  De: Jon Watte <jwatte@...> Para: Game Development Algorithms <gdalgorithmslist@...> Enviadas: Quintafeira, 25 de Junho de 2009 17:26:39 Assunto: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? Jose Marin wrote: > Yes, polygon union! > > I should have done more research before posting, so the description of the problem would be more clear. > > I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library. > > Are your polygons already overlapping, and all you need to do is ensure no selfoverlap in the output? Or do you not need the final union to be fully connected using nondegenerate faces? Sincerely, jw  Revenge is the most pointless and damaging of human desires.  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist ____________________________________________________________________________________ Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com 
From: Peter Lipson <peter@to...>  20090626 15:20:54

that sounds like you only need to remove internal edges. You're learning that specifying a problem clearly is sometimes harder than coming up with the solution! It sounds to me like you have a set of polygons (specified by vertices only?) and you need to find out which ones share edges, and remove the unnecessary edges. If you really are mimicking the Tangram game, there's no requirement that vertices adjoin. So you need to focus on the edges  identify the ones that are collinear and combine the polygons that share them, removing edges and possibly creating new vertices. So first identify the data structure that makes this task easiest. If I've identified the problem correctly, you need a structure with edges, not just vertices. So convert your data to that. Then you need an algorithm to search through the edges and find out which ones are candidates for removal. If this is for a class assignment or some other nonrealtime project, you probably don't need to worry about extremely efficient data structures or optimized algorithms (which is what gets the readers of this list excited :) Jose Marin wrote: > Think on a Tangram game. > The pieces aren't overlapping. > They are all convex, but the resulting image can be nonconvex. > I need to determinate the union of the shapes, creating a polygon of the resulting image. > > For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle. > > If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit. > > > >  Mensagem original  > De: Jon Watte <jwatte@...> > Para: Game Development Algorithms <gdalgorithmslist@...> > Enviadas: Quintafeira, 25 de Junho de 2009 17:26:39 > Assunto: Re: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? > > Jose Marin wrote: > >> Yes, polygon union! >> >> I should have done more research before posting, so the description of the problem would be more clear. >> >> I have found some libraries that do that, but all that I need is a simple algorithm to compute the union, not a full feature geometry library. >> >> >> > > Are your polygons already overlapping, and all you need to do is ensure > no selfoverlap in the output? Or do you not need the final union to be > fully connected using nondegenerate faces? > > Sincerely, > > jw > > > > > > 
From: Jon Watte <jwatte@gm...>  20090627 22:03:39

Ah, you want to "fill in" any "lakes" created! Alpha shapes, and polygon union, are not the right solutions for that. If they are not overlapping, then they need to be touching to create a "seal." I assume that you use snapping or something to make this well behaved. If you allow connection edgetoedge and vertextoedge, rather than just vertextovertex, then first you need to tesselate the touching polygons by subdividing edges where they touch the other vertices. Once you have done that, create the triangle mesh that is the union of the existing polygons. At this point, you can identify which groups of triangles make their own "islands." At this point, all you need to do is the "cap holes" algorithm on the resulting islands (I'm sure you're familiar with it from various 3D tools). This basically means identifying open edge loops that are not the "outside" loop, and tesselating that loop as a convex polygon to generate triangles. The only problem is figuring out which loop is "outside" and which is "inside." If there is only one loop, then that's "outside." If there is more than one loop, then you can test for triangle overlap; the "outside" loop, tesselated, will encompass all "inside" loops. There is still one problem: When you join two polygons vertextovertex, the loop/edge following needs to not "cross over" to create two overlapping loops. There are various options; for example, if you start on an edge that you know is "outside," then you always take the outgoing edge in such an X intersection that curves the most outwards, which ends up being a maximum value (or minimum value) test of a cross product (testing just the sign is not good enough). Something like that? Sincerely, jw Jose Marin wrote: > Think on a Tangram game. > The pieces aren't overlapping. > They are all convex, but the resulting image can be nonconvex. > I need to determinate the union of the shapes, creating a polygon of the resulting image. > > For example, if the pieces are forming a rectangle, the resulting polygon has four line segments, the outline of that rectangle. > > If the pieces are forming a rabbit, I need to determinate the polygon (or polygons) of the outline of the rabbit. > >  Revenge is the most pointless and damaging of human desires. 
From: Jon Watte <jwatte@gm...>  20090624 18:32:06

Jose Marin wrote: > I need to find the outline polygon (may be nonconvex, 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 nonconvex. 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. 
From: Jose Marin <jose_marin2@ya...>  20090624 19:04:01

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 <gdalgorithmslist@...> Enviadas: Quartafeira, 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 nonconvex, 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 nonconvex. 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.  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com 