Planarity
From Johnwiki
Planarity is a web game that I made in 2005 based on an idea of Mary Radcliffe's. The official website is Planarity.net.
Contents |
Generating Planar Graphs
Notice
Please note that this algorithm is offered "as is" and with no warranty or guarantee. Although this algorithm is not patented and algorithms cannot be copyrighted, I consider it a significant work of mine. That said, if you wish to use or modify the algorithm below, please consider citing me, John Tantalo, as a courtesy.
Algorithm
- Generate a set of random lines in a plane such that no two lines are parallel.
- Calculate the intersections of every line pair.
- Create a graph with a vertex for each intersection and an edge for each line segment connecting two intersections.
If a graph is generated from n lines, then the graph will have n choose 2 = n(n-1)/2 vertices (each line has n-1 vertices, each vertex is shared with one other line) and n(n-2) edges (each line contains n-2 edges).
The first level of Planarity is built from n=4 lines, so it has n(n-1)/2=6 vertices and n(n-2)=8 edges. Each level after is generated by one more line than the last. If a level was generated with n lines, then the next level has n more vertices and 2n-1 more edges.
Pseudocode
Input: a list L of n 2-dimensional lines, and a labeling A from each p in L to {1...n}
- Let G be an empty graph.
- Add vertices {1...n(n-1)/2} to G.
- For each line p in L:
- Let M be the list of lines q in L such that p != q.
- Order M by the intersection points of p with each q in M.
- For each pair Mi and Mi+1:
- Let u = PairIndex(A(p), A(Mi), n).
- Let v = PairIndex(A(p), A(Mi+1), n).
- Add an edge (u, v) to G.
- Return G.
This algorithm assumes lists index from 1.
Pair Index
In the graph, every pair of distinct lines (p, q) corresponds to exactly one vertex v, but it is much more convenient to address this vertex as a single value than a tuple. So, how do we most efficiently map (p, q) into v? The function PairIndex does this by mapping each (p, q) to some number between 1 and (n(n-1)/2) (inclusive), the range of vertices.
- Definition
- If 1 <= p < q <= n, then PairIndex(p, q) = (p(2n-p-1)/2)+q-p, where n is the number of lines.
- Claim
- PairIndex is a bijection (i.e., one-to-one and onto) between {(p, q) | 1 <= p < q <= n} and {1...n(n-1)/2} for a fixed n.
- Proof
- PairIndex is linear in q for a fixed p. When p=1, PairIndex takes on the values {1..n-1}. When p=n-1, PairIndex takes on the value n(n-1)/2. The maximum value of PairIndex for any p, or PairIndex(p, n-1), is exactly 1 less than the minimum value of PairIndex for p+1, or PairIndex(p+1, p+2), so PairIndex must be a bijection. Given the definition above, some basic algebraic manipulation is needed to show that PairIndex(p, n-1) + 1 = PairIndex(p+1, p+2). ∎
- This proof is due to Mary Radcliffe.
Other Implementations
- Multi-Touch Interaction System by Jeff Han (video)
- gPlanarity by Monty, written in GTK+.
- TangleBee by SmartMelon Games, for Windows.
- Tangle by MC Hot Software, for Mac OS X.
- Planar Game by Eric Abouaf, written in Javascript using the WireIt library.
- Untangle by Chris Benjaminsen, written in Flash.
- UntangleManiak by PuzzleManiak (Alexandre Minard), for the iPhone.
- The Plateau (Lite) by Spoon Juice, for the iPhone.
- "Haunted House" on a Microsoft Surface (video)
