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... . 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_s... 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_v... . 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/i...). 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/refere... ) 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