Subject: Re: [boost] [gsoc19] Seeking a mentor for Boost.Geometry project related to triangulation and random sampling
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-03-18 17:39:07
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/17M44Hpn0KMuECztCbkvTYIeN2EiXbMAUsVni22KvkVA/edit?usp=sharing
>
> 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