CGAL users discussion list

["Ch'Gans" <>]

Hi there,

I am using an R-Tree (Boost.Geometry) to do spatial queries, my
geomtric items range from small rectangle to long "thick" lines and
complex polygon with holes.

Some of my polygons have a bounding box that nearly covers the whole
set of items my rtree have to deal with, and I need to efficiently do
collision detection b/w the small items and the big polygons. Since
the rtree works with bounding box, I gain nothing when inserting such
"huge" items (their bounding box collides with everyone else's
bounding box).
See attached picture showing a layer of 254 polygons with holes for a
total of ca 70000 points: green are polygon outer boundaries, yellow
are inner boundaries, blue are outer boundary bounding box and magenta
inner boundary bounding box.

I would first like to split these big polygons into a set of smaller
polygons (or rectangles), so that i can take advantage of my rtree. I
don't care about how optimal the partitioning is, my definition of
optimum is: generate quickly sub-polygons that have a small-enough
bounding box.

I looked at CGAL polygon partitioning algos, and the optimal convex
partition looks sexy, but with complexity such as O(n^4) I think it is
no-go for me. The approximate convex partitioning has better
performance, but it seems that in my case it will produce sub-polygons
which will potentially have "big" bounding boxes.

Then there's the triangulation, but given the (very) detailed
"coast-line" of my polygon, it might not be efficient and will
certainly produce a massive amount of triangles. Maybe if i combine
this with multi-polyline simplification it might work... But this
sounds like requiring lot of CPU ...

A simple algo I had in mind is spliting a polygon according to a
coarse grid: lay out a polygon on a grid, then insert a grid cell in
the rtree, iff the cells overlaps the polygon. I thing it's a classic
approach in graphics toolkit (Qt has QRegion for this if i'm not
wrong). this could potentially be refined using a dichotomy
approach... Maybe i could use a CGAL arrangement and monitor face
splitting as i insert horizontal/vertical grid lines...

Anyhow, I thought i would send a word to this mailing list, and see is
someone has an opinion about these sort of problem, maybe i've missed
an awesome CGAL super-weapon, or maybe i'm trying to be too
clever/complicated.

Thanks,
Chris

Attachment: Screenshot_20170331_023242.png
Description: PNG image