Geometry Boost List: Re: [geometry] Polygon intersection along coincident edges.

Subject: Re: [geometry] Polygon intersection along coincident edges.
From: Paul J. Caritj (caritj_at_[hidden])
Date: 2012-07-11 16:33:35

Hello again everyone,
I have solved my problem and am reporting back for posterity (and perhaps
for the benefit of other desperate Googlers). Bg::intersection is a lost
cause, but I was able to get the results I needed another way: I now
iterate over the points defining my test polygon and check for each's
presence within the target polygon. But this sounds easier than it is
because bg::within does not actually return 'true' for points along the
border of the target polygon. The reference documents at
boost.orgsuggested that this might depend on my search strategy, but
after having
tried winding, franklin, and crossings multiply, it seems that, at least in
my case, the strategy made no difference. Fortunately, there is an easier
way: if you pull the boost source from repository you'll be happy to
discover that there is a new boost::geometry::covered_by(Geometry1 const &
geometry1, Geometry2 const & geometry2) that returns 'true' for border
cases. See:
http://www.boost.org/doc/libs/1_49_0/libs/geometry/doc/html/geometry/reference/algorithms/covered_by/covered_by_2.html

I'm sure most subscribers to this list already knew all this, but hopefully
this will be helpful to some other newcomer someday.

Thanks,
Paul
On Wed, Jul 11, 2012 at 2:14 AM, Paul J. Caritj <caritj_at_[hidden]> wrote:

> Hello everyone,
> I am trying to build a visibility graph of vertices within a collection of
> polygons. This requires (basically) for each vertex in a polygon, to test
> whether it is within another polygon. Unfortunately, the most common case
> is that the vertex is contained within a line segment corresponding to a
> coincident (or partially coincident) edge and, in this case,
> bg::intersection is yielding some (I think) odd results.
>
> Consider two squares (0 0, 0 1, 1 1, 1 0) and (1 0, 1 1, 2 1, 2 0). These
> polygons share the edge (1 1, 1 0). The most reasonable value for
> bg::intersection under these circumstances would seem to be the two
> vertices 1 1 and 1 0 (the most "correct" would, of course, be every point
> along the segment, but this seems pretty clearly unworkable). But
> bg::intersection actually returns only one point under these circumstances:
> 1 1. Could anyone explain why this is and, ideally, suggest a workaround?
>
> Thanks,
> Paul
>