| Copyright | (c) 2011, 2016 Brent Yorgey |
|---|---|
| License | BSD-style (see LICENSE) |
| Maintainer | byorgey@cis.upenn.edu |
| Safe Haskell | None |
| Language | Haskell2010 |
Diagrams.TwoD.Apollonian
Contents
Description
Generation of Apollonian gaskets. Any three mutually tangent circles uniquely determine exactly two others which are mutually tangent to all three. This process can be repeated, generating a fractal circle packing.
See J. Lagarias, C. Mallows, and A. Wilks, "Beyond the Descartes circle theorem", Amer. Math. Monthly 109 (2002), 338--361. http://arxiv.org/abs/math/0101066.
A few examples:
import Diagrams.TwoD.Apollonian apollonian1 = apollonianGasket 0.01 2 2 2
import Diagrams.TwoD.Apollonian apollonian2 = apollonianGasket 0.01 2 3 3
import Diagrams.TwoD.Apollonian apollonian3 = apollonianGasket 0.01 2 4 7
- data Circle n = Circle {}
- mkCircle :: Fractional n => n -> P2 n -> Circle n
- center :: Fractional n => Circle n -> P2 n
- radius :: Fractional n => Circle n -> n
- descartes :: Floating n => [n] -> [n]
- other :: Num n => [n] -> n -> n
- initialConfig :: RealFloat n => n -> n -> n -> [Circle n]
- apollonian :: RealFloat n => n -> [Circle n] -> [Circle n]
- data KissingSet n = KS {}
- kissingSets :: [n] -> [KissingSet n]
- flipSelected :: Num n => KissingSet n -> KissingSet n
- selectOthers :: KissingSet n -> [KissingSet n]
- apollonianTrees :: RealFloat n => [Circle n] -> [Tree (KissingSet (Circle n))]
- apollonianTree :: RealFloat n => KissingSet (Circle n) -> Tree (KissingSet (Circle n))
- drawCircle :: (Renderable (Path V2 n) b, TypeableFloat n) => Circle n -> QDiagram b V2 n Any
- drawGasket :: (Renderable (Path V2 n) b, TypeableFloat n) => [Circle n] -> QDiagram b V2 n Any
- apollonianGasket :: (Renderable (Path V2 n) b, TypeableFloat n) => n -> n -> n -> n -> QDiagram b V2 n Any
Circles
Representation for circles that lets us quickly compute an Apollonian gasket.
Constructors
| Circle | |
Fields
| |
Instances
| Eq n => Eq (Circle n) Source # | |
| RealFloat n => Floating (Circle n) Source # | The |
| RealFloat n => Fractional (Circle n) Source # | |
| RealFloat n => Num (Circle n) Source # | |
| Show n => Show (Circle n) Source # | |
Arguments
| :: Fractional n | |
| => n | signed radius |
| -> P2 n | center |
| -> Circle n |
Create a Circle given a signed radius and a location for its center.
radius :: Fractional n => Circle n -> n Source #
Get the (unsigned) radius of a circle.
Descartes' Theorem
descartes :: Floating n => [n] -> [n] Source #
Descartes' Theorem states that if b1, b2, b3 and b4 are
the bends of four mutually tangent circles, then
b1^2 + b2^2 + b3^2 + b4^2 = 1/2 * (b1 + b2 + b3 + b4)^2.
Surprisingly, if we replace each of the bi with the product
of bi and the center of the corresponding circle (represented
as a complex number), the equation continues to hold! (See the
paper referenced at the top of the module.)
descartes [b1,b2,b3] solves for b4, returning both solutions.
Notably, descartes works for any instance of Floating, which
includes both Double (for bends), Complex Double (for
bend/center product), and Circle (for both at once).
other :: Num n => [n] -> n -> n Source #
If we have four mutually tangent circles we can choose one of
them to replace; the remaining three determine exactly one other
circle which is mutually tangent. However, in this situation
there is no need to apply descartes again, since the two
solutions b4 and b4' satisfy
b4 + b4' = 2 * (b1 + b2 + b3)
Hence, to replace b4 with its dual, we need only sum the other
three, multiply by two, and subtract b4. Again, this works for
bends as well as bend/center products.
initialConfig :: RealFloat n => n -> n -> n -> [Circle n] Source #
Generate an initial configuration of four mutually tangent circles, given just the signed bends of three of them.
Apollonian gasket generation
apollonian :: RealFloat n => n -> [Circle n] -> [Circle n] Source #
Given a threshold radius and a list of four mutually tangent circles, generate the Apollonian gasket containing those circles. Stop the recursion when encountering a circle with an (unsigned) radius smaller than the threshold.
Kissing sets
data KissingSet n Source #
The basic idea of a kissing set is supposed to represent a set of four mutually tangent circles with one selected, though in fact it is more general than that: it represents any set of objects with one distinguished object selected.
Instances
| Show n => Show (KissingSet n) Source # | |
kissingSets :: [n] -> [KissingSet n] Source #
Generate all possible kissing sets from a set of objects by selecting each object in turn.
flipSelected :: Num n => KissingSet n -> KissingSet n Source #
"Flip" the selected circle to the other circle mutually tangent
to the other three. The new circle remains selected.
selectOthers :: KissingSet n -> [KissingSet n] Source #
Make the selected circle unselected, and select each of the others, generating a new kissing set for each.
Apollonian trees
apollonianTrees :: RealFloat n => [Circle n] -> [Tree (KissingSet (Circle n))] Source #
Given a set of four mutually tangent circles, generate the infinite Apollonian tree rooted at the given set, represented as a list of four subtrees. Each node in the tree is a kissing set with one circle selected which has just been flipped. The three children of a node represent the kissing sets obtained by selecting each of the other three circles and flipping them. The initial roots of the four trees are chosen by selecting and flipping each of the circles in the starting set. This representation has the property that each circle in the Apollonian gasket is the selected circle in exactly one node (except that the initial four circles never appear as the selected circle in any node).
apollonianTree :: RealFloat n => KissingSet (Circle n) -> Tree (KissingSet (Circle n)) Source #
Generate a single Apollonian tree from a root kissing set. See
the documentation for apollonianTrees for an explanation.
Diagram generation
drawCircle :: (Renderable (Path V2 n) b, TypeableFloat n) => Circle n -> QDiagram b V2 n Any Source #
Draw a circle.
drawGasket :: (Renderable (Path V2 n) b, TypeableFloat n) => [Circle n] -> QDiagram b V2 n Any Source #
Draw a generated gasket, using a line width 0.003 times the radius of the largest circle.
apollonianGasket :: (Renderable (Path V2 n) b, TypeableFloat n) => n -> n -> n -> n -> QDiagram b V2 n Any Source #
Draw an Apollonian gasket: the first argument is the threshold; the recursion will stop upon reaching circles with radii less than it. The next three arguments are bends of three circles.