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: Tinko Bartels (tinkobartels_at_[hidden])
Date: 2019-04-01 23:33:50

Hi Vissarion, hi Adam,

On Tue, 2019-03-26 at 17:06 +0200, Vissarion Fisikopoulos wrote:
> Hi Tinko,
> 
> What do you mean? What is the assessment you refer to?
> 

The assessment that a well-designed specialized solution outperforms the
more general ones (in their conclusion). That's a very general statement, of
course, never the less I'd be concerned that sharing the implementation for
Delaunay Triangulation between cartesian and spherical coordinates would
make the code more complicated and more challenging to optimize so that it
can be competitive for either case. 
If I understood correctly (5 Implementation and Experiments, first
paragraph) the implementation they based their's on was already very well
suited for adaption to triangulation on the sphere but still required
modification beyond using other geometric predicates.

The algorithm I implemented for the competency test (based on shull) would
also require modification beyond using other left-of and
in-circle-predicates, for example the reverse of the convex hull would still
need to be triangulated at the end and when adding points to the
triangulation, additional logic would need to be applied to determining
"visible" edges. I am sure the proposed algorithm would also require some
modifications to work on the sphere.

I suggest that I'll only promise an implementation for cartesian coordinates
in the proposal and try to make it work for spherical coordinates if enough
time is left after completing all the work.

> In general, the sketch of the proposal looks good to me. Looking
> forward to read your detailed draft.
> 
> Best,
> Vissarion
> 

Here it is
https://docs.google.com/document/d/137y91owur6kOIe1aK229Ap1d8ASeL18vSbeZv_dP-6o/edit?usp=sharing
.

Over the weekend I've put the proposed interface to a first test and
implemented a uniform distribution for some cases. The draft implementation
can be used like this for some geometries g1, g2

auto dist = bg::random::uniform_point_distribution<Point, Geometry,
bg::random::boundary>(g1);
bg::generate::generate(out.begin(), out.end(), std::bind(dist,
std::ref(gen)), !bg::generate::within<Point>(g2));

With regard to what constitutes interior or boundary, I've tried to conform
to the OGC standard that's linked in the Boost.Geometry documentation, here
is an example of the output

https://tinko92.github.io/boost_geometry_GSoC_2019_project_3_4_test/random_samples_interior_boundary.svg

I understand that the members of a multi linestring only have a boundary if
they are not closed.

I generated green points in the interior of a polygon (the one with the
large hole), a box, a multilinestring and a multipoint with the predicate
within(star), and blue points on the boundary of the same geometries but
with the predicate !within(star). @Adam, I think this interface can cover
the possible use cases you hinted at in your first reply to my proposal.

The code used to generate that svg can be found here:
https://tinko92.github.io/boost_geometry_GSoC_2019_project_3_4_test/random_v2.html
. This page also links to my fork of the geometry repo and the branch
containing my draft implementation (
https://github.com/tinko92/geometry/tree/feature/uniform_sampler_extension/include/boost/geometry/extensions/random).
Please consider that an appendix to my programming competency test.

I understand that the proposal has not become less ambitious. Producing the
linked implementation has renewed my confidence that it can all be done in
less than three months, though. 

For the basic geometry concepts (
https://www.boost.org/doc/libs/1_69_0/libs/geometry/doc/html/geometry/reference/concepts.html
) there are basically 4 cases for uniform sampling, namely pointlike,
linear, areal and higher-dimensional (for >=3d boxes) and they are all very
easy to handle for cartesian coordinates and should be reasonably easy to
implement for spherical coordinates. Accounting for the work to document and
test it properly, this should still leave more than enough time to complete
the delaunay/voronoi project.

Best,
Tinko

--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html