Open presseyt opened 1 year ago
Hi @presseyt sorry for taking so long to get back to you on this, this is interesting and I'm happy to merge if you agree to license this code under the MIT license which we have added since you first raised your pull request. if you would prefer not to use MIT please include a relevant license in your PR.
This is currently an order of magnitude faster than python and an order of magnitude slower than c++. I wanted to make a PR to highlight some (possibly) new ideas.
New Canonical Encoding
Given a root cube and an orientation, we can encode a cube by its adjacency graph. I'll illustrate my method by encoding this polycube with 5 cubes.
We choose a cube (
cube #0
) and the orientation [Left Right Up Down Forward Back]. Record the adjacent cubes tocube #0
as six bits:We add any adjacent cubes to our cube order. We have marked
cube #1
. We can now repeat the process forcube #1
:There are two new adjacent cubes. They are added to our list of cubes in the same order as our orientation (in this case, first Left, then Right, Up, Down, Forward and Back. This would be different if we picked a different orientation). We now repeat the process for
cube #2
:At this point we have completely ordered our cubes. Any additional bits would be redundant. We finish our encoding with six 0 bits.
Define the canonical representation of a cube to be the maximum represention over all choices of first cube and orientation.
This was encoded by choosing the middle cube to be
cube #0
- this is the only cube that can be encoded with three ones at the beginning of its adjacency graph, so we do not need to consider any other cubes as root. The representation was maxed when we chose the orientation RLBFDU.When we parse this representation, we do not know the orientation it was encoded with, so we will get the same cube in (possibly) a different orientation.
Note that this canonical representation gives a unique ordering of the cubes, and the cubes are in increasing distance from the root cube.
So we can take away the last cube, leaving a connected polycube. This gives a well-defined manner of assigning a polycube with n-1 cubes to a given polycube with n cubes.
This allows us to not use a hash table and parallelize computation as in issue #11.
I know other people have already implemented ways of getting rid of a hash table, or splitting computation computation by the dimensions of the polycube. (see issue #27 and PR #26 and #28). These people are much better coders than me, and I haven't had the time to fully read through everything that has been done, but hopefully this is an interesting way of looking at the problem. It's been a lot of fun coding a proof of concept even if I know a javascript implementation isn't going to go anywhere ;)