Re: [boost] [geometry] convex_hull: dispatch implementation details

Subject: Re: [boost] [geometry] convex_hull: dispatch implementation details
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-07-20 12:55:26

Hi Jeremy,

Jeremy Murphy wrote:
> Hi,
>
> just wondering why boost::geometry::convex_hull is implemented with that
> dispatch-struct-apply business?  Is it because of the two forms of
> convex_hull: output reference and output iterator?

Everything is described here: 
http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/design.html

In short, Boost.Geometry defines various geometries concepts and 
algorithms which works for them.
Any class may be adapted to one of the concepts.
The algorthm may find out which concept is it by the use of 
geometry::tag<> trait and then dispatch the algorithm.
In Boost.Geometry this is done using tags dispatching technique, 
specializing a struct for Tag template parameter and providing static 
apply() member function.

It's similar to the STL Iterators and algorithms.
Any class may be adapted to one of the Iterators concepts.
The Iterator "kind" may be retrieved from 
std::iterator_traits<>::iterator_category
Then an algorithm may be dispatched to handle verious iterators differently.
E.g. std::distance() is implemented differently for ForwardIterator and 
RandomAccessIterator.
However in most of the STL implementations the dispatching is done on 
the function level.
But the idea is the same.

Then, various Strategies may be passed to the Boost.Geometry algorithms 
to define some details of the algorithms.
And to STL algorithms Predicates (e.g. less) may be passed.

> I'm writing a concave_hull implementation, so I'm wondering whether I
> should emulate the conventions in the convex_hull implementation.

It's great that you're implementing concave_hull()!
I'm assuming that since you're asking about the internals of 
Boost.Geometry you plan to contribute your work to the library?

If your implementation e.g.:
- works only for some Geometries
- may be implemented differently for some Geometries
then yes, you should use this dispatching scheme.
E.g. the implementation of convex_hull() and concave_hull() for a Box is 
trivial.

Note that in the case of convex_hull() the main part is the Strategy:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp
The code in convex_hull.hpp only dispatches the algorithm and calls the 
Strategy for most of the Geometries.
You should probably do the same in concave_hull() but this depends on 
the algorithm I suppose.

But all of the things mentioned above may be added later.
I propose to focus on the implementation of the algorithm first.

We could give you tips about how it could/should be implemented in 
Boost.Geometry if you provided more information about your plans, e.g.:
What algorithm or algorithms would you like to implement?
Do you plan to implement the algorithm for some specific geometries only 
or all of them?
Do you plan to implement this algorithm for cartesian coordinate system 
or/and some other?
Is your implementation available somewhere?

This algorithm would be new to Boost.Geometry so we should probably 
think about the interface, parameters, etc.
E.g. the function in PostGIS takes 3 parameters:
http://postgis.net/docs/ST_ConcaveHull.html
http://www.bostongis.com/postgis_concavehull.snippet
and is able to produce a hull with or without holes.
In the case you wanted to implement more algorithms than one, would they 
expect the same set of parameters?

Regards,
Adam