Suggestion for cannonical representation

[BartTerpstra]

Hello All,

I am a amateur mathmatician who got interested by the puzzle.

What we are looking for is a way to generate all extensions of the previous unique shapes required to have generated all unique shapes of the next size.
OR
To generate all combinations of cubes required to have generated all unique shapes of a given size.

The hardest part of the problem is having to do a "contains" operation on the set of all currently found unique shapes, as it requires an expensive comparison N times, where N is the amount of shapes already found.

It would be nice if we could have a relatively cheap operation that turned a shape into it's canonical form and put it into an ordered table/hashtable, which would be an existence table/frequency table initialized at 0. saving us from ~N^N expensive operations.

We need a measure independent of rotation and translation, as all we care about is shape.

So, what if we could find a cube as a starting point in a way based on shape, rather than specifics, and then use that cube as a root node and then generate a tree structure as if it would be generated from the root cube?

If this tree structure can always be generated and always returns the same canonical form, it is a useful canonical function.

Selecting this cube might be done by finding the closest cube to the "center of mass"+ a function to generate "Up" and "Left" to be able to create an unambiguous tree structure.

Up and Left could be generated from the center of mass stat if it is biased from the true center of a cube.
If the center of mass is on a center plane of a cube, you need another exemption or full check.
If the center of mass is dead center, you need a full check.

This solution can be executed perfectly parallel.

My question to the more experienced:
How expensive is a center of mass calculation? If you work of previous data, you might you be able to fudge mass calculations.

What have I misunderstood about the complexity of the problem?
Because it feels like my suggestion is different from others, so i must have misunderstood something. Maybe center of mass is really expensive.

I look forward to your replies.

[Playit3110]

In the original repo i had a simular idea, where i would use radii and angles to define the location of single cubes. I also said that the center of mass would be an idea, because it doesnt change after rotations.

It is a bit more difficult to first calculate a center of mass instead of using some other point as center of the coordinates but should be pretty easy if you think of the cubes as 1 weight unit it is easy to find where to but the bar to balance it.

Issue

[Quasido]

I was thinking a similar thing but would have started from the least dense point / an extremity. As I understand it, if I a shape has one point that has different "densities / weightings" to the others than you can easily check it's not a square/loop.

[nsch0e]

Center of Mass should be relatively easy to compute: just add all coordinates of ones (there should be N) and divide by N (number of cubes in polycube).

Your idea is close to what I am thinking about. I stumbled upon Hu Moments which describe a 2d shape regardless of translation and rotation. I did not search for an 3d formulation yet.

Another idea was Principle Component Analysis (PCA) which perhaps is a bit overkill but should allow for unique representation.

[BartTerpstra]

Right, that is just center of mass, that's quite cheap.
So it's a canon function for lopsided shapes, and at the very least you can narrow down the remaining cubes in 4(?) separate groups that are mutually exclusive groups, the symmetries of weight.
No symmetry, single rotation symmetry, 2 rotations symmetry and full symmetry?
in a body: none.
on a plane: one.
on an edge: two.
on a corner or center: three/all.

I wonder what the distribution of these groups is as N increases.
I feel like lopsided shapes should become a larger group than the symmetrical groups.

[BartTerpstra]

No wait, there is something inconsistent there.
I'll do some more thinking before posting again.
Disregard that definition of what the symmetries are.

[Playit3110]

on a corner or center: three/all.

Corner or center is not complete because the symmetry could also be in other points.

[BartTerpstra]

If the center of mass is in the center of a cube or a corner, you can not determine anything about the canonical orientation, and can not construct the canonical form, given the current description of the function. You don't know up and you don't know left. you can combine these to know the full orientation.

If it's on the center of a face, you can agree this face was facing up or down.
If it's in a corner of a face, you can agree that it's the upper left corner + up or bottom right + down.
If it's inside the cube, you can say that direction is up, left and forward.

By symmetry i meant, how many different degrees of freedom are still ambiguous about the orientation.

[nsch0e]

Perhaps I'm oversimplifying things, but the general goal is to always select one of the 24 rotations to identify the set of 24, am I right?

In my C++ implementation I never use the voxel representation (where we set ones in a bigger array of zeros). I only use the coordinates of the ones. Here a simple 2D example

Voxel:

# y
# 0 1 2
[[1 1 1]  # 0  x
 [0 0 1]] # 1

Coordinates:

# x y
[[0 0]
 [0 1]
 [0 2]
 [1 2]]

The coordinate rep. should always be sorted, so it is unique for this formation. When we rotate the formation and get the coordinate rep for all of them, we can simply sort all reps by comparing element-wise in the list.

Now we only have to select the first or last rep and it should be always the same one, regardless of the starting orientation.

Since symmetries end up with exactly the same representation we don't have to account for them and in practice we don't have to sort the whole list but just remember the lowest/highest one while generating.

Please correct me if I'm wrong.

[nsch0e]

Another idea: first sort by shape (alias bounding box), so shape[0] <= shape[1] <= shape[2]. When we enforce this we can eliminate rotations before executing them.

[ClaasF]

Since symmetries end up with exactly the same representation we don't have to account for them and in practice we don't have to sort the whole list but just remember the lowest/highest one while generating.

Please correct me if I'm wrong.

Maybe I'm thinking wrong here, but aren't the indizes dependent on the orientation? A 2x2 matrix with a single 1 could be have (1,0), (1,1), (0,1) or (0,0) as coordinates for the same cube.

What your encoding accounts for rather well is if the same polycube can be reached via two different routes from different base cubes. That is, an E shape can be reached from an F shape and a C shape by adding a single cube.

[nsch0e]

Maybe I'm thinking wrong here, but aren't the indizes dependent on the orientation? A 2x2 matrix with a single 1 could be have (1,0), (1,1), (0,1) or (0,0) as coordinates for the same cube.

That's the point: for each orientation there is a different representation as you describe. Now we want to choose one rep. so we compare them:
(0,0) < (0,1) <(1,0) < (1,1) if we order first by x then y [ then z]

so for your example we would always choose (0,0) as our rep.

ps: the example would never occur because we always crop so there are no rows/cols with only 0s.

[ClaasF]

So, you still want to do all the rotations and then take the "smallest" one? If that's the case, I proposed a similar solution in another issue (that didn't work as expected, though).

[nsch0e]

yes, you would have to calculate them all. But if we incorporated the second idea, we could skip rotations if the shape doesn't follow our rules. Also rotation on this rep shouldn't be that compute intensive.

[NailLegProcessorDivide]

I haven't done any profiling yet but I enforce shape.X >= shape.Y >= shape.Z and then minimum value to restrict both how the polycubes grow and rotate. it seems to work reasonably well but I've only compared it to the original python version so far which is extremely slow.

This means that X != Y != Z only checks 4 rotations, X == Y != Z or X != Y == Z needs 8 rotations and finally X == Y == Z needs the full 24.

[NailLegProcessorDivide]

A potential up to 50% improvement for encoding space I havent seen mentioned yet would be to canonicalise mirrors as the shape itself and then search the set at the end for asymmetrical shapes and just double counting them but I think someone would need to measure to see if this could be a meaningful improvement