# Is this Intersect or Union algorithm associative?

Similar to Is the Intersection Operation Commutative? . Spoiler for that one: Intersection is commutative and associative.

I've created an algorithm (in PostGIS but the theory would work in other languages) that takes an array of polygons as an argument and performs the following: if the polygons overlap, take their intersection. If they do not overlap, union them instead.

``````     i integer;
tmpGeom geometry;
begin
tmpGeom := geoms[1];
FOR i IN 1..array_length(geoms,1) LOOP
IF ST_CROSSES(tmpGeom,geoms[i]) THEN
tmpGeom:= ST_Intersection(tmpGeom,geoms[i]);
ELSE
tmpGeom:= ST_UNION(tmpGeom,geoms[i]);
END IF;
END LOOP;
return tmpGeom;
end;
``````

My question is, does the order of the operation matter? I can test that by randomizing the order for an input of a set of polygons, but I'm looking for some resources to prove it.

This operation is obviously commutative because its description is entirely in terms of commutative operations.

The important, and slightly more interesting, issue concerns whether the operation is associative.

Let us temporarily denote this operation by "+". The question is whether for all polygons P, Q, and R it is the case that

`````` P + (Q+R) = (P+Q) + R.
``````

In the figure, since P and Q overlap, P+Q is their intersection. Since this is disjoint from R, (P+Q)+R is the union of R with P+Q.

Similar reasoning shows that Q+R is their intersection, whence P+(Q+R) is the union of P with Q+R. In particular, any point x that is in P but not in Q will lie in P+(Q+R) but not in (P+Q)+R, providing a counterexample to the desired equality.

Therefore this operation is not generally associative. This severely limits the algebraic manipulations that can be performed and it compels one to use parentheses carefully to avoid ambiguous expressions.

• Got my definitions mixed. Changed the title to fix that. Thank you, you answered what I was looking for. Commented Dec 31, 2014 at 3:15