Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net