[geos-devel] Polygon multiple intersection algorithm?

Martin Davis mbdavis at VividSolutions.com
Thu Jul 13 12:44:18 EDT 2006


Fernando,

The name of the algorithm you are looking for is polygon overlay.   This
is a standard GIS algorithm.  Unfortunately it's not in JTS/GEOS right
now - but soon hopefully....

This is also sometimes referred to as (polygonal) coverage overlay.  You
should find quite a few references to these on Google - but I haven't
had any luck in finding code.  Let me know if you do!

Martin Davis, Senior Technical Architect
Vivid Solutions Inc.      www.vividsolutions.com
Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046


> -----Original Message-----
> From: geos-devel-bounces at geos.refractions.net 
> [mailto:geos-devel-bounces at geos.refractions.net] On Behalf Of 
> Ferdinando Villa
> Sent: July 13, 2006 9:11 AM
> To: geos-devel at geos.refractions.net
> Subject: [geos-devel] Polygon multiple intersection algorithm?
> 
> 
> Good folks,
> 
> apologies for tapping into your knowledge without a real GEOS 
> question, but I can't even seem to express this with enough 
> brevity for a Google search. There must be a name for an 
> algorithm that creates the maximum set of non-overlapping 
> shapes based on the intersection of a source shape set. For 
> example, the intersection of squares A and B is a smaller 
> square C. The intersection set is A-C, C, and B-C. I need to 
> do the same as efficiently as possible with an arbitrary 
> number of shapes.
> 
> Does this process have a name, and/or a smarter algorithm 
> than the exponential ones I can think of? It sounds so 
> generally useful that I can't think it doesn't, but I found 
> no clue. Pardon my ignorance....
> 
> Cheers,
> ferdinando 
> 
> --
> Ferdinando Villa, Associate Research Professor, 
> Ecoinformatics Ecoinformatics Collaboratory, Gund Inst. for 
> Ecol. Economics and Dept. of Botany
> University of Vermont           http://ecoinformatics.uvm.edu
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net 
> http://geos.refractions.net/mailman/listinfo/geos-devel
> 



More information about the geos-devel mailing list