Boost logo

Geometry :

Subject: [geometry] Polygon intersection along coincident edges.
From: Paul J. Caritj (caritj_at_[hidden])
Date: 2012-07-11 02:14:30

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?


Geometry list run by mateusz at