Geometry Boost List: [ggl] intersection of two vectors of polygons

Subject: [ggl] intersection of two vectors of polygons
From: Vishnu (vrang3)
Date: 2011-04-28 13:17:19

I'm wondering whether anyone has recommendations for calculating the
intersection between two vectors of polygons.

Currently, I use boost::geometry::intersection(). Before calling this
function, I convert the 2 vectors of polygons into 2 valid multi_polygons.
The problem with this approach is that instead of getting 9 discrete
polygons in the intersection result, I get a single polygon that is the
union of the 9 polygons.

The reason it's important to get 9 discrete polygons in the intersection is
as follows. Say that 4 adjacent squares in the first collection are 4 farms
labeled by ownership and the 4 adjacent squares in the 2nd set are labeled
according to mineral rights. Let's say one wants the polygons corresponding
to farm with owner "1" and mineral rights "3". 

This is what I have right now. Each vector of polygons in the inputs has 4
squares. The second vector of 4 squares is a copy of the first set, offset
slightly in the +x and +y directions. The intersection should have discrete
9 squares.

The first collection of polygons is:

POLYGON((0 0.5,0 1,0.5 1,0.5 0.5,0 0.5))POLYGON((0.5 0.5,0.5 1,1 1,1 0.5,0.5
0.5))POLYGON((0 0,0 0.5,0.5 0.5,0.5 0,0 0))POLYGON((0.5 0,0.5 0.5,1 0.5,1
0,0.5 0))

and the second collection of polygons is

POLYGON((0.25 0.75,0.25 1.25,0.75 1.25,0.75 0.75,0.25 0.75))POLYGON((0.75
0.75,0.75 1.25,1.25 1.25,1.25 0.75,0.75 0.75))POLYGON((0.25 0.25,0.25
0.75,0.75 0.75,0.75 0.25,0.25 0.25))POLYGON((0.75 0.25,0.75 0.75,1.25
0.75,1.25 0.25,0.75 0.25))

To convert each vector of polygons into a valid multi_polygon, I move down a
vector and take the union of the current polygon with the union of all
preceding polygons. I can post the code snippet if necessary.

The problem, as I see it is that the multi_polygons are too restrictive in
that they don't allow a collection of 4 adjacent squares such as a 2x2 cell
on graph paper to be treated as discrete polygons.

The alternative I am thinking of is to intersect each polygon in the first
vector with each polygon in the second vector and then put the resulting
polygons into a 3rd vector. This would be an O(n^2) operation, hence bad for
large vectors of inputs.

Does anyone see another way? I think that having a way to do intersections
on vectors of polygons and not just multi_polygons would be a valuable
feature in boost-geometry. 

Vishnu

--
View this message in context: http://boost-geometry.203548.n3.nabble.com/intersection-of-two-vectors-of-polygons-tp2875513p2875513.html
Sent from the Boost Geometry mailing list archive at Nabble.com.