Thanks to warmCabin for making these movies. They have been a lot of fun!
Back when the first movie came out, I spent a little time playing around with a different idea for adjacency testing using a Voronoi-inspired approach. Eventually I decided that it was pretty good, in my opinion. But this was some weeks after publication, and I felt like maybe the movie's moment had passed, so I didn't bother posting it. But now I'm taking this new movie as an opportunity to write up my suggestion with some examples. I hope that folks find it interesting, and maybe worth using as a standard for future runs. Hopefully my explanation is okay. Let me know if you have questions about it.
Here's the short explanation:
1. Consider each colorable pixel as a point in a
Voronoi diagram.
2. Draw the boundary lines of the Voronoi diagram.
3. Consolidate Voronoi areas that share the same colorable regions into a single region.
4. Observe which consolidated regions share a border. These are considered adjacent. (Regions that share only a corner are not considered adjacent.)
If you aren't familiar and don't want to read the wikipedia article, I would say that a Voronoi diagram shows which regions of a plane are closest to each of the initial points. Boundary lines in a Voronoi diagram indicate places that are equidistant to two or more of the initial points.
Sorry, inline images aren't working for me? I've turned them into normal links for now.
Here's an example of the whole adjacency process for a sample region.
0. Let's work with #11, Crested Duckbill, near the eyeball area.
http://ehall.freeshell.org/dinosaur/11%20-%20focus%20area.png
1. Mark a point for each colorable pixel in the part of the image we're investigating.
http://ehall.freeshell.org/dinosaur/11%20-%20points%20only.png
2. Make a Voronoi diagram using these points.
http://ehall.freeshell.org/dinosaur/11%20-%20all%20lines.png
3. Consolidate the regions that belong to the same colorable area.
http://ehall.freeshell.org/dinosaur/11%20-%200%202%2020%2021%2022%2023.png
4. Observe that regions 0 and 23 share a boundary. They are adjacent. Regions 21 and 22 only share a corner. They are not adjacent.
Here are some more examples. Keep in mind that I put these together manually, so if I put any pixels in the wrong place, then the conclusions could be incorrect.
#1, Stegosaurus toenails. Regions 51 and 53 are adjacent. Regions 0 and 52 are not adjacent.
http://ehall.freeshell.org/dinosaur/01.png
http://ehall.freeshell.org/dinosaur/01%20-%200%2041%2051%2052%2053.png
#13, Mini stegosaurus back plates. Regions 0 and 2 are not adjacent. Regions 18 and 20 are not adjacent.
http://ehall.freeshell.org/dinosaur/13.png
http://ehall.freeshell.org/dinosaur/13%20-%200%202%2018%2020.png
#14, Mighty T-Rex eyeball. Regions 0 and 27 are not adjacent. Regions 1 and 27 are adjacent.
http://ehall.freeshell.org/dinosaur/14.png
http://ehall.freeshell.org/dinosaur/14%20-%200%201%2026%2027.png
It should be possible to write an algorithm to test every region using this approach, without manually making Voronoi diagrams and looking at them, but I never got that far. If you're interested in manually making Voronoi diagrams, I used
Desmos Voronoi Diagram to make the example images in this post. I manually typed in each of the pixel coordinates, and then cleaned up the images in Krita. I don't recommend it, but it worked well enough for a proof of concept.
