Boost logo

Geometry :

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

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

Geometry list run by mateusz at