Suggestion for cannonical representation

[BartTerpstra]

Suggestion for cannonical representation

[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