NAME
Math::PlanePath::LCornerTree -- cellular automaton growing at exposed corners
SYNOPSIS
use Math::PlanePath::LCornerTree;
my $path = Math::PlanePath::LCornerTree->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
This is the pattern of a cellular automaton growing by 3 cells from an exposed corner at each growth level. Points are numbered anti-clockwise within their level. The default is four quadrants starting from four initial cells N=0 to N=3,
68 67 66 65 4
69 41 40 39 38 35 34 33 32 64 3
42 20 19 37 36 18 17 31 ... 2
43 21 8 7 6 5 16 30 1
44 45 9 1 0 4 28 29 <- Y=0
47 46 10 2 3 15 63 62 -1
48 22 11 12 13 14 27 61 -2
49 23 24 54 55 25 26 60 -3
70 50 51 52 53 56 57 58 59 75 -4
71 72 73 74 -5
^
-5 -4 -3 -2 -1 X=0 1 2 3 4The rule is that a cell which is an exposed corner grows by the three cells surrounding that corner. So
depth=0 depth=1 depth=2 depth=3
d d d d d d d d
\| |/ \| |/
c c c c d-c c-d d-c c-d
\| |/ \| |/
b b b b c-b b b b-c d-c-b b b b-c-d
\| |/ \| |/ /| \| |/ |\
a a b-a a-b b-a a-b d d b-a a-b d d
-> -> ->
a a b-a a-b b-a a-b d d b-a a-b d d
/| |\ /| |\ /| |\ |/
b b b b c-b b b b-c d c-b b b b-c-d
/| |\ /| |\
c c c d-c c-d d-c c-d
/| |\ /| |\
d d d d d d d d"a" is the first cell in each quadrant and grows into the three "b" around each. Then for the "b" cells only the corner ones are exposed corners and they grow to the "c" cells. Those "c" cells are then all exposed corners and give a set of 36 "d" cells. Of those "d"s only the corners are exposed corners for the next "e" level.
Grouping the three children of each corner shows the growth pattern
+-----------------------+
| | | | |
| +-----+ | +-----+ |
| | | | | | |
|--| +-----+-----+ |--|
| | | | | | |
| +--| +--+--+ |--+ |
| | | | | | |
|-----+--+--+--+--+-----|
| | | | | | |
| +--| +--+--+ |--+ |
| | | | | | |
|--| +-----+-----+ |--|
| | | | | | |
| +-----+ | +-----+ |
| | | | |
+-----------------------+In general the number of cells gained in each level is 4*3^count1bits(depth). So for example depth=3 binary "11" has 2 1-bits so cells=4*3^2=36. Through to a depth=2^k adding all those powers-of-3 gives a power-of-4 square area.
Each side part turns by 90 degrees at its corner, so the plane is filled in a self-similar style turning into each side quarter, making an attractive way to fill the plane by a tree structure. See Math::PlanePath::LCornerReplicate for a digit-based approach to the replication.
+----------------+
| | |
| ^ | ^ |
| \ | / |
| \ | / |
| | |
|-------+--------|
| | |
| ^ | \ |
| / | \ |
| / | v |
| / | |
+----------------+One Quadrant
Option parts => 1 confines the pattern to the first quadrant. This is a single copy of the repeating part in each of the four quadrants of the full pattern.
parts => 1
4 | 18 17
3 | 14 13 12 11 16
2 | 15 6 5 10
1 | 3 2 4 9
Y=0 | 0 1 7 8
+---------------------
X=0 1 2 3 4 Half Plane
Option parts => 2 confines the tree to the upper half plane Y>=0, giving two symmetric parts above the X axis.
parts => 2
36 35 34 33 4
37 27 26 25 24 21 20 19 18 32 3
28 12 11 23 22 10 9 17 2
29 13 6 5 4 3 8 16 1
30 31 7 1 0 2 14 15 <- Y=0
--------------------------------------
-5 -4 -3 -2 -1 X=0 1 2 3 4Three Parts
Option parts => 3 is three replications arranged in a corner down and left similar to the way the tree grows from a power-of-2 corner X=2^k,Y=2^k.
parts => 3
55 54 50 49 4
56 43 42 41 40 28 27 26 25 48 3
44 19 18 39 29 14 13 24 2
45 20 10 9 5 4 12 23 1
46 47 11 2 0 3 21 22 <- Y=0
------------------+ 1 8 38 37 -1
| 6 7 17 36 -2
| 30 15 16 35
| 31 32 33 34 53
| 51 52
^
-5 -4 -3 -2 -1 X=0 1 2 3 4Ulam Warburton
Taking just the non-leaf nodes gives the pattern of the Ulam-Warburton cellular automaton, oriented as per Math::PlanePath::UlamWarburtonQuarter and using 2x2 blocks for each cell.
parts=>1 non-leaf points
...
** ** ** **
** ** ** **
** **
** **
** ** ** **
** ** ** **
**
**
** ** ** **
** ** ** **
** **
** **
** ** ** **
** ** ** **
*parts=>4 gives the pattern of Math::PlanePath::UlamWarburton but turned 45 degrees and again in 2x2 blocks.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::LCornerTree->new ()$path = Math::PlanePath::LCornerTree->new (parts => $integer)-
Create and return a new path object.
partscan be 1, 2, 3 or 4.
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$nhas no children (including when$n < 0, ie. before the start of the path).Each point has either 0 or 3 children. Such a tree is sometimes called a "3-tree". The children of a corner
$nare the three cells adjacent to it which turn to "on" at the next depth. A non-corner has no children.
OEIS
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A160410 (etc)
parts=4 (the default)
A160410 total cells at given depth (Ndepth)
A161411 added cells at given depth, 4*3^count1bits(n)
parts=3
A160412 total cells at given depth (Ndepth)
A162349 added cells at given depth, 3*3^count1bits(n)
parts=1
A130665 total cells at given depth (Ndepth)
A048883 added cells at given depth, 3^count1bits(n)Drawings by Omar Pol
parts=4
http://www.polprimos.com/imagenespub/polca023.jpg
http://www.polprimos.com/imagenespub/polca024.jpg
parts=3
http://www.polprimos.com/imagenespub/polca013.jpg
http://www.polprimos.com/imagenespub/polca027.jpg
http://www.polprimos.com/imagenespub/polca029.jpg
parts=1
http://www.polprimos.com/imagenespub/polca011.jpg
http://www.polprimos.com/imagenespub/polca012.jpg
http://www.polprimos.com/imagenespub/polca014.jpgSEE ALSO
Math::PlanePath, Math::PlanePath::LCornerReplicate, Math::PlanePath::UlamWarburton, Math::PlanePath::ToothpickTree
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2012, 2013 Kevin Ryde
This file is part of Math-PlanePath-Toothpick.
Math-PlanePath-Toothpick is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath-Toothpick is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath-Toothpick. If not, see <http://www.gnu.org/licenses/>.