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

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:
http://www.iis.sinica.edu.tw/page/jise/2012/201205_10.pdf

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.

Cheers.

Jeremy

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