Re: [boost] [gsoc19] Seeking a mentor for Boost.Geometry project related to triangulation and random sampling

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