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

[Glynn Clements]

Eric G. Miller wrote:

> > > > XDRIVER24 uses XFillPolygon's "Complex" mode, which should handle
> > > > self-intersecting polygons. However, there is a choice of two filling
> > > > rules: EvenOdd and WindingRule. From the XChangeGC manpage:
> > > 
> > > Yes, I played with them, they aren't the problem.
> > > 
> > > Problem is, there's no protocol for drawing polygons with holes.  That
> > > is, the inner "holes" of the polygon should mask out the drawing of the
> > > outer polygon.  I fooled around with d.area to create something of a
> > > work around, but it isn't a very good implementation.  This capability
> > > needs to exist in the drivers so they can implement it however is best
> > > for their "device".  Built vector areas have the holes identified, so
> > > it's at least partially a matter of passing this data to the driver for
> > > appropriate behavior.
> > 
> > So, the issue is that the drivers can only draw "polygons", leaving no
> > simple way to fill arbitrary "paths" like PostScript can?
> 
> 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.

> 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.

> > 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.

-- 
Glynn Clements <glynn.clements at virgin.net>

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