Hi Tinko, Adam, thanks for the interest in the project! In general I find your proposal good but a bit overambitious. I am mainly covered by Adam's response but I have a few comments. 1. Apart from the two projects (triangulation and random generators) your project includes one more, namely "robust geometric predicates" that could be a solely GSOC project. This is not described in the proposal but what I am understanding is something like this http://www.cs.cmu.edu/~quake/robust.html (there are many solutions for robust predicates I just named one) to be done for both "orientation" (aka side) and "in-circle" predicate and for all 3 coordinate systems. 2. The center of the circle passing by three points is NOT the centroid (barycenter) of those points! The former could be outside of the triangle formed by the three points. Also it is not needed to split the problem of in-circle predicate in "simpler" functions, at least for cartesian this is very well studied. For other coordinate systems it needs some work/research. What I propose is to either focus on one topic (e.g. Delaunay triangulations) and go further in coordinate system support etc. or do Delaunay and random generators only for cartesian. In any case you can include more topics as extras. In other words there will not be a problem if you do more that you propose. Best, Vissarion On Mon, 18 Mar 2019 at 19:39, Adam Wulkiewicz via Boost <boost@lists.boost.org> wrote:
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
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost