[WIP] Uniform polygon sampling

[OwenGraves]

I'd like to implement uniform polygon sampling. I've added uniform triangle sampling, but am still working on the other methods.

Any and all feedback, criticism, or best practices information would be much appreciated! 😄

[lemmih]

Nice! You can split a polygon into triangles by using the triangulation module and this code snippet:

import Algorithms.Geometry.PolygonTriangulation.Triangulate

polygonTriangles :: (Ord r, Fractional r) => Polygon t p r -> [SimplePolygon p r]
polygonTriangles p =
    map (view core) $
    map (`rawFacePolygon` g) $
    map fst $ V.toList (internalFaces g)
  where
    g = triangulate' Proxy p

[OwenGraves]

Not sure if the animation is in the right place (or setting files modified correctly) and the animation could be beautified, but it seems to work!

[noinia]

Does this strategy of sampling triangles really produce a uniform sampling? Intuitively it seems similar to sampling in a disk by taking an uniform sample of polar coordinates. However that does not produce an uniform sampling in the disk, as you are more likely to pick points near the center this way. This type of sampling seems very similar to that, so I would like to see more evidence that this produces the right result.

A simple alternative strategy is to simply sample uniformly at random from the boundingbox of the triangle and resample if it turns out that point does not lie in the triangle (but that is a bit slower/may require more random bits).

[lemmih]

The sampling /is/ uniform. We use the triangle to create a parallelogram which can be sampled uniformly. A sampled point has a 50% chance of being outside of the original triangle. If the point is outside, we reflect it over the triangle edge such that it ends up inside the triangle. Thus we have uniform sampling in O(1) steps.

This article describes the approach in detail: https://blogs.sas.com/content/iml/2020/10/19/random-points-in-triangle.html

[lemmih]

I'll document the algorithm before merging this PR.

[lemmih]

Hi @OwenGraves, I've modified your animation to use text polygons:

https://user-images.githubusercontent.com/1443107/111307837-f0502c80-8694-11eb-8273-4cb220dbf11d.mp4

There are still a few TODO items left but I think we can handle those in another PR and merge this one.

[lemmih]

TODO items:

• [ ] O(log n) sampling using a fingertree.
• [ ] Uniform sampling of multiple polygons at once.
• [ ] Drop the Real r constraint (by not using fromList).

[lemmih]

On the website: https://hgeometry.org/#uniformsampling

[OwenGraves]

Awesome, that animation looks really cool!

[OwenGraves]

Another TODO item could be to implement the Alias method since it looks like it might be a way to do this sampling in O(1) after the initial setup.