
Geometry : 
Subject: [ggl] intersection() and mixed geometries
From: Barend Gehrels (barend.gehrels)
Date: 20101010 17:08:37
Hi again,
> Is intersection() able to intersect any two geometries together? For example, can I intersect a multipoint with a multilinestring?
It is not intersecting ANY two geometry types. The most important (and
also during review) were polygon/box, polygon/polygon, multiversions 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
multiversions, 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 mixedgeometry. However it understands the concept of multigeometry of a single type (e.g. multipoint). 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: multipoint set, L: multilinestring set, A: multipolygon 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
Geometry list run by mateusz at loskot.net