Boost logo

Boost :

Subject: Re: [boost] [geometry] convex_hull: dispatch implementation details
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2014-07-21 09:39:26

Hey Adam,

thanks for the generous reply! OK, yeah, that makes sense about supporting
different geometries via strategies, etc.

I am working on the implementation on company time, so I'll have to ask
them about contributing it -- I would love to, of course and I think there
is a good chance. The algorithm I'm using is a relatively recent and
simple one by Park and Oh:

I will probably implement it specifically for my work's purpose to begin
with, but I would like to keep geometry and coordinate genericity as a goal
in the back of my mind. The parameters in PostGIS are about the same as
what I'm doing, although the percent coverage may work differently to Park
& Oh's "smoothness" parameter. I wasn't planning to include holes but I
can see that it would be a useful feature.



On 21 July 2014 02:55, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]> wrote:

> 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:
> 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:
> 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:
> 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
> _______________________________________________
> Unsubscribe & other changes:
> mailman/listinfo.cgi/boost

Boost list run by bdawes at, gregod at, cpdaniel at, john at