Planarity
From Johnwiki
Planarity is a web game that I made in 2005 based on an idea by Mary Radcliffe. 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.
This algorithm is not patented. I know of no other prior art or patent for this algorithm. Given that, it was first published 3 April 2007 and is now in the public domain.
The specific pseudocode and illustrations below are copyrighted by John Tantalo. The proof is copyrighted by Mary Radcliffe.
I consider the algorithm a significant invention of mine. That said, if you wish to implement, adapt, or modify the algorithm below, please consider citing me, John Tantalo, the author, 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 lines q in L ordered by the intersection points of p with q and p != q.
- For each consecutive 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-1)(2n-p)/2+q-p
- Many thanks to Manfred Kroehnert and Craig Bailey for improving this definition.
- 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
- Observe that PairIndex is linear in q when p is fixed. When p=1, PairIndex takes on the values {1..n-1}. When p=n-1, PairIndex is n(n-1)/2. For a given p, the the minimum value is PairIndex(p,n) and the maximum value is PairIndex(p,p+1). Basic algebraic manipulation is required to show that the maximum value of PairIndex for any p is exactly one less than the minimum value for p+1. Therefore every value in {1...n(n-1)/2} must correspond to exactly one pair (p, q). ∎
- This proof is due to Mary Radcliffe.
References
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 (Microsoft Surface)
- LightsOut by Jacob Hughes
- Planarity by Jason Davies (JavaScript+D3)
- Crazy Bugs by Ivan Kuckir (JavaScript+WebGL)
- Planarity Game by Nannette and Peter Liske (Java)
