
Boost : 
Subject: Re: [boost] [geometry] convex_hull: dispatch implementation details
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20140720 12:55:26
Hi Jeremy,
Jeremy Murphy wrote:
> Hi,
>
> just wondering why boost::geometry::convex_hull is implemented with that
> dispatchstructapply 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk