Bounding box

For general discussion about Conway's Game of Life.
Post Reply
User avatar
ssaamm
Posts: 125
Joined: June 4th, 2010, 9:43 pm

Bounding box

Post by ssaamm » February 6th, 2011, 10:46 pm

Well, I've been thinking about the theory of lightspeed and such, and I think it's about time we found a new standard better than "bounding box". I think that if every cell was represented by the smallest possible point, it would be the area of the smallest possible octagon that could have each of those points within it or on the edges of it. What do you think?

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: Bounding box

Post by Mats » February 7th, 2011, 12:30 pm

I'm not sure I understand this. What is "the smallest possible point" that represents a cell? The center point of the cell? Any point of your choise within or on the boundary of the cell? Somthing else? And what do you mean by "octagon"? A regular octagon? A convex octagon? Any shape with eight sides and eight corners? Something else? What would the "bounding octagon" of three cells in a row (a blinker) be?

User avatar
calcyman
Posts: 2226
Joined: June 1st, 2009, 4:32 pm

Re: Bounding box

Post by calcyman » February 7th, 2011, 1:25 pm

The idea of a bounding octagon has already been proposed:
Heinrich Köenig wrote:Another side effect of this is that it might be incorporated into a
metric for calculating bounds for objects -- take the intersection
of the orthogonal and the diagonal bounds.
Dave Greene wrote:A bounding octagon -- yes! On that metric, I have a whole pile of
guns that are smaller than the ones in the current gun collection --
but the combined forces of tradition and practicality are too strong
(bounding octagon metrics are much less amenable to manual
calculation) and Jason would never change the rules at this point.
At least, I sure hope not...
What do you do with ill crystallographers? Take them to the mono-clinic!

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Bounding box

Post by 137ben » February 7th, 2011, 5:41 pm

As I posted in another thread, why force everything to be the same shape? We could measure area by a bounding polyomino (I already posted this in two other threads, so I will spare the details here).

Whenever a standard shape is selected, it will still be an arbitrary bounding shape. Allowing the bounding polyomino to vary would give a better idea of how much space the pattern takes up.

User avatar
ssaamm
Posts: 125
Joined: June 4th, 2010, 9:43 pm

Re: Bounding box

Post by ssaamm » February 7th, 2011, 6:18 pm

I'll be more specific to clear things up here, because I'm not sure we're all on the same page...
If every cell were represented by a point in the very center of it, this would be the smallest possible equal-angular octagon, and it would be aligned with the grid so the top and bottom sides are flat with the horizon.

I chose this because patterns almost always extend either horizontally or vertically in life. (sorry knightships)
An alternative could be the smallest possible ellipse, I guess.

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Bounding box

Post by 137ben » February 7th, 2011, 7:25 pm

It is still a very arbitrary shape (and I still don't understand why you picked it, since I can't think of any patterns that are roughly octangular).

User avatar
ssaamm
Posts: 125
Joined: June 4th, 2010, 9:43 pm

Re: Bounding box

Post by ssaamm » February 9th, 2011, 7:26 pm

Well, it does make it so that diagonal patterns don't end up with extra junk in them...I'm starting to like the polyomino setup, though, even though it may be difficult to calculate in larger patterns.

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Bounding box

Post by 137ben » February 9th, 2011, 9:58 pm

Yea, I think part of the reason the bounding rectangle has been used historically is because it is extremely easy to compute. For small patterns the bounding polyomino is easy to calculate by hand, but for large patterns...I guess it would be a matter of checking each combination of connecting chunks. Still, I can compute the bounding box of the gemini almost instantly by pressing ctrl-a, but a script to find the bounding polyomino would take quite awhile if it has to search through every combination of connections between gliders in the instruction tape. The bounding polyomino is a reasonable thing to measure when asking (for example) what the smallest pattern that results in infinite growth is (a 13-omino is sufficient), but once patterns start getting really big it becomes troublesome.

User avatar
ssaamm
Posts: 125
Joined: June 4th, 2010, 9:43 pm

Re: Bounding box

Post by ssaamm » February 10th, 2011, 6:20 pm

Well, I think that the problem can be solved using a CA.

I think a CA in which all cells put out orthagonal-moving cells that leave a trail, and then the trails would "solidify" when it hit another trail or solid structure, and destroy unnecessary material around it. When it was all done, a special type of cell could be put in that would change the state of all cells and destroy all material except the solid stuff, which would show via the population count how many cell the polyomino has.

Just what I'm imagining, it might not actually be the best way to do it.

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Bounding box

Post by 137ben » February 10th, 2011, 6:38 pm

Code: Select all

Well, I think that the problem can be solved using a CA.

I think a CA in which all cells put out orthagonal-moving cells that leave a trail, and then the trails would "solidify" when it hit another trail or solid structure, and destroy unnecessary material around it. When it was all done, a special type of cell could be put in that would change the state of all cells and destroy all material except the solid stuff, which would show via the population count how many cell the polyomino has.

Just what I'm imagining, it might not actually be the best way to do it.
Probably not the best way, as the CA would still need to be simulated by a practical computer, rather than simply having the practical computer perform the computation itself.

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: Bounding box

Post by Mats » February 26th, 2011, 5:48 am

The problem with the Bounding box concept seems to be that the size appears too large for patterns that are mainly spread diagonally. That is if size is measured as the area of the bounding box. But the area is not the only way to measure size. Any function with the property:

f(box1) > f(box2) and f(box2) > f(box3) implies f(box1) > f(box3)

can be used as a measure of the size of a Bounding box.

Instead of using the area of a Bounding octagon or Bounding polyeder I suggest that the size of a Bounding box is measured not by area but by a method based on the maximum Chebyshev distance of the Bounding box, since Chebyshev distance seems to be a natural way of measuring distances i CGoL.

The way I suggest is pretty simple. First, an m by n box is equal in size to an n by m box so for simplicity I will from now on assume m >= n.

Definition: A Bounding box m1 by n1 is larger than a Bounding box m2 by m2 by n2 iff
m1 > m2
or
m1 = m2 and n1 > n2

The list of Bonding boxes sorted by size this way will be:
1 by 1
2 by 1
2 by 2
3 by 1
3 by 2
3 by 3
4 by 1
4 by 2
4 by 3
4 by 4
5 by 1
...

If you want the size of a Bounding box to be represented by a number it can be calculated as:

s(m,n) = (m^2 - m)/2 + n

Exapmle: A 6 by 3 Bounding box gets size number 18, calculated as (6^2-6)/2 + 3 = 30/2 + 3 = 18

If you know the size number, s, and want to know m and n they can be calculated as:
m is the integer closest to sqrt(2m)
(or m = int(sqrt(2m) + 0.5) where int(x) is the largest integer <= x)
and
n = s - (m^2 - m)/2

Example: Bounding box number 100 is the 14 by 9 Bounding box since sqrt(200) = 14.1421... which gives m = 14, and n = 100 - (14^2-14)/2 = 9.

Post Reply