[GRASS5] [bug #242] (grass) R_polygon_abs() seems to ignore islands

[Eric G. Miller]

On Thu, May 03, 2001 at 03:24:59AM +0100, Glynn Clements wrote:`
> > I'm not sure what you mean.  We're only talking the context of filling
> > an area defined by a polygon, but allowing a portion of the filled area
> > to be masked (so it retains whatever was already there).  Like:
> > 
> >   ------
> >   \xxxxx\___________
> >    |xxxxxxxxxxxxxxxx|
> >    \x-------xxxxxxx/
> >     \x\     \xxxxx/
> >      \x\_____\xxx/
> >       \xxxxxxxxx/
> >        ---------
> 
> OK; a lot of people (myself included) wouldn't call that a "polygon". 
> Further, a lot of people automatically read "polygon" as "convex
> polygon", as many graphics APIs are limited to such.

Understand, but this is a real world requirement for *any* GIS that does
vectors.

> > What I did with d.area is connect every inner "hole" with the outer
> > polygon via the shortest pair of colinear line segments I could make
> > from existing vertices.  It's rather a slow process though, especially
> > when the polygons are very large.  Also, I think there are cases where
> > it will produce poor results since it doesn't check if the shortest path
> > between a hole and the outside crosses another hole.
> 
> A correct solution is far from straightforward, as the Mesa[1] folks
> have discovered.
> 
> [1] Mesa is a GPL'd implementation of the OpenGL API.

I knew that ;)

> > > In which case, this isn't likely to get fixed any time soon; even
> > > lifting Mesa's GLU-1.2 tesselator won't help. We would need the
> > > equivalent of the GLU-1.3 tesselator; given that Mesa's current stance
> > > is "use SGI's GLU library", I'm not expecting a GPL'd version to
> > > become available any time soon.
> 
> [NB: I was off by one (or rather, by point-one) with the GLU versions.]
> 
> > No idea about such things...
> 
> A quick run-down:
> 
> OpenGL polygons have to be convex. In order to draw non-convex
> polygons, or polygons with "holes", you have to tessellate the shape
> into a set of convex polygons. To facilitate this, the GLU (GL
> Utilities) library provides a "tessellator" API.
> 
> The API in GLU 1.1 would tessellate non-convex polygons, including
> self-intersecting polygons, but it didn't directly allow for polygons
> containing "holes". It was possible to get around this problem by
> inserting a pair of co-linear edges to connect the hole with the
> perimiter; however, this required the application to be able to figure
> out which vertices to join.
> 
> GLU 1.2 introduced a new tessellator API, which allowed shapes to be
> specified as multiple closed paths, which were then added or
> subtracted using the appropriate fill-rule.
> 
> For a long time, the one feature missing from Mesa was the GLU 1.2
> tessellator. Several people discussed implementing it, but nobody
> managed to come up with the goods (a GLU 1.2 tessellator was included
> in 3.1b3; it was removed in 3.2.1 because it didn't work).
> 
> Now, the Mesa website recommends using SGI's GLU library (free, but
> not GPL) instead of there own, which suggests that they've given up on
> being able to solve this particular problem.
> 
> In short, this "bug" isn't likely to be fixed soon.

I think your being a little too pessimistic here.  The OpenGL scenario
has several issues not present in a 2d representation.  Also, I'm sure
there was considerable concern about the speed of the implementation,
since GL is used in games and such where the image needs to change
rapidly (less of a concern here).

Besides, I *know* this problem is solvable (even if I don't have the
solution yet).  The weak solution would be just to rasterize all of
the fill areas in a seperate buffer and then "overlay" that on the
current display buffer.  I considered that approach for d.area but
haven't yet tried it to see if it's faster for large data sets (I
assumed not).

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

---------------------------------------- 
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo at geog.uni-hannover.de with
subject 'unsubscribe grass5'