Thread: [Algorithms] Simple algorithm for regular polygon union
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Jose M. <jos...@ya...> - 2009-05-05 16:30:48
|
Hi,
I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons.
Do you know any?
Thank you.
Jose
Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com
|
|
From: Jeremy <jsw...@gm...> - 2009-05-05 17:48:18
|
Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote: > > Hi, > > I have found some libraries in the net to perform polygon operations, but I > need a very simple one: union of closed convex polygons. > > Do you know any? > > Thank you. > > Jose > > > Veja quais são os assuntos do momento no Yahoo! +Buscados > http://br.maisbuscados.yahoo.com > > > ------------------------------------------------------------------------------ > The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your > production scanning environment may not be a perfect world - but thanks to > Kodak, there's a perfect scanner to get the job done! With the NEW KODAK > i700 > Series Scanner you'll get full speed at 300 dpi even with all image > processing features enabled. http://p.sf.net/sfu/kodak-com > _______________________________________________ > 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 > |
|
From: Jose M. <jos...@ya...> - 2009-05-05 18:02:21
|
Yes, but looks like that lib have some restrictions for commercial use. ________________________________ De: Jeremy <jsw...@gm...> Para: Game Development Algorithms <gda...@li...> Enviadas: Terça-feira, 5 de Maio de 2009 14:48:13 Assunto: Re: [Algorithms] Simple algorithm for regular polygon union Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote: Hi, I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons. Do you know any? Thank you. Jose Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ------------------------------------------------------------------------------ The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your production scanning environment may not be a perfect world - but thanks to Kodak, there's a perfect scanner to get the job done! With the NEW KODAK i700 Series Scanner you'll get full speed at 300 dpi even with all image processing features enabled. http://p.sf.net/sfu/kodak-com _______________________________________________ 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: Eric H. <eri...@gm...> - 2009-05-05 18:03:15
|
[Trying again, since I moved my email address and my reply got filtered out.] I don't know of a "stripped down" union library for this particular problem. It sounds like you've already found some of these, but the best page I know that lists a few 2D polygon union packages is the one linked from Jeremy's: http://www.cs.man.ac.uk/~toby/alan/software/links.html. Eberly's had the least restrictive licensing, though wasn't particularly efficient (but gave solid results - he uses exact integer arithmetic). I've used this package in shipping software, it works well. I found most of the other packages listed had "For non-commercial use only" or other limitations, which was annoying. The Eberly link from the GPC page is broken, and you'll have to dig on Eberly's site a bit for the code: Classes here, and paper on his algorithm at the bottom: http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html Actual code here: http://www.geometrictools.com/SampleFoundation/Boolean2D/Boolean2D.html Eric On Tue, May 5, 2009 at 1:48 PM, Jeremy <jsw...@gm...> wrote: > Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html > > > > On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...>wrote: > >> >> Hi, >> >> I have found some libraries in the net to perform polygon operations, but >> I need a very simple one: union of closed convex polygons. >> > |
|
From: Jose M. <jos...@ya...> - 2009-05-05 18:24:02
|
Thank you very much, Eric! Very usefull tips... ________________________________ De: Eric Haines <eri...@gm...> Para: Game Development Algorithms <gda...@li...> Enviadas: Terça-feira, 5 de Maio de 2009 15:03:04 Assunto: Re: [Algorithms] Simple algorithm for regular polygon union [Trying again, since I moved my email address and my reply got filtered out.] I don't know of a "stripped down" union library for this particular problem. It sounds like you've already found some of these, but the best page I know that lists a few 2D polygon union packages is the one linked from Jeremy's: http://www.cs.man.ac.uk/~toby/alan/software/links.html. Eberly's had the least restrictive licensing, though wasn't particularly efficient (but gave solid results - he uses exact integer arithmetic). I've used this package in shipping software, it works well. I found most of the other packages listed had "For non-commercial use only" or other limitations, which was annoying. The Eberly link from the GPC page is broken, and you'll have to dig on Eberly's site a bit for the code: Classes here, and paper on his algorithm at the bottom: http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html Actual code here: http://www.geometrictools.com/SampleFoundation/Boolean2D/Boolean2D.html Eric On Tue, May 5, 2009 at 1:48 PM, Jeremy <jsw...@gm...> wrote: Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote: Hi, I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons. Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com |
|
From: Graham R. ARA/S. <gr...@ar...> - 2009-05-05 18:24:02
|
Note that if you union two convex polygons, the result is not necessarily convex. And, would result in two loops if the source polygons don't intersect each other or if one isn't contained in the other. You probably realize this, but I thought I'd point it out. David Eberly's open source WildMagic engine has a sample application for performing Boolean set operations on polygons...not necessarily convex, but of course does handle those. Here is a link: http://www.geometrictools.com/SampleFoundation/Polysolid2D/Polysolid2D.html You can download a fairly minimal set of code (you don't need the entire engine...only a few files) and it does work as advertised. That is based on BSP trees, which a lot of people like but is not my personal preferred approach. My own preferred approach to doing Polygon Booleans (and again, not restricted to convex), and the one I have used in my code, is based on a paper by Greiner and Hormann, "Efficient Clipping of Arbitrary Polygons," ACM Transactions on Graphics, Vol. 17, No. 2, April 1998, pp 71-83. This is a very straightforward paper. I am sure there is something that is tuned for convex polygons, but I can't point you to anything that specific. Graham -----Original Message----- From: Jose Marin [mailto:jos...@ya...] Sent: Tuesday, May 05, 2009 12:31 PM To: gda...@li... Subject: [Algorithms] Simple algorithm for regular polygon union Hi, I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons. Do you know any? Thank you. Jose Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ------------------------------------------------------------------------------ The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your production scanning environment may not be a perfect world - but thanks to Kodak, there's a perfect scanner to get the job done! With the NEW KODAK i700 Series Scanner you'll get full speed at 300 dpi even with all image processing features enabled. http://p.sf.net/sfu/kodak-com _______________________________________________ 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 |
|
From: Gregory J. <gj...@da...> - 2009-05-05 18:28:46
|
Hi Jose, You don't mention any of the ones you have found and rejected, so forgive me if you've looked at GTS already: http://gts.sourceforge.net/ It's LGPL, which is consistent with commercial usage (assuming you don't mean "commercial on a console"). Greg -----Original Message----- From: Jose Marin [mailto:jos...@ya...] Sent: Tuesday, May 05, 2009 9:31 AM To: gda...@li... Subject: [Algorithms] Simple algorithm for regular polygon union Hi, I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons. Do you know any? Thank you. Jose Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com ---------------------------------------------------------------------------- -- The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your production scanning environment may not be a perfect world - but thanks to Kodak, there's a perfect scanner to get the job done! With the NEW KODAK i700 Series Scanner you'll get full speed at 300 dpi even with all image processing features enabled. http://p.sf.net/sfu/kodak-com _______________________________________________ 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 |
Thanks for helping keep SourceForge clean.
X