Re: [Jts-topo-suite-user] Break overlapping polygons into fragments?
Brought to you by:
dr_jts
Menu
▾
▴
Re: [Jts-topo-suite-user] Break overlapping polygons into fragments?
|
From: Martin D. <mtn...@te...> - 2010-07-22 20:56:43
|
Hi, Nick! Good to see you're still lurking... You're right, the suggested approach is not all that efficient. (This is often the case when a series of "larger" operations is chained together to produce a result, since there tends to be a lot of redundant processing and structured involved.) Hopefully the algorithm may be of use in appropriate situations (e.g. small inputs, not time-critical) One of the aspects of computational geometry that is both frustrating and fascinating is how "brittle" the algorithms are, in the sense that small changes in use case constraints (such as requiring convex polygons as output) can either force or allow completely different approaches to a given problem. Sometimes this allows developing much more efficient algorithms; other times it's exactly the opposite! Martin Nick Wiggill wrote: > Hi > > This is something I'm busy working on as we speak, outside of JTS > though. I need to perform operations like these in perhaps less than > 5ms per overlap operation, and I need the resultant fragment polygons > to be convex, so I unfortunately couldn't use JTS... I did try it but > the union stuff is quite processor-heavy. > > Martin's answer should work just fine for you using JTS to solve the > problem, but if you have any other questions on the general approach, > I'll see if I can help out or offer some code. > > PS. Martin -- hope you're well, long time, seems my game project has > headed off in another direction so I've put my JTS usage on hold for a > while. But I haven't forgotten this great lib and am still watching > the mailing list! > > Nick > > On 22 July 2010 20:18, Martin Davis <mtn...@te... > <mailto:mtn...@te...>> wrote: > > This is what is generally known as Polygon Overlay. There's nothing in > JTS right now that does this explicitly, but you can approximate it by > the following technique: > > - extract the linework > - noding it using UnaryUnion or more robustly GeometryNoder > - polygonize the noded linework > - parentage of the resultant polygons can be recovered via > point-in-polygon tests > > See this thread for some further information: > > http://sourceforge.net/mailarchive/forum.php?thread_name=80529b1a1003160818j1d880262p822880eb73960b4a%40mail.gmail.com&forum_name=jts-topo-suite-user > <http://sourceforge.net/mailarchive/forum.php?thread_name=80529b1a1003160818j1d880262p822880eb73960b4a%40mail.gmail.com&forum_name=jts-topo-suite-user> > > At some point I intend to summarize all this in the JTS FAQ... > > Martin > > Jeff Adams wrote: > > How do you take a collection of polygons that may overlap, and turn > > them into polygons that do not overlap (I.E. each overlapping > area is > > now a distinct polygon)? > > > > I.E. if you have two rectangles (0 0, 2 0, 2 1, 0 1, 0 0) and (1 > 0, 3 > > 0, 3 1, 1 1, 1 0) as input, you'd get three squares (0 0, 1 0, 1 > 1, 0 > > 1, 0 0), (1 0, 2 0, 2 1, 1 1, 1 0), and (2 0, 3 0, 3 1, 2 1, 2 0) as > > output. > > > > Thanks, > > Jeff > > > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Sprint > What will you do first with EVO, the first 4G phone? > Visit sprint.com/first <http://sprint.com/first> -- > http://p.sf.net/sfu/sprint-com-first > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > <mailto:Jts...@li...> > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > > -- > Nick Wiggill > www.handcraftedgames.net <http://www.handcraftedgames.net> > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Sprint > What will you do first with EVO, the first 4G phone? > Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first > ------------------------------------------------------------------------ > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > |