I’ve created a script that takes a surface that is divided up and randomly dispatchs them into 4 groups. I was wondering how I could take it further and have the 4 separate groups never border another from the same group like the four color theorem. IE: a red tile would never border another red tile.
It uses a custom C# to do the recursion, I begin to assign a color to a face, get the adjacent not colorized, choose one colorize it depending on neighbour …
You need a Sandbox that is used to get the topology of Brep.
Wow, that’s amazing! I was thinking that there would be a plugin. I like patterning using Lunchbox and when I slide through random seeds, there’s sometimes awkward clumping and that made me think of the Four Color Theorem. How can the items be split out? It worked perfectly with the Lunchbox paneling but I tried it with a Voronoi and there was an error.
indeed there was many bugs, but the logic I choose has also a flaw in my algorithm because with Voronoi it doesn’t allow just 4 colors. So when I can’t I put an index = -7 (there is no logic here 4 must be better) .
Here I colorize in White the cell with problem
Some add in the implementation, still need to play with seed if there are some white cells. With 300 Voronoi cells there is 25 % of case with some bad coloring. FourColors_Legacy.gh (35.5 KB)
And I discovered the Animation menu in Slider, I neither used it since so many years !!!
I came across this article online which describes a simple polynomial-time algorithm for a five coloring of a graph, apparently far simpler than general four-coloring algorithm (which seems to be NP-hard and very complicated) http://www.devx.com/dotnet/Article/32927
In theory you could write a program to examine a map and use the 1,476 special cases to find a four-color solution, but the resulting program would be long, complicated, and impossibly hard to debug. It would probably also be fairly slow.
Despite the problems involved in writing a program to color a map in four colors, it’s not too difficult to write one that colors a map with five colors. Unless you have a strange monitor that can display only four colors at a time, five-coloring should be good enough for most applications.
indeed I used face face connectivity it works most of the time. But with Voronoi and 4 colors it fails sometime I lower the percentage of fail by choosing new face to color which touched a maximum of already colored faces. But that’s not 100%.
Just for fun (been dealing with combinatorial algorithms recently), here is a really inefficient method of N-colouring a graph based on ‘dumb’ genetic combination rules:
(video sped up 2x)
The advantage with genetics is that you require practically zero insight into the theory behind graph colouring - just let it loose and it will eventually converge on a solution
Hmm, that doesn’t work out too well for highly regular structures like the hex grid: the algorithm just ends up oscillating around local minima forever, forming these crystal defect-like boundaries.
There’s a probability for this to become the most challenging thread of all times (performance wise). Beats Hanoi Towers by a factor of 100.
My current (a bit miserable) status: Since the right question yields 100% right results but takes a year and a half to finish (backwards recursion) for random valence region collections as shown (see info panel on top for max valence) > C# is rejected as stupid and pointless > new Plan B > variable clustering (N of colors in this occasion) > hope dies last > needs 3 milliseconds to solve the puzzle (~ 500 random regions) … but …well … there’s some failures in the menu (life sucks).
Normaly the algorithm tries to find a color for neighbouring faces, where two faces are neighbours if they share a common edge. I added an option (respect duality) to define that two faces are neighbours if the share an edge OR a vertex.
Here a new version of n Color of faces with non similar color for adjacent faces. I add some improvements. And it seems to give good agreement for most of the uses. it no more uses SandBox.
So the script needs :
Face-Face topology so it could be brep topology or mesh topology or whatever…
Seed : a seed that is useful to change the patterns
A number of color wanted (lowest possible =2), but with autonoumous mode the number of color will be augmented if no solutions found
nextColorNotRandom, if true the next color choosen is not a random one but the lowest color number possible
if autonomous set to true, the script try to find the best solution, augment the number of color if needed, change nextColorNotRandom if needed, could be stopped by using Escape touch.
I put some examples. All are solved in reasonable time. Time will surely be very long for a big number of faces or with things like a mesh cube.
The cube (here just 3 faces) is long if you ask for 2 colors, because it makes many tests with 2 colors. If you put 3 colors it is OK
I add/modify some changes in code to improve speed of execution => trying to avoid repetitive calculations where possible. Testing on 2000 faces shows aprox. 4 times faster code execution.
Some additional improvements can be done, but we leave that to somebody who needs this algorithm to be faster.
Wow, @laurent_delrieu@PeterFotiadis, you guys have come up with some really cool stuff… I walked away from my random pondering and come back to find some amazing responses. I’m going to have to take a look at these… the tesselation, pent, and vorinoi is
Forgot completely (blame advancing Alzheimer) that thread: I did at the time a working (?) solution for the 4 Vodka pints theorem (related with Tequila in fact) but what was the name of the C#? That’s the 1M question.