# Difference between revisions of "Bounding box"

m |
AwesoMan3000 (talk | contribs) (→Notes) |
||

(21 intermediate revisions by 6 users not shown) | |||

Line 1: | Line 1: | ||

{{Glossary}} | {{Glossary}} | ||

− | The '''bounding box''' of a [[pattern]] is the smallest rectangular array of cells that contains the entire pattern. | + | The '''bounding box''' of a [[pattern]] is the smallest rectangular array of cells that contains the entire pattern. It is one of the standard ways to measure the [[size]] of an object; the other standard metric is the [[population]]. |

==Moving objects== | ==Moving objects== | ||

Line 8: | Line 8: | ||

===Leading edge=== | ===Leading edge=== | ||

− | The '''leading edge''' of a moving object is the edge of that object's bounding box that is farthest in the direction of travel, essentially, the "front" of the object. The leading edge of a diagonally moving object can be considered in two ways: it may incorporate both edges of the bounding box in its direction of travel, or, alternatively, it may be defined as the diagonal row of cells that is farthest in the direction of travel. Most known moving objects have a leading edge that only ever moves forward; in [[:Category: | + | The '''leading edge''' of a moving object is the edge of that object's bounding box that is farthest in the direction of travel, essentially, the "front" of the object. The leading edge of a diagonally moving object can be considered in two ways: it may incorporate both edges of the bounding box in its direction of travel, or, alternatively, it may be defined as the diagonal row of cells that is farthest in the direction of travel. Most known moving objects have a leading edge that only ever moves forward; in [[:Category:Patterns_found_in_1991|1991]], however, [[Dean Hickerson]] constructed the [[13-engine Cordership]], the first [[Types_of_spaceships#Non-monotonic_spaceship|non-monotonic]] [[spaceship]] -- a spaceship whose leading edge "falls back" in at least one generation.<ref>{{CiteLexicon|file=lex_n.htm#nonmonotonic|name=non-monotonic|accessdate=April 24, 2009}}</ref>. In [[:Category:Patterns_found_in_1992|1992]], [[Hartmut Holzwart]] found the [[Non-monotonic_spaceship_1|first orthogonal example]]. Since then many other spaceships have been found which exhibit this property, such as the [[weekender]]. |

===Trailing edge=== | ===Trailing edge=== | ||

− | The '''trailing edge''' of a moving object may be considered the "back" of the object. It is the edge of the bounding box which is farthest opposite direction of travel. For puffers and rakes this does not generally include their output. The trailing edge is described most commonly in reference to spaceships, as their shape often determines their reactions with [[tagalong]]s or other objects. | + | The '''trailing edge''' of a moving object may be considered the "back" of the object. It is the edge of the bounding box which is farthest opposite the direction of travel. For puffers and rakes this does not generally include their output. The trailing edge is described most commonly in reference to spaceships, as their shape often determines their reactions with [[tagalong]]s or other objects. |

==Stationary objects== | ==Stationary objects== | ||

− | The bounding box of a [[still life]] is | + | The bounding box of a [[still life]] is the bounding box which contains the pattern in its only phase. The bounding box of an [[oscillator]] is sometimes considered in one phase, but is most often expanded so as to include the entire oscillator in all of its phases. A [[gun]]'s bounding box is similar to that of an oscillator but it does not include any outgoing streams of spaceships. |

==Other life-like cellular automata== | ==Other life-like cellular automata== | ||

− | The same definitions of bounding box also apply in other [[Cellular_automata#Life-like_cellular_automata |life-like cellular automata]], and the [[Rule#Rules|rules]] for these cellular automata determine bounding box properties | + | The same definitions of bounding box also apply in other [[Cellular_automata#Life-like_cellular_automata |life-like cellular automata]], and the [[Rule#Rules|rules]] for these cellular automata determine bounding box properties. For example, it is quite simple to show that a rule with no births cannot contain any oscillators or moving patterns because patterns are unable to expand in any direction. |

===Spaceships=== | ===Spaceships=== | ||

− | The nonexistence of spaceships in life-like cellular automata can often be determined by simple patterns in the rulestrings, which affect the changes in a patterns bounding box. For an object to be considered a spaceship it must return to its initial phase (but in a different location), thus | + | The nonexistence of spaceships in life-like cellular automata can often be determined by simple patterns in the rulestrings, which affect the changes in a patterns bounding box. For an object to be considered a spaceship it must return to its initial phase (but in a different location), thus ensuring that the bounding box returns to a fixed size. For cellular automata with rules that include a birth with only one live neighbour, the bounding box of all patterns (excluding the pattern with no on cells) expands at the speed of light in every direction. Spaceships also cannot exist in rules with survival at zero, one, two, three, and four cells, as the trailing edge of a moving pattern could never completely die. For rules that do not have births at one, two, or three cells, the pattern can never expand beyond its initial bounding box, preventing any spaceships from existing. Such a rule can have oscillators however (provided it has births), but these oscillators will never leave their initial bounding box, and so their bounding boxes can be treated in the same way as those of still lifes. |

+ | |||

+ | == See also == | ||

+ | * [[Bounding diamond]] | ||

==Notes== | ==Notes== | ||

Line 30: | Line 33: | ||

==External links== | ==External links== | ||

− | + | {{LinkLexicon|lex_b.htm#boundingbox}} |

## Revision as of 23:57, 25 July 2018

The **bounding box** of a pattern is the smallest rectangular array of cells that contains the entire pattern. It is one of the standard ways to measure the size of an object; the other standard metric is the population.

## Contents

## Moving objects

The bounding box of a moving object is often considered in only one phase, but may also refer to the bounding box that contains the object in all phases of its period. For puffers and rakes this usually does not include their output.

### Leading edge

The **leading edge** of a moving object is the edge of that object's bounding box that is farthest in the direction of travel, essentially, the "front" of the object. The leading edge of a diagonally moving object can be considered in two ways: it may incorporate both edges of the bounding box in its direction of travel, or, alternatively, it may be defined as the diagonal row of cells that is farthest in the direction of travel. Most known moving objects have a leading edge that only ever moves forward; in 1991, however, Dean Hickerson constructed the 13-engine Cordership, the first non-monotonic spaceship -- a spaceship whose leading edge "falls back" in at least one generation.^{[1]}. In 1992, Hartmut Holzwart found the first orthogonal example. Since then many other spaceships have been found which exhibit this property, such as the weekender.

### Trailing edge

The **trailing edge** of a moving object may be considered the "back" of the object. It is the edge of the bounding box which is farthest opposite the direction of travel. For puffers and rakes this does not generally include their output. The trailing edge is described most commonly in reference to spaceships, as their shape often determines their reactions with tagalongs or other objects.

## Stationary objects

The bounding box of a still life is the bounding box which contains the pattern in its only phase. The bounding box of an oscillator is sometimes considered in one phase, but is most often expanded so as to include the entire oscillator in all of its phases. A gun's bounding box is similar to that of an oscillator but it does not include any outgoing streams of spaceships.

## Other life-like cellular automata

The same definitions of bounding box also apply in other life-like cellular automata, and the rules for these cellular automata determine bounding box properties. For example, it is quite simple to show that a rule with no births cannot contain any oscillators or moving patterns because patterns are unable to expand in any direction.

### Spaceships

The nonexistence of spaceships in life-like cellular automata can often be determined by simple patterns in the rulestrings, which affect the changes in a patterns bounding box. For an object to be considered a spaceship it must return to its initial phase (but in a different location), thus ensuring that the bounding box returns to a fixed size. For cellular automata with rules that include a birth with only one live neighbour, the bounding box of all patterns (excluding the pattern with no on cells) expands at the speed of light in every direction. Spaceships also cannot exist in rules with survival at zero, one, two, three, and four cells, as the trailing edge of a moving pattern could never completely die. For rules that do not have births at one, two, or three cells, the pattern can never expand beyond its initial bounding box, preventing any spaceships from existing. Such a rule can have oscillators however (provided it has births), but these oscillators will never leave their initial bounding box, and so their bounding boxes can be treated in the same way as those of still lifes.

## See also

## Notes

- ↑ "non-monotonic".
*The Life Lexicon*. Stephen Silver. Retrieved on April 24, 2009.

## External links

- Bounding box at the Life Lexicon