Beginner-friendly tasks

[lemmih]

1. Random, monotone polygons.

Done! PR: #95. Thank you @1ndy!

2. Ray-casting visibility polygon.

What?

Imagine that the edges of a polygon represents the walls of a room seen top-down. Standing at some point inside of the room, how much can you see and how much is obscured? The area you can see is called the "visibility polygon."

There are many advanced algorithms for computing the visibility polygon but we'll focus on the simplest, brute-force solution and solve the problem in O(n^2) time. This slow solution will be instrumental in writing and testing faster solutions.

How?

By shooting rays from a point of origin through each vertex, we'll know which edges are entirely visible, entirely obscured, or partially visible. The algorithm is described on Wikipedia.

Tests?

Pick a random point inside a random polygon and generate the visibility polygon. Now pick a second random point on the boundary of the original polygon. Draw a line between the two points and count the intersections. If there are no intersections, the second point must be in the visibility polygon. If there are intersections, the second point must not be in the visibility polygon.

Type signatures:

The final module should look something like this:

visibility :: SimplePolygon p r -> Point 2 r -> SimplePolygon () r

3. SSSP visibility polygon.

What?

Computing the visibility polygon from a corner is much easier than from an arbitrary point inside a polygon.

How?

HGeometry already has code for computing the single-source shortest-path tree. This SSSP tree can tell use which corners are occluded and, if so, which corner is occluding them. Shooting a ray from the point of origin through the occluding vertex can tell us how much of an edge is occluded.

The algorithm is explained exhaustively in this paper on page 218: https://doi.org/10.1007/BF01840360 The paper can be found for free on sci-hub.

There's a Haskell implementation available here: https://github.com/reanimate/reanimate/blob/5795a59d4481e5b506210cdf16ed9adec62f0ebf/src/Reanimate/Math/Polygon.hs#L704 It could serve as a good starting point.

Tests?

Same as in task 2 except we're only picking points from the polygon boundary.

Type signatures:

The final module should look something like this:

visibility :: SSSP -> SimplePolygon p r -> SimplePolygon p r

4. Pick a random point in polygon.

What?

It is often useful to uniformly sample points inside a polygon. This can be used for testing or when generating showcase animations.

How?

Sampling a random point from a triangle is quite simple. Polygons are more complex but, fortunately, we can reduce any polygon to a list of triangles. Picking a random point from a random triangle is close to being correct but it would favor small triangles over bigger triangles. We can correct for this by selecting larger triangles more frequently.

So, the algorithm would look like this:

1. Break the polygon down into triangles.
2. Assign a frequency to each triangle. The frequency is the area of the triangle over the area of the polygon. See fromList in MonadRandom: https://hackage.haskell.org/package/MonadRandom-0.1.3/docs/Control-Monad-Random.html
3. Pick a triangle from the list.
4. Sample a random point from the triangle.

Hint 1: TriangulateSpec.hs:31 has a function for splitting a polygon into triangles. Hint 2: Neat way of uniformly sampling a triangle: https://jsfiddle.net/96fw5x8p/1/

For extra credit: Use a finger tree to sample uniformly in O(log n) rather than in O(n).

Tests?

Any randomly sampled point should be inside the polygon or on the border.

Type signatures:

The final functions should look something like this:

-- | O(n log n)
samplePolygon :: (RandomGen g, Random r, Fractional r) => Polygon t p r -> Rand g (Point 2 r)
-- | O(n) sampleConvex is optional.
sampleConvex :: (RandomGen g, Random r, Fractional r) => ConvexPolygon p r -> Rand g (Point 2 r)
-- | O(1)
sampleTriangle :: (RandomGen g, Random r, Fractional r) => Triangle 2 p r -> Rand g (Point 2 r)

-- | O(n log n)
toTriangles :: (Fractional r, Ord r) => Polygon t p r -> [Triangle 2 p r]

[BebeSparkelSparkel]

@Lemmih I have created a lot of QuickCheck Arbitrary instances for polygons that may be helpful

https://bitbucket.org/william_rusnack/geometry-2d/src/master/src/PolylineArbitrary.hs

[lemmih]

Oh my, that looks cool. It'll take me a while to read through all of it.

[BebeSparkelSparkel]

Let me know if you have any questions. I have most of the development sketched out in a paper notebook so if you need I can scan those and add them here.

[lemmih]

I don't see your library on Hackage. It's a hidden gem. Thanks for telling me about; I wouldn't have found it otherwise.

[hafizhmakmur]

So.... We fork the repo and then we make a hgeometry- folder and implement it there?

[lemmih]

You fork the repo and create a new branch. The name of the branch isn't important. Then you either add a new module somewhere in hgeometry/src/ or you add your code to one of the existing modules. You can immediately create a draft Pull Request. That way, I can see what you're working on and help you along.

To create a draft PR, first make a commit in your own branch, push it to GitHub, and then go to the "Pull requests" tab for this project. GitHub will ask you if you want to create a new pull request. Say yes and change the type to "draft".

[hafizhmakmur]

How do we test and see existing algorithms (and eventually our own algorithm)? I'm not really sure how to use the examples.

[lemmih]

The available algorithms are listed on Hackage: https://hackage.haskell.org/package/hgeometry

If you want to run, say, the graham scan algorithm for convex polygons, then you can load the module in GHCi and run convexHull. It has this type signature:

convexHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> ConvexPolygon p r

This means it takes a non-empty list of points annotated with some extra data (called p) and returns a ConvexPolygon.

Now, this will just give you a bunch of coordinates and it's not particularly intuitive or visual. Ideally, I'd like to have graphical examples of all the algorithms offered by HGeometry. Five algorithms have already been animated and are hosted here: https://hgeometry.org The source code for the animations can be found in the hgeometry-showcase folder.

[hafizhmakmur]

Interesting. I'll see what I can do. Also wouldn't it be a good idea to set a fixed function name and type signature for all these tasks? So the tasks will be more concrete.

[lemmih]

That's a good idea.

[noinia]

In terms of generating random polygons; I think this would actually be nice to implement (as well): https://ilyasergey.net/papers/polygons-icfp16.pdf I.e. it describes a way to generate (simple) polygons by generating the dual tree of their triangulation

[sureyeaah]

@noinia I would like to implement that paper :)

[lemmih]

Great! If you make a draft PR then we can collaborate.

[sureyeaah]

@Lemmih Will share draft PR, just read the paper.