[GRASS5] Nested vector islands, and incorrect left/right poly id's for island edges...

[Eric G. Miller]

On Tue, 22 Jan 2002 20:19:42 +0000, David D Gray <ddgray at armadce.demon.co.uk> wrote:

> Eric G. Miller wrote:
> 
> > It appears that GRASS doesn't write correct information for
> > left/right adjaceny for edges of areas nested more than
> > one polygon deep.  That is: If polygon 1, contains polygon
> > 2, and polygon 2 contains polygon 3, the lines comprising
> > polygon 3 will have polygon 1 written as the adjacent area
> > for either left or right, when I would think it should be
> > polygon 2.
> > 
> 
> 
> Yes I would have thought so.
> 
> 
> > I was trying to work up a way to do the following:
> > 
> >   Given an area with N islands/holes.  Create a set of
> >   interior boundaries such that islands/holes that
> >   share one or more edges are combined into a single
> >   boundary (with interior edges being dropped).
> > 
> 
> 
> I don't quite understand how islands can share edges. I thought in the 
> earlier posting you meant that an edge of an island can be the same as 
> that of an (outer) ring. If two 'islands' share a boundary, then they 
> are actually the constituent cells of an island, not the island itself. 
> If the build routine is creating islands within a polygon that abut, 
> then that is a bug.

I'm perhaps not being clear.  Area A, contains areas B, C and D.
Areas B and C share a common edge.  Therefore, the interior boundaries
of A are formed from the exterior boundaries of D and the minimal
boundary enclosing B and C.  However, when I iterate through the
islands in GRASS (Vect_get_isles_points), each boundary of each
interior area (B, C, and D) is returned, and therefore I get
duplicate linework for the common boundary of B and C.

At least, that seems to be what is going on.  So, now I'm looking at
eliminating those common edges, but apparently I can't rely on the
line -> area adjacency information, so I'll have to use a "seen list"
instead.  But at this point, I think I'm wasting my time on the
simplified, scanline, polygon simplification algorithm I've been using,
and I might as well just try implementing a generic scan line rasterizer.
The overhead of the "simplified" solution seems to be getting to high,
where it won't yield much (if any) performance benefit.

-- 
Eric G. Miller <egm2 at jps.net>