# [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
>

```