Hi Tinko, Tinko Bartels Via Boost wrote:
Hi,
I am interested in participating in this year's Google Summer of Code with a contribution to Boost.Geometry. I am looking for mentors and I understand that potential mentors for Boost.Geometry-related projects are Vissarion Fysikopoulos and Adam Wulkiewicz.
Thanks for your interest. Yes we're potential mentors for Boost.Geometry.
My proposal is a project that is based on project 3 and 4 for Boost.Geometry in the Wiki. I propose to add concepts for triangles, triangulation, and point-generators for random sampling, as well as corresponding models and an algorithm for Delaunay-triangulation with parametrizable geometric predicates.
The first draft of my proposal can be found here: https://docs.google.com/document/d/17M44Hpn0KMuECztCbkvTYIeN2EiXbMAUsVni22Kv...
My implementation of the tasks in the competency tests can be found here: https://tinko92.github.io/boost_geometry_GSoC_2019_project_3_4_test/
I'd be thankful for any feedback.
The proposal looks good and I have a few questions. 1. General One projects can be a lot of work and you propose to work on 2 at the same time. Are you certain you'd like to do it? Or is it maybe because both projects are somehow related, i.e. one is needed by the other? What coordinate systems are you planning to support? Cartesian, geographic, etc. In case you decided to implement algorithm for one coordinate system, would the same algortihm theoretically work with different ones or would different algorithm be required? 2. Triangulation So triangulation is basically a triangle mesh represented by arrays of vertices and indexes, correct? If that's the case then maybe we need more general mesh concept? If the result of triangulation is a mesh then why do you need triangle concept as 3-point ring? Wouldn't a view/proxy used internally in your algorithm and storing iterators/pointers to vertices in the mesh be enough? You mentioned Boost.Graph. Would your algorithm depend on this library? If possible we should avoid dependencies. If it doesn't depend then we could still have concepts compatible with other libraries so the same types can be easily adapted to work with both. left-of-predicate in Boost.Geometry is called "side strategy" and is implemented for all supported coordinate systems. in-circle-predicate however is not. It also looks like more complex operation since you have to find a center of the circle and then check if a point is inside it. In Boost.Geometry this would be divided into centroid() and distance(). So my guess is that the in-circle-predicate should be divided into more basic building blocks. However I'm not sure if the center of the circle is the same as barycenter in non-cartesian coordinate systems. Furthermore Boost.Geometry doesn't have non-cartesian centroid yet. Even if you do not support geographic triangulation right now we should do theoretical work and prepare the interface for future extensions, i.e. know what basic coordinate-system-dependant operations will be needed in the future. In case you wanted to work on centroid too, geographic centroid could be yet another whole project for GSoC, we were actually considering to add it. ;) 3. Randomization Just an idea about the generalization of the interface. I can imagine that someone may want to generate points in the interior of a polygon and someone else may want points in the interior or on the boundary, etc. With current design you'd have to add more function names for various conbinations, correct? In Boost.Geometry we use the standard topological definitions, e.g. here: https://en.wikipedia.org/wiki/DE-9IM. So one possibility is to have one function and take parameters defining where your random points should be, in the interior or boundary or exterior of a geometry, but... AFAIU the rejection_generator would be a special case of a generator capable to take spatial predicates defining returned points. In this case returning points that are let's say within(A) && ! covered_by(B) (so in the interior of A and in the exterior of B). So another possibility is to have a generator taking general spatial predicates. Furthermore, the above (points in interior/boundary/exterior) could also be achieved with this approach. Note also that performing randomization for arbitrary geometries would be supported with this interface, also e.g. N random points within multipoint. It is also possible to decide to go this way but do not implement all elements right now. In such case we could think about the interface and be prepared for extensions in the future. E.g. for now support only something like this: namespace bg = boost::geometry; bg::rng::generate(bg::rng::within(A), output); Just a thought. Adam