Boost logo

Geometry :

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:

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

Geometry list run by mateusz at