Geometry Boost List: [ggl] map overlay of planar subdivisions

Subject: [ggl] map overlay of planar subdivisions
From: Barend Gehrels (barend)
Date: 2011-07-19 14:52:19

Hi Rob,

> I would like to compute the overlay of two planar subdivisions (polygonal
> meshes) such that the result is the maximal connected subset of the polygon
> face intersections.  Ideally it would also provide the reference information
> from the new polygons to the containing faces from the originating
> subdivisions.
>
> This looks like similar functionality to Boost.Geometry's union_: return all
> constituent sub-polygons rather than just the outlined union.  Could you
> tell me if detail::overlay as called by union_ is intended for public use
> since I can't find documentation for it, and provide some guidance on how to
> achieve the above?

Basically all Boost.Geometry functions work (as OGC does) per object, or 
per pair of objects.

You can see your planar subdivision as a multi-polygon (one object), but 
then you run into a problem: it is not valid. Because multi-polygons may 
only touch tangentially, not side-by-side. Besides this, you will loose 
the reference information.

So the way to go is to match all polygons of set A with all polygons of 
set B. You can do that quadratically, but better is use the partition 
algorithm, with which you can speed the process up. If you do it polygon 
per polygon, you can keep track of the information yourself.

Note that this is quite similar to the question of Vishnu asked before 
on this list, see this thread:
<http://boost-geometry.203548.n3.nabble.com/intersection-of-two-vectors-of-polygons-td2875513.html>

including samples (search for codepad).

detail:: functions are not intended for public usage, they are not (yet) 
documented and (more important) the interface might change.

Regards, Barend