The game like Untangle / Planarity

After last 2 posts about geometry, I decided to explain, how to make a game like Untangle (solving planar graph by moving vertices).

Idea of the game

Let’s specify, what exactly we want to do and how we are going to do it.

Where we get the graphs?

The game works with planar graphs (which can be drawn without line crossings). If we just make a random graph, it can be non-planar (for example, $K_{3,3}$ is not planar).

We can make the graphs manually, but first we must come up with some good ideas for graphs. Another option is to generate them with a computer.

We know, that triangulated graph is planar. In the last article about Voroi diagram we made an algorithm, which makes a Delaunay triagnulation of some points. So we can use it.

We should check edge crossings and draw a graph accordlingly to them. This checking can be used from the last article about Geometry.

So, we should do these things:

• generate random 2D points
• compute the triangulation (list of edges)
• throw out some edges to make the graph simpler
• shuffle vertices on random positions (I put them into a circle)
• let the user to move vertices, redraw the graph

Extra features

We can add some nice graphics into our game, or some extra features. The game would be much more interesting and may be also joyful. I used techniques described above and created the game FlyTangle. If you like it and you have Google Chrome browser, you can install it as a Chrome app.