*This is no longer true! I wrote a package for this, and wrote a way better one! I recommend that if you try out triangulation now, you use Poisson Disc Sampling to generate fill points (if you’re going for evenly spaced points of course). I stole a stack-overflow response that does this it works, it’s just slow. A sort of ok solution is to generate a ton of random points and then remove them until none are within a certain distance to each other. Unfortunately, there’s no R package to do this*.
There’s actually an algorithm to generate random, but evenly spaced points: poisson-disc sampling. On the other side we could try an evenly spaced grid, but this is just too perfect and regular–A classic goldilocks dilemma. Generating random points is an obvious place to start, but random points tend to make a bunch of clusters and voids, we want something more evenly spaced. The fill points will determine how big the triangles and how many triangles make up our final image, so it’s a very important step. Once I had my outline points, there’s some finagling to get them in the format that RTriangle wants, and then we need to generate some fill. I built a shiny app that lets me interactively click on the outline points to choose those I want to keep and put them in an ordered dataframe which I can copy and paste into R using datapasta.
In the end this was a problem that’s super easy for a human, but surprisingly hard for a machine, so I decided to do it manually. There was also not a great way to reduce the number of points to make a more triangular outline that still resembled the original silhouette. I actually coded up a solution to do this using the tsp package, but later realized the algorithm doesn’t work well when there are sharp corners and is generally unreliable. What we need to do is find the shortest path through the points while only visiting each point once–the classic traveling salesman problem. Getting the outline of my giraffe was easy using imager::cannyedges, but this doesn’t put them in order. The RTriangle package can do constrained triangulation, but you need to specify a set of ordered edge points. What I really want is a constrained Delaunay triangulation, which as it turns out, is much harder to do. Technically this is what I asked R to do, but it’s not what I wanted it to do. The first thing I got working looked like this. The pixel sampling relies on high-contrast so a perfect silhouette is the ideal example to start with… little did I know this would influence my final outcome quite a bit. My image of choice was a black and white silhouette of a giraffe, because I think giraffes are cute. Using these points we calculate the delaunay triangulation using the deldir package (Fronkonstin calculated the voronoi tessellation, which is the dual graph of the Delaunay triangulation–more on that later). Here we take an image, convert it to greyscale, then sample points based on the darkness of each pixel. This excellent post from Fronkonstin (an amazing math art R blog) did most of the work for me. You can click and drag the corners of the triangle to change its shape, find the midpoint between two points, and rotate a shape around a point.I started out trying to calculate the Delaunay triangulation of an image. You might find the interactivity below useful for this:
Simple tessellation ideas triangles series#
If your answer is yes, can you explain how you know that all triangles tessellate, and can you give an algorithm (a series of instructions) that you can use on any triangle to produce a tessellation? If your answer is no, can you give an example of a triangle which doesn't tessellate and explain why it doesn't? Now try drawing some triangles on blank paper, and seeing if you can find ways to tessellate them. You can print off some square dotty paper, or some isometric dotty paper, and try drawing different triangles on it. You could also draw some triangles using this interactive. Let's think about other triangles which tessellate: We say that a shape tessellates if we can use lots of copies of it to cover a flat surface without leaving any gaps.įor example, equilateral triangles tessellate like this: