Geometry Boost List: [ggl] intersection() and mixed geometries

Subject: [ggl] intersection() and mixed geometries
From: Barend Gehrels (barend.gehrels)
Date: 2010-10-10 17:08:37

  Hi again,

> Is intersection() able to intersect any two geometries together? For example, can I intersect a multi-point with a multi-linestring?

It is not intersecting ANY two geometry types. The most important (and 
also during review) were polygon/box, polygon/polygon, multi-versions of 
these. This all delivers (multi)polygons in the form of output iterators.

Also supported are (multi)linestring/box delivering linestrings, useful 
for painting etc.

Also supported are linestring/linestring and (previous email) now also 
multi-versions, delivering intersection points.

NOT supported are, for example, multi_point/box  or 
multi_point/multi_point (should deliver all points in common), and 
polygon/polygon delivering points, etc. Though some of these are 
trivial, to implement all, we get a bit of a combinatorial problem here, 
resulting in a time problem...

> Boost.Geometry does not understand the concept of mixed-geometry. However it understands the concept of multi-geometry of a single type (e.g. multi-point). I thought that it should be easy then to emulate mixed geometry set operations using simple set algebra:
> 	Let u: union, n: intersection, 0: empty set
> 	Let P: multi-point set, L: multi-linestring set, A: multi-polygon set
>
> Any mixed geometry G can be written
> 	G = P u L u A

OK.

> Given two mixed geometries
> 	G1 = P1 u L1 u A1
> 	G2 = P2 u L2 u A2
> we have for their intersection:
> 	G1 n G2 = G1 n (P2 u L2 u A2)
> 		= (P1 n P2) u
> 		  (L1 n P2) u
> 		  (A1 n P2) u
> 		  (P1 n L2) u
> 		  (L1 n L2) u
> 		  (A1 n L2) u
> 		  (P1 n A2) u
> 		  (L1 n A2) u
> 		  (A1 n A2)

Sounds good.
But... you also have to give the output type. An intersection of two 
polygons can result in a polygon(set), a linestring(set) (common 
borders) and a point(set). If you handle it like described here, within 
our template approach, we get a problem. Or maybe not. But at least it 
is important.

So:

= (P1 n P2) u ->  points
   (L1 n P2) u ->  points
   (A1 n P2) u ->  points
   (P1 n L2) u ->  points
   (L1 n L2) u ->  linestrings or points
   (A1 n L2) u ->  linestrings or points
   (P1 n A2) u ->  points
   (L1 n A2) u ->  linestrings or points
   (A1 n A2)   ->  linestrings or points or areas

So the only output type in common are points, but I think you want (at 
least for A1 n A2) a polygon output type...

When specifying the output type, it will be simpler.
For points: what you had above.
For linestrings:

= (L1 n L2) u ->  linestrings
   (A1 n L2) u ->  linestrings
   (L1 n A2) u ->  linestrings
   (A1 n A2)   ->  linestrings

For polygons:

   (A1 n A2)   ->  areas

> I have attempted to implement this as follows:
> 	// MultiPoint, MultiLinestring, MultiPolygon can be considered std::vector's
> 	MultiPoint P1; MultiLinestring L1; MultiPolygon A1;
> 	// preprocess geometry G1 into P1, L1, A1
> 	MultiPoint P2; MultiLinestring L2; MultiPolygon A2;
> 	// preprocess geometry G2 into P2, L2, A2
> 	MultiPoint P; MultiLinestring L; MultiPolygon A;
> 	bg::intersection(P1, P2, P);
> 	bg::intersection(L1, P2, P);
> 	bg::intersection(A1, P2, P);
> 	bg::intersection(P1, L2, P);
> 	bg::intersection(L1, L2, P);
> 	bg::intersection(A1, L2, L);
> 	bg::intersection(P1, A2, P);
> 	bg::intersection(L1, A2, L);
> 	bg::intersection(A1, A2, A);
>
> However only bg::intersection(A1, A2, A) compiles. Can someone plz explain?

OK, here you have the output specified indeed. So for lines you want to 
have points indeed. That is implemented, L1, L2, P should compile as 
well now. But this gives you only one extra combination. I'll see if 
some extra can be implemented, if you want that. At least the 
intersection of (multi)linestrings within (multi)polygons delivering 
linestrings is intersecting for many, and the basic pieces are there.

Regards, Barend