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-26 15:06:23

Hi Tinko,

On Sat, 23 Mar 2019 at 16:09, Tinko Bartels via Boost
<boost_at_[hidden]> wrote:
>
> 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.

What do you mean? What is the assessment you refer to?

> 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.

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

Best,
Vissarion

> Kind regards,
> Tinko Bartels
>
>
>
> --
> Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost