[boost] [GTL] clipping and merge of general polygons with attributes

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-06-04 14:46:43

I am currently porting pre-existing internal code for performing scanline based merge of arbitrary-angle planar polygons into GTL.  The algorithm carries generic property values associated with the input polygons through to the output.  That means that if polygon A has property X and polygon B has property Y the output of merge would be potentially three types of polygons, those with property X, those with property Y and those with property {X, Y}.  This is essentially the 2D version of the interval set operations proposed by Joachim Faulhaber.  Obviously, it can be used as the foundation for general Boolean operations: e.g. the intersection between all polygons with property X and all polygons with property Y is simply the portion of the output with property {X, Y}.  

I wanted to ask Bruno and Barend to comment on whether they think this algorithm would be useful and solicit the boost community in general to comment on my progress designing the interfaces to it.  I looked at Barend's library and could only find rectangle clipping, did I miss it, or is a comparable capability not provided by Barend's geometry library?

I also looked at the documentation for Mateusz Loskot's geos library, but was only able to find linestring intersection algorithms, and the geometry container and polygon container types didn't obviously support Boolean operations, though I could have missed it.  I would have expected that it would.

I have added arbitrary angle polygon data types and concepts to GTL to support the API the algorithm will provide.  These are different from those proposed by Barend, though the concepts should be compatible with his data types.  My concepts for polygons center around the idea that they should be able to provide iterator range semantics for getting and setting their contents.

I have concepts for the following

struct polygon_90_concept {...};
struct polygon_90_with_holes_concept : polygon_90_concept {...};
struct polygon_45_concept : polygon_90_concept {...};
struct polygon_45_with_holes_concept : virtual polygon_45_concept, polygon_90_with_holes_concept {...};
struct polygon_concept : polygon_45_concept {...};
struct polygon_with_holes_concept : virtual polygon_concept, polygon_45_with_holes_concept {...};

A polygon_90 is a polygon that is restricted to axis-parallel edges, and has angles that are all multiple of 90-degrees.
A polygon_45 is a polygon that has angles that are all multiple of 45-degrees.
A polygon is a polygon with arbitrary angles.

The concepts inherit from each other to share some implementation, such as the holes, and to allow some measure of polymorphism of polygon types.  For instance, the result of a Boolean operation on 90-degree geometry could be stored to arbitrary angle polygons at the output with the same generic function call as would be used to store to 90-degree polygons because an arbitrary angle polygon can represent 90-degree angle data.

The high level overview of the API proposal is that generic free functions detect the conceptual type of geometry objects that are called on and redirect the call to the function of the same name defined within the appropriate geometry concept, sometimes with tag dispatching to select between different versions of the function within the concept.  For example contains:

template <typename geometry_type_1, typename geometry_type_2>
bool contains(const geometry_type_1& geometry_object, const geometry_type_2& contained_geometry_object, 
              bool consider_touch = true) {
  return geometry_concept<geometry_type_1>::type::contains(geometry_object, contained_geometry_object,
                                                           consider_touch, typename geometry_concept<geometry_type_2>::type());
}

might be called on a rectangle and a point, a polygon and a rectangle, or any other sensible combination of geometry objects, provided that the associated concept structs define the algorithm required conforming to the syntax expected.  For example, the rectangle contains point function is defined as follows:

  template <typename rectangle_type, typename point_type>
  static bool contains(const rectangle_type& rectangle, const point_type point_contained, 
                                bool consider_touch, point_concept tag) {
    return interval_concept::contains(get<HORIZONTAL>(rectangle), point_concept::get<HORIZONTAL>(point_contained), consider_touch, no_type()) &&
      interval_concept::contains(get<VERTICAL>(rectangle), point_concept::get<VERTICAL>(point_contained), consider_touch, no_type());
  }

This indirection leads to some welcome benefits to usability.  It leads to very simple and straightforward syntax errors in incorrectly formed user code, for instance, say the user calls vertical(user_point_object), which shouldn't work because vertical expects a rectangle or prism, the compiler generates the fairly readable error:

gtl.hpp: In function typename component_type<geometry_type>::type vertical(const geometry_type&) [with geometry_type = point_data<int>]:
main.cpp:14:   instantiated from here
gtl.hpp:125: error: vertical is not a member of point_concept

, telling the user only where their mistake was (main.cpp:14) and what is wrong (vertical is not a member of point_concept), which is exactly the information the user needs to fix their error and not more.

Other syntax errors may result in substitution failure such as if the user calls center(user_point_object), which shouldn't work because a point doesn't have a center, the compiler generates a substitution failure error instead:

main.cpp:14:   instantiated from here
post_geometry_traits_definitions.hpp:24: error: no type named center_type in struct point_concept::registration<point_data<int> >
main.cpp: In function void foo():
main.cpp:14: error: no matching function for call to center(point_data<int>&)
main.cpp: In function bool testRectangle():

, informing the user that point doesn't provide a center_type and giving them the very clear error that there is no function center() which takes their data type.

In the case that the user has not registered their type with the library the error will look like:
...
gtl.hpp:125: error: <function name> is not a member of no_type

I could change the name of no_type to undefined_concept to make it a little more obvious what is going on.

I am currently considering adding a coordinate_concept and coordinate_traits to the library because for 32-bit integer we would like to use 64-bit integer for area types and double for Euclidean distance, but for floating point coordinates we would just use the coordinate type for those.  With the need for numerical robustness of arbitrary geometry algorithms looming the use of more advanced coordinate data types looks likely, which might necessitate traits.

As always, I welcome any feedback that will help me improve the library and make it conform to boost standards/expectations for eventual review when I have completed the re-write.

You can find the up-to-date re-write of the library in sandbox/gtl.

Thanks,
Luke