Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-26 16:26:07

Mika Heiskanen wrote:
> Simonson, Lucanus J wrote:
> > I believe design decisions should lead to a library that is
> > convenient to use rather than convenient to implement.
>
> I agree with Luke on this one. I have written a contouring
> algorithm which produces either polygons for filling or polylines
> for stroking. The filling will work just fine if I use the even-odd
> filling rule regardless of the orientation of any individual subpolygon.
> However, I'd hate to have to produce a certain winding rule for the
> exterior and the holes in order to use the same data for more
> complicated GIS calculations such as logical operations and buffering.
> IMHO it should be just as easy as choosing to use the even-odd filling
> rule instead of the winding rule.

We currently follow the "rules" of the OGC, stating:
> The exterior boundary LinearRing defines the “top” of the surface 
> which is the side of the surface from which the
> exterior boundary appears to traverse the boundary in a counter 
> clockwise direction. The interior LinearRings will
> have the opposite orientation, and appear as clockwise when viewed 
> from the “top”,
> The assertions for Polygons (the rules that define valid Polygons) are 
> as follows:
> a) Polygons are topologically closed;
> b) The boundary of a Polygon consists of a set of LinearRings that 
> make up its exterior and interior boundaries;
(source: http://www.opengeospatial.org/standards/sfa#downloads)

I'm talking about OGC more on this list. They have defined a 
well-defined interface which is followed by the majority of the GIS 
world and which is based on a mathematical/topological foundation. So we 
better follow their guidelines than take decisions about every 
possibility ourselves. Most if not all Open Source implementations are 
following these rules.

Of course we can concentrate on making polygons "winding-agnostic" and 
"closing-point-agnostic". I'm not convinced however that that is so 
easy. If you calculate a convex hull, do you want it returned in the 
same winding direction as you defined it? It will have an influence, 
plus a performance malus, on many algorithms. By just providing the 
"correct" algorithm we enable library users to use our library with 
every polygon. It cannot be called from the algorithms themselves: to 
verify the winding rule the area has to be calculated beforehand. This 
will drastically decrease performance.

The solution might be a traits class telling the winding rule the 
polygon type has. That might be ever implemented, but for now we'll 
better concentrate on other things. Same for closing point.

Regards, Barend