Suggestion: for rotation or translation fixed

[Playit3110]

change of view
instead of thinking about the cubes as structure, think about a mash of edges and node (group theory?). Each node is the center of a cube and each edge is the next bordering cube. In the following ideas only the nodes are used to identify a cube and in the translation fixed idea the edges are possible paths.

1. Rotation fixed
   For a rotation fixed storage, it would be an idea to store the location in polar coordinates, because the radius would always be the same without the need to know the rotation. Important is only which point you use as center. Otherwise it gets pretty complicated to get unique radii for different cubes. All radii always give the same formation of cubes independent of rotation and the same hash as well.

2. Translation fixed
   For a translation fixed storage it would be like a turtle game. Start with the turtle at some corner cube and tell it the move to the next cube. Important is, that cubes, which are only neighbour of one other cube, are the start or the end or, if both not possible, some predefined path is used. to the next cube. This way it is not important where the combination of cubes is. because the path is always the same and the hash of it as well.

[Playit3110]

Also a question: is there a limitation for structures? Like is a cube formation like a 3x3x3 cube with the center cube missing valid? Or is a filled structure needed?

[SscSPs]

for your question, yes, i think its valid, all structures are valid as long as each and every cube is touching some other cube(at least 1) with a face

[Playit3110]

Also an idea: just store the radius and the direction. like a vector and prioritize alpha direction over beta direction. so you get standardized structure. then you have only 6 rotations to make by just adding 90*n degrees to alpha and/or beta. You have six directions you can rotate the cubes. Only the center is important again. I would say the center of mass would be the best center, because it is independent of the coordinate axes and rotations.

[AlreadyTakenJonas]

I had a similiar idea. I have some experience with theoretical chemistry, which often deals with translation and** rotation free coordinate systems. One way this is usually solved in chemistry is a z-matrix. This is a way of defining your coordinate system based on the actual points of interest in your coordinate system.

I haven't put much thought into the actual data structure to put this in memory so let's just go with a nx3-matrix, where n is the number of cubes, for the sake of argument. Here's how I'd adapt it to the cubes problem:

1. Every row of our matrix contains one cube with three coordinates. Switching the rows does not affect the structure.
2. The first cube has always the coordinates (0,0,0).
3. The second cube has always the coordinates (1,0,0). This definition is of course arbitrary, but it defines one dimension of our cube-structure-internal coordinate system. Translating or rotating the structure in the external cartesian coordinate won't change this. Switching columns also does not affect the shape, because we're changing the definition of our coordinate system in the same way.
4. The first cube orthogonal to the first two cubes is (0,1,0). This limitation eliminates some duplicate notations that represent the same structure. For example: you could define an L-shape as

0 0 0          0 0 0
1 0 0   or   1 0 0
2 0 0          2 0 0
2 1 0          0 1 0

. Both yield the same shape.
This also causes the first cube to always be a corner, if the structure is more than one dimensional, but that does not prevents us from defining all possible structures, because we define the first cube arbitrarily.
5. Cubes with non-zero values in the third column are orthogonal to the first the previously defined plane. The first orthogonal cube does not have to be (0,0,1), because this would actually prevent us from generating all possible structures, e.g. structures where all cubes have less than three neighbours.

I think it should be relatively easy to generate all possible structures systematically, if you build them row by row and only insert valid rows (rows defining a cube attached to an already existing cube). A valid row can be generated from an already existing row by copying it and adding/subtracting 1 from one of the three columns. @SscSPs, this ensures all cubes are touching each other. This might get trickier for larger structures, because you'd have to check for colliding cubes. Haven't thought about that part yet.

@Playit3110 The origin of this coordinate system is not the center of mass and that's a good thing, because we don't know the center of mass before generating the cube. So we'd have to generate the structure, find the center of mass and then define our rotation & translation free coordinate system.

One thing to keep in mind: This coordinate system still distinguishes between enantiomers. Enantiomers are two structures, that are mirror images of each other. They might look the same at first glance, but you can't transform one into the other by rotating it.

I'm not sure about meso-forms, though. Haven't looked into that yet. Meso-forms are enantiomers, that have a plane of reflection inside the structure destroying the mirror-image-property. These structures can be transformed into each other by rotation and are actually the same structure. Not sure, if this coordinate system would allow non-unique definitions of these.

I'm not 100% sure that this is defines all possible structures uniquely, but I was already in bed and about to sleep when I started coming up with this and I had to write this down so... Maybe we need to check that as well? Or just make sure we create only unique structures by generating them systematically. I'm not sure.

One last idea I had was how to hash the coordinates. For hashing the structure we can take the columnwise sumes and interpret them as digits of a single number. This would match identical structures even when rows are switched. This fells like a to easy solution, but I was not able to come up with examples that hash collisions of valid structures. Which does not necessarily mean there are none, but I planned on going to bed like 3 hours ago before I fell into the youtube-rabit-hole, so that's all I have so far.

Good night and thanks for the great video @mikepound! Always a good day when your uploading!

[Playit3110]

I wish you also a good night. Only the hashing has the collision of sums, because 1 + 0 + 1 = 1 + 1 + 0 = 0 + 1 + 1 so it would make different shapes the same.

My question @AlreadyTakenJonas is, what is the first cube and how can it be defined independently?

[drewctaylor]

I think I've been taking an approach similar to @AlreadyTakenJonas, which I think, in the 2D case, produces a representation of the polyomino that is the same regardless of rotation or translation (but not reflection).

Represent the squares to points in space. For example, for an L-tetromino, imagine the point is the center of the square, and represent it as the points (0, 0), (0, 1), (0, 2), and (1, 0).

Identify the center of the smallest circle that encompasses those points. For any set of points, there is exactly one smallest circle. In the case of the L-tetromino above, the center of the circle would be at (1, 1.5) with a radius of around 1.1.

Identify the vector from the center of the smallest circle to the nearest point. In the case of the L-tetromino above, it would be a vector from the center of the circle (1, 1.5) to the square at (0, 1).

Represent each square as a distance from the center of the smallest circle and the angle from that vector. In the case of the L-tetromino, it would be (.5, 0 deg), (1.1, 63 deg), (1.1, 117 deg), (1.1, 297 degrees).

Represent the polyomino as the set of the representations of the squares. No matter how you rotate or translate the L-tetromino, it should have the same representation.

There are some issues:

• There may be more than one point nearest to the center of the smallest circle. In that case, I think you could use the center of the arc defined by those points.

• It doesn't handle reflections. That said, I wonder if taking the clockwise angle from the vector might not give it to you; the L-tetromino reflection might be (.5, 0 deg), (1.1 63 deg), (1.1, 243 deg), (1.1, 297 deg).

• I haven't figured out if it would work in 3D. I think you'd need to pick a second vector (maybe the second nearest point?) to define a plane, then define the cubes in terms of the distance from the center, the angle from the first vector in the plane, and the distance from the plane.

EDIT: After I implemented the "smallest circle" algorithm (lol, of course), I realized that because of the limitations on the points (centers of the polyominoes) and the limitations on the rotations (some multiple of 90 degrees), it's simply going to be the center of the rectangle that bounds the points, which I suspect is simpler to compute.

[AlreadyTakenJonas]

I wish you also a good night. Only the hashing has the collision of sums, because 1 + 0 + 1 = 1 + 1 + 0 = 0 + 1 + 1 so it would make different shapes the same.

My question @AlreadyTakenJonas is, what is the first cube and how can it be defined independently?

The first cube has always the coordinates 0 0 0, because we define the coordinates of a give cube based on the cubes defines previously. That's what I meant by that.

[AlreadyTakenJonas]

I think I've been taking an approach similar to @AlreadyTakenJonas, which I think, in the 2D case, produces a representation of the polyomino that is the same regardless of rotation or translation (but not reflection).

Represent the squares to points in space. For example, for an L-tetromino, imagine the point is the center of the square, and represent it as the points (0, 0), (0, 1), (0, 2), and (1, 0).

Identify the center of the smallest circle that encompasses those points. For any set of points, there is exactly one smallest circle. In the case of the L-tetromino above, the center of the circle would be at (1, 1.5) with a radius of around 1.1.

Identify the vector from the center of the smallest circle to the nearest point. In the case of the L-tetromino above, it would be a vector from the center of the circle (1, 1.5) to the square at (0, 1).

Represent each square as a distance from the center of the smallest circle and the angle from that vector. In the case of the L-tetromino, it would be (.5, 0 deg), (1.1, 63 deg), (1.1, 117 deg), (1.1, 297 degrees).

Represent the polyomino as the set of the representations of the squares. No matter how you rotate or translate the L-tetromino, it should have the same representation.

There are some issues:

* There may be more than one point nearest to the center of the smallest circle. In that case, I think you could use the center of the arc defined by those points.

* It doesn't handle reflections. That said, I wonder if taking the clockwise angle from the vector might not give it to you; the L-tetromino reflection might be (.5, 0 deg), (1.1 63 deg), (1.1, 243 deg), (1.1, 297 deg).

* I haven't figured out if it would work in 3D. I think you'd need to pick a second vector (maybe the second nearest point?) to define a plane, then define the cubes in terms of the distance from the center, the angle from the first vector in the plane, and the distance from the plane.

EDIT: After I implemented the "smallest circle" algorithm (lol, of course), I realized that because of the limitations on the points (centers of the polyominoes) and the limitations on the rotations (some multiple of 90 degrees), it's simply going to be the center of the rectangle that bounds the points, which I suspect is simpler to compute.

That sounds like a good idea, although you need to keep gimbal lock for the 3D case in mind. You can't define unique coordinates in 3D space via two angles and a radius, because you lose a degree of freedom for certain rotation angles. But it should be possible by doing something similiar to Arvo's fast random rotation matrices, he defines one angle and one planes of reflection. He substitutes one rotation by a reflection at two perpendicular planes (the defined plane and the plane perpendicular to it); two reflections give you essentially a rotation (see householder transformation), but avoids the gimbal lock problem. Took me a week to find this out, when I had issues with gimbal lock without even knowing it...

[Playit3110]

I wish you also a good night. Only the hashing has the collision of sums, because 1 + 0 + 1 = 1 + 1 + 0 = 0 + 1 + 1 so it would make different shapes the same.

My question @AlreadyTakenJonas is, what is the first cube and how can it be defined independently?

The first cube has always the coordinates 0 0 0, because we define the coordinates of a give cube based on the cubes defines previously. That's what I meant by that.

Ok, but what is the first cube.
For example we have:

0 1
1 1

Which one of the three is the first one?
a) bottom left
b) bottom right
c) top right

I understand that the first cube has coordinates (0, 0, 0), and (0, 0, 0) is the first cube, but it doesn't define which one is the reference cube (0, 0, 0). I hope I could clear up my question.

[AlreadyTakenJonas]

I wish you also a good night. Only the hashing has the collision of sums, because 1 + 0 + 1 = 1 + 1 + 0 = 0 + 1 + 1 so it would make different shapes the same.
My question @AlreadyTakenJonas is, what is the first cube and how can it be defined independently?

The first cube has always the coordinates 0 0 0, because we define the coordinates of a give cube based on the cubes defines previously. That's what I meant by that.

Ok, but what is the first cube. For example we have:

0 1
1 1

Which one of the three is the first one? a) bottom left b) bottom right c) top right

I understand that the first cube has coordinates (0, 0, 0), and (0, 0, 0) is the first cube, but it doesn't define which one is the reference cube (0, 0, 0). I hope I could clear up my question.

If you give me a whole structure, you can pick any one to be the first. This will yield different representations for the same structure. But I think you can generate unique representations, when you generate the structures in my proposed coordinate system from scratch and completely ignore the cartesian space.