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: Vissarion Fisikopoulos (fisikop_at_[hidden])
Date: 2019-03-19 10:56:03

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_at_[hidden]> 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/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
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost