Boost logo

Geometry :

Subject: [geometry] How to divide up a box with a sequence of points
From: John Swensen (jpswensen_at_[hidden])
Date: 2014-02-28 20:09:17

I am once again trying to use Boost Geometry for and mobile app and have
run into a snag. I am trying to take a box (or polygon of some arbitrary
shape), shoot a ray around, then divide up the box/polygon using the
sequence of points. A quick example is shown in the following image.
I basically let the ray keep traveling and bouncing off edges until it
intersects itself. I have this part working great.

I had first prototyped this in Matlab using the polybool function to then
take the intersection and difference of the sequence of points with the
original box/polygon. This worked great and divided the box/polygon up into
the 6 regions shown in the image ({1,2,3,4,6} were generated from the
difference computation and {5} was generated from the intersection
computation). So then I switched over to trying to doing the same thing
with the intersection and difference functionality of Boost Geometry, but
keep getting exceptions about self-intersections.

So, my question is whether
1) there is a better way to do this with an algorithm that already exists
in Boost Geometry?
2) if not, is there a paper or website you know of that describes this kind
of algorithm that I can implement myself using Boost Geometry as the
geometry toolkit?

Geometry list run by mateusz at