Re: [boost] [GTL] clipping and merge of general polygons withattributes

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-06-08 19:23:17

Bruno Lalande wrote:
>Your API based on tag dispatching looks good to me. Could you just be
>more precise on the polygon concepts? Which are the different valid
>expressions required by each of them? For now Barend's library doesn't
>use concepts to represent polygons but a provided class, due to the
>complexity of manipulating a polygon (compared to a linestring for
>example, that can be summarized by a mere pair of iterators). So I'm
>curious to see what could be a polygon concept...

I'm glad to hear that you approve of the tag dispatching based generic
API.  I have been assuming that the lack of strong opposition to the
idea on the boost list meant that people generally approved.  :)

I noticed that Barend's library provided a heavily templated polygon
class.  Unfortunately providing a new polygon data type does not benefit
most applications, which already have their own polygon if one was
needed.  The primary benefit that generic programming can provide in
such an environment is to ease and improve the quality of integration of
new library algorithms with application data types, such as polygon.  To
be very specific, a polygon must be able to get and set its outer shell
using iterator semantics over polygon vertices.  It should also be
default/copy constructible and provide an assignment operator such that
it can be an element of a std container.  Additionally, to support
efficient axis-parallel polygon data crunching it should provide the
"compact" iterator interface to get and set its shell based upon ranges
of non-redundant coordinates (one per edge).  I provide lazy iterator
algorithms for up and down converting from iterator ranges of points to
compact coordinates and visa-versa.  It is expected that getting compact
iterator range would throw en exception if the polygon were not
axis-parallel.  Any of these requirements need not be satisfied if the
templates that use them are not instantiated, and I would provide
separate checks, instead of is_polygon.  This is because some polygon
objects may be read-only, not default constructable, or otherwise
crippled, but still compatible with a useful subset of the polygon
concept related behaviors in my library.  I specifically do not require
polygons to conform to a winding orientation convention or open/closed
(redundant last vertex) convention because these choices are made
arbitrarily by authors of polygon data types, and it is not particularly
hard to write loops that are invariant to such considerations, though it
does increase validation effort.  Because a legacy polygon data type
will provide its own legacy vertex type I must also provide a vertex
concept in my library to be able to consume an iterator range over the
legacy vertex type.

>One other question: at the beginning your library was supposed to me
>limited to 90 and 45 degrees computations (if I understood well), but
>you're now talking about arbitrary angles. Has the scope of your
>library changed? Did I miss something?

Yes, and no.  At the beginning I said that we have an internal code base
of arbitrary angle algorithms that may be ported into my library at some
future time.  We have two independent implementations of scanline on
arbitrary angle polygons.  I have been scheduled to port one of these
into my library within the next several weeks.  I didn't have a concrete
plan for when this work would happen before, and now I do, so that has
changed.

Thanks,
Luke