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
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