You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

S  M  T  W  T  F  S 


1

2

3

4

5
(9) 
6
(1) 
7

8

9
(8) 
10
(1) 
11

12

13

14

15

16
(4) 
17

18
(6) 
19
(1) 
20

21

22

23

24
(10) 
25
(4) 
26
(3) 
27
(1) 
28

29

30





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: 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: 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: Sam Martin <sam.martin@ge...>  20090626 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 nonoverlapping 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. Nonconvex 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 nonconvex hulls: http://www.spatialanalysisonline.com/output/html/Nonconvexhulls.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" <gdalgorithmslist@...> 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 <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  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist __________________________________________________________________ The new Internet Explorer® 8  Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist  Revenge is the most pointless and damaging of human desires. 
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...>  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: 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: Jon Watte <jwatte@gm...>  20090625 00:59:15

<!DOCTYPE html PUBLIC "//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta content="text/html;charset=ISO88591" httpequiv="ContentType"> </head> <body bgcolor="#ffffff" text="#000000"> An alpha shape is not guaranteed to be a closed nonoverlapping 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.<br> <br> Nonconvex 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).<br> <br> 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..<br> <br> Sincerely,<br> <br> jw<br> <br> <br> metanet software wrote: <blockquote cite="mid:837110.54226.qm@..." type="cite"> <pre wrap="">hi, you might also want to check out alpha shapes and nonconvex hulls: <a class="moztxtlinkfreetext" href="http://www.spatialanalysisonline.com/output/html/Nonconvexhulls.html">http://www.spatialanalysisonline.com/output/html/Nonconvexhulls.html</a>; <a class="moztxtlinkfreetext" href="http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf">http://www.cs.wustl.edu/~pless/546/lectures/lecture22.pdf</a>; <a class="moztxtlinkfreetext" href="http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html">http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html</a>; raigan  On Wed, 6/24/09, Jose Marin <a class="moztxtlinkrfc2396E" href="mailto:jose_marin2@..."><jose_marin2@...></a> wrote: </pre> <blockquote type="cite"> <pre wrap="">From: Jose Marin <a class="moztxtlinkrfc2396E" href="mailto:jose_marin2@..."><jose_marin2@...></a> Subject: [Algorithms] Res: Res: Polygon from point cloud and other from triangle list? To: "Game Development Algorithms" <a class="moztxtlinkrfc2396E" href="mailto:gdalgorithmslist@..."><gdalgorithmslist@...></a> 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 <a class="moztxtlinkrfc2396E" href="mailto:jwatte@..."><jwatte@...></a> Para: Game Development Algorithms <a class="moztxtlinkrfc2396E" href="mailto:gdalgorithmslist@..."><gdalgorithmslist@...></a> 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: </pre> <blockquote type="cite"> <pre wrap="">I need to find the outline polygon (may be nonconvex, </pre> </blockquote> <pre wrap="">and will be on most of the times) defined by the resulting shape. </pre> <blockquote type="cite"> <pre wrap=""> </pre> </blockquote> <pre wrap="">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 <a class="moztxtlinkabbreviated" href="mailto:GDAlgorithmslist@...">GDAlgorithmslist@...</a> <a class="moztxtlinkfreetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist">https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist</a>; Archives: <a class="moztxtlinkfreetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist</a>; Veja quais são os assuntos do momento no Yahoo! +Buscados <a class="moztxtlinkfreetext" href="http://br.maisbuscados.yahoo.com">http://br.maisbuscados.yahoo.com</a>;  _______________________________________________ GDAlgorithmslist mailing list <a class="moztxtlinkabbreviated" href="mailto:GDAlgorithmslist@...">GDAlgorithmslist@...</a> <a class="moztxtlinkfreetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist">https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist</a>; Archives: <a class="moztxtlinkfreetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist</a>; </pre> </blockquote> <pre wrap=""><!> __________________________________________________________________ The new Internet Explorer® 8  Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at <a class="moztxtlinkfreetext" href="http://downloads.yahoo.com/ca/internetexplorer/">http://downloads.yahoo.com/ca/internetexplorer/</a>;  _______________________________________________ GDAlgorithmslist mailing list <a class="moztxtlinkabbreviated" href="mailto:GDAlgorithmslist@...">GDAlgorithmslist@...</a> <a class="moztxtlinkfreetext" href="https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist">https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist</a>; Archives: <a class="moztxtlinkfreetext" href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist</a>; </pre> </blockquote> <br> <br> <div class="mozsignature"> <br> <pre> Revenge is the most pointless and damaging of human desires. </pre> </div> </body> </html> 
From: metanet software <metanet_gda4@ya...>  20090624 23:17:23

hi, you might also want to check out alpha shapes and nonconvex hulls: http://www.spatialanalysisonline.com/output/html/Nonconvexhulls.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" <gdalgorithmslist@...> > 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 <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 > >  > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > __________________________________________________________________ The new Internet Explorer® 8  Faster, safer, easier. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/ 
From: Rachel Blum <rachel@ra...>  20090624 21:37:10

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 
From: Rachel Blum <rachel@ra...>  20090624 21:34:16

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 
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 
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: James Robertson <jamesr@fu...>  20090624 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 nonconvex. > > 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 > >  > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > 
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: 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: Richard Fabian <raspo1@gm...>  20090624 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 nonpicked 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 <jose_marin2@...>: > > 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 nonconvex. > > 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 > >  > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >  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...>  20090624 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 nonconvex. 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 
From: Paul_F<irth@sc...>  20090619 08:57:52

BEGIN PGP SIGNED MESSAGE Hash: SHA256 > In this case, the tie breaker could be that end points are sorted before > start points. That goes into the sorting function, not the index testing > function. > Although if you support resting/touching contact, you probably want the > tie breaker to be end points go after beginning points... Someone mailed me offline and said a way to get around this problem is to artificially bias end points so that min points have their lowest bit cleared from the value and max bits have their lowest bit set, that way a max can never have the same value as a min. Of course this could lead to false positives, but since its a broadphase algorithm this isn't the end of the world. Additionally, if we've entered the realm of false positives you might as well quantise the values to unsigned ints/shorts and then you can compare integers instead of floats... Not sure if that was the same as what you are suggesting (the first part)? Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this email BEGIN PGP SIGNATURE Version: PGP Universal 2.9.1 (Build 287) Charset: USASCII wsBVAwUBSjtMznajGqjtoMHxAQgnOQf/aEsMSMDcFOlDCp9BjJV4W8INk45Mlnuw nGqcK4dMxkfZ/B88pv7S1KmXCuQmpwcnyovKKvsF/kvOsePmyTSKqCrnNAkAkGAx op6SdI7KbBksiqVg6at7ZggQomk3NtNasWpFT/ZDcggbQdYiy6IOt5b2Fg/0p2L9 E8+D5KRX2C9JHX8lxUn3tAxeWgCnEwkbQzS7iE1KF3ePDTeadvq5qO5rRn2Yua41 Zeu+WWxfBN/sK35vxbyyXenbgupiGqjr6YhKaMXSysZO4QX9IGGVBM27C2biOzlJ 8jaggnplGoPXs98SJUbMAXLkgQWJznm8Q/bRmTXdqRl+O3EOZ+VXJw== =8PdK END PGP SIGNATURE 
From: Jon Watte <jwatte@gm...>  20090618 18:20:51

Paul_Firth@... wrote: > AB > CD > EF > > Indices: > > A B C D E F > 0 2 1 4 3 5 > > So if you were to check C to see if it were before B by index you'd get a > positive, but checking E for before B gives a negative even though both > B,C and E have the same actual value. > In this case, the tie breaker could be that end points are sorted before start points. That goes into the sorting function, not the index testing function. Although if you support resting/touching contact, you probably want the tie breaker to be end points go after beginning points... Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Paul_F<irth@sc...>  20090618 17:55:53

BEGIN PGP SIGNED MESSAGE Hash: SHA256 > If the problem is that the same value maps to multiple indices, then I > don't see why  you get a stable sort by checking index (as long as the > index relates to the value). The values are sorted correctly, the trouble is when i come to detect whether the is a 1d overlap of bounds, i can't check the indices instead of the values because one value maps to many indices in the case of exactly touching objects: i.e. AB CD EF Indices: A B C D E F 0 2 1 4 3 5 So if you were to check C to see if it were before B by index you'd get a positive, but checking E for before B gives a negative even though both B,C and E have the same actual value. Hope i haven't messed that example up :) Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this email BEGIN PGP SIGNATURE Version: PGP Universal 2.9.1 (Build 287) Charset: USASCII wsBVAwUBSjp/mHajGqjtoMHxAQhwfQgAkuRIr44cCNt86GsEVgfqceS2v22QPmHy TlZZSHp5LSdjKGQCbj5YznMzhZdbmNKFj9Xj+DCzG9KQHU1ShBnh5t0xljDiQ9EV aNmMjRo2J7JpqXw+p01rwk9NLuzcNbjxYYDMy8s8ddYDc9Av0eD+IFzSfZIb6Upb mX6PV7BGlGtmeKvLSR46YKpgEF53aHIkY1WF3HF9yprJzqdVlbZzHRONMwO1h47s VvGPFBYdqRBcwQ12WHIOCCLgV6ec7nW5fKbXzOZ4ejh2KMlMEG3o5qu8bVR3LyZY ufN3TlkfU8s4L5JALwH4osJKhvjTGe15bp4JS0MSFm+JkaJXhZqB1A== =wi0P END PGP SIGNATURE 
From: Jon Watte <jwatte@gm...>  20090618 17:06:14

Paul_Firth@... wrote: > BEGIN PGP SIGNED MESSAGE > Hash: SHA256 > > >> In a stable sort, you generally have a tie breaker, such as the "this" >> pointer of the value in question, in the case of a tie. >> > > Hmmm, wouldn't that mean i'd need to do the expensive value vs value test > anyway first? > If the problem is that the same value maps to multiple indices, then I don't see why  you get a stable sort by checking index (as long as the index relates to the value). If the problem is that the same index maps to multiple values, then yes, you need to check values. If the problem is that you have nonunique values, which map to nonunique indices, but you want an ordering between separate values with the same value/index, then using a tiebreaker is one solution. Sincerely, jw 
From: Paul_F<irth@sc...>  20090618 16:27:47

BEGIN PGP SIGNED MESSAGE Hash: SHA256 > In a stable sort, you generally have a tie breaker, such as the "this" > pointer of the value in question, in the case of a tie. Hmmm, wouldn't that mean i'd need to do the expensive value vs value test anyway first? ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this email BEGIN PGP SIGNATURE Version: PGP Universal 2.9.1 (Build 287) Charset: USASCII wsBVAwUBSjpq+HajGqjtoMHxAQjxSwf9FZYsHOhF5iq6fAYKT+3HSwpwlVAiahQG WlA5GZvrwS8PkmDUjOqwxMCZdT59T7OgGw7RXvmbZiukoLuFI7gcILT+UKDmCgDB nx+KKSVg67g+EEijKiQnJ1yzX7+hnFdLJAio9IUzAnJGXDbNBzS0ILr5Lf7YoqVK 6yO0jCS4fhef4DKz1I7eQ+RqKhCogIQn5LbICji3Y6yRz61t5zJgyb+uFvuuGzOD 8k8x45n8M8vkjNcBzl50fDqHU4OYl6jkpdwselOp/RUCI7qNz4k5pmnuXlpVSdjC 0dyVDrjrkNjlfqLbGABSmm5SM5edy89zXiaoJPBEYCZ90mW97qx0rQ== =5OzP END PGP SIGNATURE 
From: Jon Watte <jwatte@gm...>  20090618 15:29:48

Paul_Firth@... wrote: > So do i need to compare bound values in all cases? Is there another way > around this? > In a stable sort, you generally have a tie breaker, such as the "this" pointer of the value in question, in the case of a tie. Sincerely, jw 
From: Paul_F<irth@sc...>  20090618 14:41:20

BEGIN PGP SIGNED MESSAGE Hash: SHA256 Hi guys, I'm running into a few issues with my sort and sweep broadphase algorithm. It comes down to bounds in an axis with identical values. Most of the stuff i've read about using an array based method for sorting your axis values say a good optimisation (for the overlap test) is to compare bound indices instead of bound values. But in the case where there are identical bound values in the axis, this breaks down since some of them would be reported as overlapping and some would not depending on where they were in the array. Unfortunately this case comes up a lot in our game. So do i need to compare bound values in all cases? Is there another way around this? Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this email BEGIN PGP SIGNATURE Version: PGP Universal 2.9.1 (Build 287) Charset: USASCII wsBVAwUBSjpRynajGqjtoMHxAQiZ2gf/ZcIToOT/o1LNU4RKP70AZtIbEek2lObO g1M7VbLNmgP9vRZUIRcr/4kNi9W/o2IIPguTfNYtOiBWZ5N8cVmgwOzF25DUR2Kq dhF7zPMK5mAZj+e3PBFEJaBwXZFockqBt44ekTV+z4jA3AZfjgvRr+By+oSXc9QU ym566w1L3pUIfwZaj3b2X7IKVG6GeFitQ2s/21QlFUUSBlw9W0N7Alsl8SKhgqrP rHfqSjNKtxjR6at3TApMsS73PMXPZjJJxth7uClwnEy53tEbH3TADVjuFU+EYYIZ qI9dyiqAklFRjir3lI8uwUqJzthzDb5qQZrgNqegORQGB2Z/75Yosw== =xzS9 END PGP SIGNATURE 