Geometry Boost List: [ggl] clockwise-ness

Subject: [ggl] clockwise-ness
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-10-19 10:23:16

Hi list,

Herewith again the topic of the start of July.

> [...] 4) Implementing the orientation in the polygon traits class as a 
> three-state option: clockwise, counter clockwise or 
> undetermined/both/unknown. The library can then handle it accordingly, 
> only making the check in the last case.
> [...]
> Solution 4 is probably the most generic and convenient.

This is handled in the library now, in preparation of the review. It is 
"part of the design", so should be there, and some (actually many) 
algorithms handle it correctly now.

So there is the meta-function / traits class point_order, which can be 
specialized for rings to denote counter-clockwise-ness (default is still 
clockwise).

The algorithms area, correct, and convex-hull are adapted. The within 
algorithm was already agnostic to order, so is also working. Many other 
algorithms as perimeter, simplify do not depend on it. The overlay 
algorithms will probably not yet be adapted (so will not compile for 
counter-clockwise geometries).

For area there was an issue: it was handled by std::abs previously. That 
is removed to be more pure. If the polygon is correct, it is positive, 
if it is reverse to the specified direction, it is negative.

For convex hull there was an issue: it operated on an output-iterator. 
The output-iterator itself does not have any notion of what it outputs 
to (at least, not that I know of). So there always a clockwise ring is 
assumed. However, the version with the output iterator might be 
inconvenient anyway, sometimes, because most algorithms have the form of 
geometry, geometry (so input, output).

Therefore the (proposed) behaviour is as following:
convex_hull(geometry_in, geometry_out)
convex_hull_inserter(geometry, output_iterator)

So the original functionality is renamed, a more generic function as 
added, outputting to a ring or a polygon. It is not possible to merge 
these two because a geometry is a reference, an output iterator is 
normally an object (besides that, it returns the output-iterator as well).

Is there agreement on this? This (the _inserter postfix) will probably 
also be the convention for simplify, and/or for intersections (there 
were discussions on output iterators earlier), to have a consistent design.

Finally, the provided geometries linear_ring and polygon have an 
optional boolean flag (template parameter) now to denote counter 
clockwise order (default is also here still clockwise).

Regards, Barend