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: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-03-19 16:53:52

I appologize for answering myself but I have one more side note.

Adam Wulkiewicz wrote:
> Tinko Bartels Via Boost wrote:
>>> 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).
>
> If the interface allowed it and predicates were passed they would 
> define in which topological parts the randomized points would be. So 
> if one wanted to get points within multipoint like this:
>
> generate(N, within(multipoint), output)
>
> the algorithm would return N points from a multipoint (in the interior 
> of multipoint, see: https://en.wikipedia.org/wiki/DE-9IM). Note that 
> it doesn't mean it would have to be rejection sampler because we can 
> imagine a case when the predicate expression is analysed, new geometry 
> is generated from it and then sampling is done in this geometry, e.g.:
>
> generate(N, within(polyA) && ! within(polyB), output)
>
> could first calculate
>
> difference(polyA, polyB, polyC)
>
> and then generate points that are in polyC (with special handling of 
> boundaries because the boundary of polyB would be allowed).
>
> Not all predicates could be allowed, we could limit which kinds of 
> geometries and predicates can be passed together, etc.
>
I probably overcomplicated this. If it's true that rejection sampling is 
slower in all cases then we can move the responsibility for creating the 
geometry to the user. So we do not have to calculate the difference, 
support the concatenation of predicates with operator&&, etc. since the 
user can generate an arbitrary geometry and pass it to the generator. 
All is needed is the support for single randomization predicate.

So predicates like within, covered_by, touches, intersects are obvious, 
but how about disjoint? Does it have sense to generate a random point 
outside the geometry using the whole available exterior space? Not sure 
about the cartesian but in spherical and geographic I can imagine 
someone would like to do this.

Adam