2

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.

2

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.

Figure

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.

| improve this answer | |
  • Got my definitions mixed. Changed the title to fix that. Thank you, you answered what I was looking for. – raphael Dec 31 '14 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.