Thread: Re: [Algorithms] Polygon from point cloud and other from triangle list?
Brought to you by:
vexxed72
From: Simon F. <sim...@po...> - 2009-06-24 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 non-convex. What other constraints are required? If none then, AFAICS, given N points you could create (N-1)!/2 different (potentially self-intersecting) polygons. Simon |
From: Jose M. <jos...@ya...> - 2009-06-24 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 non-convex, and will be on most of the times) defined by the resulting shape. ----- Mensagem original ---- De: Simon Fenney <sim...@po...> Para: Game Development Algorithms <gda...@li...> Enviadas: Quarta-feira, 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 non-convex. What other constraints are required? If none then, AFAICS, given N points you could create (N-1)!/2 different (potentially self-intersecting) polygons. Simon ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... 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 |
From: Richard F. <ra...@gm...> - 2009-06-25 09:28:41
|
this is a completely different problem, this is just a polygon union function isn't it? 2009/6/24 Jose Marin <jos...@ya...>: > > 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 non-convex, 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 M. <jos...@ya...> - 2009-06-25 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 <ra...@gm...> Para: Game Development Algorithms <gda...@li...> Enviadas: Quinta-feira, 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 <jos...@ya...>: > > 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 non-convex, 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. ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... 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 |
From: Jon W. <jw...@gm...> - 2009-06-25 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 self-overlap in the output? Or do you not need the final union to be fully connected using non-degenerate faces? Sincerely, jw -- Revenge is the most pointless and damaging of human desires. |
From: Jose M. <jos...@ya...> - 2009-06-26 13:17:17
|
Think on a Tangram game. The pieces aren't overlapping. They are all convex, but the resulting image can be non-convex. 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 <jw...@gm...> Para: Game Development Algorithms <gda...@li...> Enviadas: Quinta-feira, 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 self-overlap in the output? Or do you not need the final union to be fully connected using non-degenerate faces? Sincerely, jw -- Revenge is the most pointless and damaging of human desires. ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... 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 |
From: Peter L. <pe...@to...> - 2009-06-26 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 non-realtime 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 non-convex. > 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 <jw...@gm...> > Para: Game Development Algorithms <gda...@li...> > Enviadas: Quinta-feira, 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 self-overlap in the output? Or do you not need the final union to be > fully connected using non-degenerate faces? > > Sincerely, > > jw > > > > > > |
From: Jon W. <jw...@gm...> - 2009-06-27 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 edge-to-edge and vertex-to-edge, rather than just vertex-to-vertex, 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 vertex-to-vertex, 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 non-convex. > 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 W. <jw...@gm...> - 2009-06-24 18:32:06
|
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. |
From: Jose M. <jos...@ya...> - 2009-06-24 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 <jw...@gm...> Para: Game Development Algorithms <gda...@li...> 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 GDA...@li... 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 |