https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html

Untangle is a game where you must “untangle” the line so they don’t cross.

It requires a planar graph, meaning a graph that be laid on a plane.

I have tried browsing the code, it reads like old school C:

https://www.chiark.greenend.org.uk/~sgtatham/puzzles/puzzles.tar.gz

I just found this here:

http://johntantalo.com/wiki/Planarity/

`Let M be the lines q in L ordered by the intersection points of p with q and p != q.`

Although I don’t understand this pseudocode, the “label” or the “Let M be the lines q in L ordered by the intersection points of p with q and p != q.” part.

Some hints for understanding the pseudo code:

The third line of pseudo-code, considering that L is a list

``````For each line p in L:
``````

means that we iterate for each element in the the list, and call it p in the loop body.

The fourth line means that we will construct a list called M , of all the other lines (q are the lines in L that are different from p):

``````    Let M be the lines q in L ordered by the intersection points of p with q and p != q.
``````

The elements in a list are ordered, and the order is specified in this list definition as the intersection points.

Considering that lines are in geometric terms not finished segments, but have an infinite length, this pseudo code leaves some minor ambiguity:

• p and q will cross either once, or never (2 parallel lines) or on an infinity number of points (2 parallel lines and that are superposed, i.e. the same line with two names). This last possibility is excluded.
• in consequence, it is not clear what to do if there’s no intersection: are these lines excluded from the result ? Or do they just have some arbitrary order?
• the order of the line is the order of the intersection point: this order is not defined (is it the order of the point name ? is it the lexicographic order of the coordinate components ?

The “labelling” means that you give a name to each line. In mathematical terms, this means that you define a mapping from the list of lines to a number between 1 and n. In other words, each line gets a name that corresponds to a number or an index.

Some hints for understanding the algorithm?

I cannot explain you why this algorithm works. But now that the instructions are explained, you may try to execute it on a tiny sample to get an understanding about what’s going on.