[boost] [GTL] proposal for geometry set operations

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-05-07 18:45:00

The most useful algorithms implemented in the library are the polygon
set operations.  Also known as layer mask operations, Boolean
operations, polygon clipping and merge etc.

In the code uploaded to the vault the API for applying these algorithms
is a little old fashioned and OO in nature.  I have in mind a generic
API.

I define a polygon_set_concept, which is defined as anything that models
a collection of polygon data, which could be a std::container of
polygons, or rectangles, or a data structure that contains the internal
representation used by my scanline algorithm that applies Boolean
operations.  (The polygon_set is so named because it is an argument to
polygon set operations, not because it is somehow associated with
std::set.)

        struct polygon_set_concept {...};

The polygon set concept provides the behaviors for objects that model
polygon set.

I define a polygon_set_traits, which must be specialized for user data
types that model polygon set.

        template <>
        polygon_set_traits<std::list<UserPolygonType> > { 
          ...minimal interface to satisfy concept... };

The user must register their type as a polygon set type:

        template <>
        geometry_traits<std::list<UserPolygonType> > { typedef
polygon_set_concept geometry_concept; };

Then the user can use their type along with the library provided type to
perform set operations through the intuitively overridden c++ logical
operators & | ^ -.

        template <typename geometry_type_1, typename geometry_type_2>
        polygon_set_view operator&(const geometry_type_1& geo1, 
                                        const geometry_type_2& geo2) { 
                ...tag dispatching and so forth... }

I also provide some Boolean logic capabilities to move flow control into
functional code.

        template <typename geometry_type>
        polygon_set_view operator&(const geometry_type& geo, bool
condition) { 		if(condition) return polygon_set_view(geo); }

to the user to write code that looks like the following:

std::list<UserPolygonType>* do_something_complex(bool condition1, 
                                                        bool condition2)
{
        std::list<UserPolygonType>*  resultPolygons = 
                new std::list<UserPolygonType>;
        std::vector<rectangle_data> input1;
        initialize1(input1);
        std::vector<rectangle_data> input2;
        initialize2(input2);

        //if both condition1 and condition2 are true return the merged 
        //result of the subtraction of input2 from input1
        //stored as UserPolygonType into resultPolygons		
        //if condition1 is true and condition2 is false return input1 
        //merged and stored as UserPolygonType into resultPolygons
        //if condition1 is false return empty resultPolygons
        resultPolygons |= ((input1 & condition1) - (input2 &
condition2));
        //legacy application puts onus on caller to delete
resultPolygons
        return resultPolygons;
}

Note that I'm using a polygon_set_view to provide lazy evaluation of the
scanline algorithm when chaining operations.  A polygon_set_view models
the polygon_set_concept on the lazily produced result of the operation.

Because evaluation is lazy, the result of a Boolean operation should be
stored to a polygon_set data structure before the arguments go out of
scope or are deleted to ensure correct execution.  Checking and proper
generation of exceptions for such cases should be provided by the view.
Modification of an argument after creating a view from it and before
evaluating the view would be an undetectable user error.

This proposed API is the most concise and intuitive way I can think of
to provide these algorithms to the library user.

Thoughts?

Thanks,
Luke