Bounding box

[ssaamm]

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?

[Mats]

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?

[calcyman]

The idea of a bounding octagon has already been proposed:

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.

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...

[137ben]

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.

[ssaamm]

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]

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).

[ssaamm]

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]

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.

[ssaamm]

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]

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.

[Mats]

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.