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-19 13:22:49

Hi,

some more comments here.

> > One projects can be a lot of work and you propose to work on 2 at the
> > same time. Are you certain you'd like to do it? Or is it maybe
> > because both projects are somehow related, i.e. one is needed by the
> > other?
>
> There is a relation in the sense that I think that a fast (not necessarily
> Delaunay) triangulation algorithm and a triangle concept are beneficial for
> a random point generator that generates points uniformly distributed inside
> a polygon (and this is probably true for higher dimensions as well). For a
> large number of points, I found that directly sampling to triangles
> outperforms a rejections sampler.

As far as I know there are (at least) 3 ways to generate random
points: a) rejection-acceptance, b) triangulation + simplex (triangle)
sampling, c) random walks. You found (a) slower but I guess this
depends on how you implement membership for the geometry (given a
point answer if it is inside of outside geometry). With a fast
membership rejection sampling should be very competitive. So I think
it make sense to implement both a,b (and maybe some c methods that
would be useful for sampling on boundary) and test for which cases the
one is faster than the other. Finally, since you mention high
dimensions, there (a), (b) are very slow as dimension grows (size
oftriangulation has exponential dependence on dimension) so (c) is the
only way, but this is another story...

> Other than that, my proposal to combine two projects is based on a
> conservative estimate of the total amount of work. It took roughly a day to
> implement an initial, imperfect variant of s-hull (for the programming
> competency test) and the triangulation algorithms commonly described in
> literature seem to be intuitively accessible enough to be implemented
> properly in a reasonable timeframe. The random samplers are, in my opinion,
> a simpler problem than the triangulation, so they can be completed afterward
> but still within the GSoC. I am certain that I can produce a good quality
> implementation with proper tests and documentation of the proposed features
> in the GSoC work period with reasonable effort.
>
> > What coordinate systems are you planning to support? Cartesian,
> > geographic, etc. In case you decided to implement algorithm for one
> > coordinate system, would the same algortihm theoretically work with
> > different ones or would different algorithm be required?
>
> Regarding the random generators: Generally, uniform sampling can be done in
> geographic coordinates using an equal-area transformation from the cylinder
> to the sphere, and I have considered that in the proposal (last paragraph
> before milestones).
>
> However, I imagine that in GIS applications one is usually interested in
> very small subsets of the sphere so rejection_sampling would be
> prohibitively expensive. In the programming competency test, I implemented a
> more efficient sampler for convex polygons by decomposing it into triangles
> and sample uniformly on triangles.
>
> I suppose the most obvious approaches would be to do the same thing for
> polygons on spheres (I've found a straightforward way to do that in
> literature: https://www.graphics.cornell.edu/pubs/1995/Arv95c.pdf ) or to at
> least chose some box or polygon in cartesian coordinates so that its image
> (under an equal area transformation) covers the interesting area of the
> sphere and not too much more, take uniform samples in it, map them to the
> sphere, and reject them if necessary.
>
> I'd be thankful for input from potential users of randomly generated points
> in geographic (or other) coordinate systems if there is more to consider.
> More on randomly generated points below.
>
> Regarding triangulation: In my literature research for the proposal, I
> concentrated on Delaunay triangulations in cartesian coordinates. I've
> looked into the spherical case and there is a lot of literature for that as
> well, for example, this paper on adapting Fortune's algorithm to spheres (
> http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf ). I've seen
> very intuitive approaches to that using complex hull algorithms and
> projections to the sphere. I don't know how well and with how much effort
> the algorithm I've linked in my proposal translates to triangulations on
> spheres but I will think about it.
>
> Do you know how much interest there would be in Delaunay triangulations on
> spheres and what the usual use case would be? If someone enters 3 points
> does he want a decomposition of the sphere into 4 triangles or would one
> usually be interested in the triangulation of a small subset of the sphere?

Delaunay triangulations on a sphere can be used for maritime zone
determination (but I am not the right person to speak about
applications ;) For a more robust approach you can have a look at this
paper: https://link.springer.com/chapter/10.1007%2F978-3-642-13193-6_39
and this implementation in python:
https://github.com/tylerjereddy/py_sphere_Voronoi

I discuss about Delaunay and Voronoi without taking care of splitting
the discussions since those two are equivalent and I think that your
Delaunay implementation should also made it possible to the user to
compute the Voronoi (probably two interfaces that share the same
implementation).

Best,
Vissarion

> > 2. Triangulation
> >
> > So triangulation is basically a triangle mesh represented by arrays
> > of vertices and indexes, correct? If that's the case then maybe we
> > need more general mesh concept?
>
> I suppose it could be generalized. Edges and vertices would remain the same
> thing but faces could be arbitrary rings with more than three adjacent
> faces.
>
> > If the result of triangulation is a mesh then why do you need
> > triangle concept as 3-point ring? Wouldn't a view/proxy used
> > internally in your algorithm and storing iterators/pointers to
> > vertices in the mesh be enough?
>
> I imagine triangles are useful primitives in general and it would be
> beneficial to have the concept to specialize some existing algorithms for
> them (like area) so that their implementation can make use of the additional
> constraint of the triangle being a ring with only three points. I agree that
> internally in the algorithms for Delaunay triangulation, triangles would be
> represented by views with iterators to vertices but I thought that would not
> make a difference because those views and triangles that actually store
> vertices could both fulfill the same concept.
>
> > You mentioned Boost.Graph. Would your algorithm depend on this
> > library? If possible we should avoid dependencies. If it doesn't
> > depend then we could still have concepts compatible with other
> > libraries so the same types can be easily adapted to work with both.
>
> I would not depend on it because the algorithm linked in the proposal (as
> far as I can see) does not use any complicated graph operations. It would be
> nice to be compatible with BGL because I've already had cases in which I had
> to perform more complicated graph operations on meshes.
>
> > left-of-predicate in Boost.Geometry is called "side strategy" and is
> > implemented for all supported coordinate systems.
>
> I completely overlooked that one. I see that it is designed to optionally
> supports higher precision coordinate types. I will look further into that.
>
> > in-circle-predicate however is not. It also looks like more complex
> > operation since you have to find a center of the circle and then
> > check if a point is inside it. In Boost.Geometry this would be
> > divided into centroid() and distance(). So my guess is that the in-
> > circle-predicate should be divided into more basic building blocks.
> > However I'm not sure if the center of the circle is the same as
> > barycenter in non-cartesian coordinate systems. Furthermore
> > Boost.Geometry doesn't have non-cartesian centroid yet. Even if you
> > do not support geographic triangulation right now we should do
> > theoretical work and prepare the interface for future extensions,
> > i.e. know what basic coordinate-system-dependant operations will be
> > needed in the future.
>
> I implemented it in that two-stage way in my implementation of Delaunay
> Triangulation for the programming competency test. However, I found that
> this seems to be usually done in a single step (see
> https://www.cs.cmu.edu/~quake/robust.html ), I guess for performance and
> stability reasons. I noticed that with larger problem sizes (1'000'000
> points and more) my Delaunay triangulation would not terminate for some runs
> (I generate the problems randomly) and some experiments (I did not look too
> deeply into it) suggest that my two-staged, non-robust in-circle-predicate
> is to blame here.
>
> I would trust the literature there and implement a simple approximate
> predicate that works for non-degenerate problems and an adaptive predicate
> that will be a little slower but still work for degenerate cases.
>
> > In case you wanted to work on centroid too, geographic centroid could
> > be yet another whole project for GSoC, we were actually considering
> > to add it. ;)
>
> I am afraid that would lead to overstretching my proposal. ;)
>
> > 3. Randomization
> >
> > Just an idea about the generalization of the interface. I can imagine
> > that someone may want to generate points in the interior of a polygon
> > and someone else may want points in the interior or on the boundary,
> > etc. With current design you'd have to add more function names for
> > various conbinations, correct?
>
> I would not create special generators for all conceivable cases. But I think
> handling some special cases is very benefecial. The one I produced for the
> programming competency test for project 4 uses a trivial fan triangulation
> and uses that to produce random samples directly rather than sampling from
> the bounding box and rejecting based on the within-predicate.
>
> I did not commit it but I did write a simple rejection sampler as well and
> found it to be much slower (I think about 2-3 times), even though the convex
> polygons are comparatively simple geometries to check within for and they
> cover a large portion of their bounding box so only a good portion of
> samples would not be rejected.
>
> > AFAIU the rejection_generator would be a special case of a generator
> > capable to take spatial predicates defining returned points. In this
> > case returning points that are let's say within(A) && ! covered_by(B)
> > (so in the interior of A and in the exterior of B). So another
> > possibility is to have a generator taking general spatial predicates.
> > Furthermore, the above (points in interior/boundary/exterior) could
> > also be achieved with this approach.
>
> I totally agree with the suggestion that arbitrary spatial predicates should
> be supported for rejection sampling.
>
> > Note also that performing randomization for arbitrary geometries
> > would be supported with this interface, also e.g. N random points
> > within multipoint.
>
> I agree but the probability of a uniformly distributed point lying inside a
> multipoint (except for a very coarse space) is vanishingly small. I think
> that point generation should at least be specialized by the type of domain
> (discrete, lines, volumes).
>
> > It is also possible to decide to go this way but do not implement all
> > elements right now. In such case we could think about the interface
> > and be prepared for extensions in the future. E.g. for now support
> > only something like this:
> >
> > namespace bg = boost::geometry;
> > bg::rng::generate(bg::rng::within(A), output);
>
> I like that interface. I would maybe drop the rng, because it's conceivable
> to have generators in the future for deterministic point generation as well,
> for example to create some regular lattice or nodes on edges.
>
> 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