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-03-23 14:08:43

Hi Adam, hi Vissarion,

I've attempted to use your feedback to refine my proposal, and I hope that I
addressed that feedback as well as the general Boost guidelines
sufficiently. 

I understand that projects 3 and 4 are opening up a considerable space of
possible designs, so I think, the most important thing would be to define
and document a general interface. I'll start with project 4:

I think it would be sensible to design random geometries to match the
existing interface for random sampling found in Boost and the STL. That
would mean, we have (pseudo-)random generators, random distributions, and
free generate-functions. The point of generators is to create pseudo-random
numbers, and the point of random distribution is to map them to values that
conform to some distribution. We do not need new generators to create random
geometries, we only need new distributions of geometries. Borrowing from the
existing requirements for distributions in Boost (
https://www.boost.org/doc/libs/1_66_0/doc/html/boost_random/reference.html#boost_random.reference.concepts
) and STL, I propose

for a distribution class X, returning objects of type T, a param_type P, a
value u of X and possibly const values x, y of X, p a value of type P, and a
UniformRandomNumberGenerator e returning numbers of type U:

X::result_type returns T
X::param_type returns P
X(p) constructs a distribution from parameters
u.reset() ensures that the following returned values do not depend on the
previous ones
u(e) returns a value of T 
u(e, p) equivalent to X(p)(e)
x.param() gets the parameters
x.param(p) sets the parameters
x == y, x != y compares the distributions
os << x, is >> u writes the state and parameters to os or restores them from
is.

I've omitted min() and max() because these concepts cannot be directly
translated from random numbers to geometries. Possible replacements could be
to return points that are min_corner and max_corner of the envelope of
possible values, or, more generally, there could be a domain()-member that
returns the space of all possible values, but I'd be unsure how to interpret
that for anything but points, and I'm not sure that this would be a useful
interface.

For use with existing generators and the described concept of geometry
distributions I propose two simple generate and generate_n functions that
optionally take a unary predicate, as Adam suggested. This predicate would
take one value of T and return true or false. I agree with Adam,
specializing on those would be overcomplicating things, and I'll address
uniform distributions below. I would simply run them on every generated
value before putting it into the output range, for maximum flexibility. That
way all predicates that Adam referenced could be supported. 
Vissarion, you mentioned random walks. This design would allow for
non-independently distributed output as well, and the internal state could
be reset and preserved as with RandomNumberDistributions. I hope that it
also can be a basis for future distributions that could generate random
geometries other than points (for example for testing).

Based on that concept, the implemented distributions for project 4 could
look like this:

uniform_point_distribution<typename Point, typename DomainGeometry, typename
DomainTag = interior, typename Strategy = default_strategy&lt;...>>

where DomainTag is one of interior, boundary or exterior (exterior only
makes sense when the exterior of the DomainGeometry has bounded measure, for
example with polygons on spheres), DomainGeometry is the type of geometry
that is supplied as domain and Point is the type of the output.

With respect to the concept above, T is Point, P is a struct holding an
instance of DomainGeometry and reset does nothing.

@Adam, I tried to write it in a way that allows all the possibilities you
mentioned but leaves the computation of the domain (which is the only
parameter of a uniform distribution) to the user. The implementations can
then deduce at compile-time that template parameters
uniform_point_distribution<point, ring, interior> require sampling in some
area, maybe by triangulation, perhaps by sampling from the envelope and
rejection based on the within-predicate, that
uniform_point_distribution<point, ring, exterior> only makes sense on
something like a sphere and is equivalent to sampling inside the reversed
ring, that uniform_point_distribution<point, ring, boundary> requires
sampling along a range of segments, and that
uniform_point_distribution<point, multipoint, interior> could be done using
uniform_int_distribution.

I will keep your comment with regard to transformations in mind. Generally,
transformations between spherical and cartesian coordinates will distort
distributions, but in the particular case of uniform distributions, those
will be preserved by equal-area transformations. The distortion of the
polygon would be an issue though, in determining a suitable cover of it to
sample from. If we get triangulation in spherical coordinates, we could use
the simple algorithm described in this paper:
https://dl.acm.org/citation.cfm?id=218500 . It describes an equal-area
transformation from the unit square to a spherical triangle for uniform (and
stratified) sampling in spherical triangles. I noticed, btw that Boost
already supports generating random points on a sphere (
https://www.boost.org/doc/libs/1_69_0/doc/html/boost/random/uniform_on_sphere.html
).

Concerning project 3, I agree with Vissarions suggestion to make a general
polygonal mesh that could represent Voronoi diagrams and to design the
algorithms in a way that allows the calculation of either one or both of
Delaunay triangulation and Voronoi diagram. I've read the article which you
provided about spherical Delaunay Triangulations, and I've also looked into
its reference 33 (Na, H.S., Lee, C.N., Cheong, O.: Voronoi diagrams on the
sphere) in which the problem is solved by solving a corresponding problem in
the plane. If the assessment of
https://link.springer.com/chapter/10.1007%2F978-3-642-13193-6_39 is correct,
providing a mostly shared implementation for Voronoi triangulation in the
plane and on the sphere might be difficult and not desirable. As far as I
can see, currently boost has also no support for algebraic numbers.

Having reconsidered the proposal, I think a reasonable goal for a 3 month
GSoC work period is to document and define the concepts above, implement
uniform distributions for points for the interiors of all documented
geometries at least in cartesian coordinates, possibly in the different
spherical coordinate systems as well, and implement a fast and robust
Delaunay triangulator/Voronoi diagram generator for points the plane and in
cartesian coordinates and make an assessment on whether the algorithm is
suitable for adaption to Delaunay Triangulation on spheres.

I'd be happy to hear further suggestions, and I'll try to refine the
proposal until next week and update the competency test to illustrate the
use of the interface described above.

Kind regards,
Tinko Bartels

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