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

Hi Tinko, On Sat, 23 Mar 2019 at 16:09, Tinko Bartels via Boost 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#b... ) 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>

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 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 only makes sense on something like a sphere and is equivalent to sampling inside the reversed ring, that uniform_point_distribution requires sampling along a range of segments, and that uniform_point_distribution 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_spher... ).

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