Hello,
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.
FourColors.gh (20.4 KB)
I appreciate any help!
Hello,
it was not a so simple problem but it was interesting. I struggle a bit but here is a solution (I hope 
).
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.
Hello
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)
Happy coloring.
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
Quote:
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.
A new version with specified number of colors. This script affect an index color at each face, if it is not possible the index is equal to -1.
Here some examples with differents polygons.
BTW: For the 4 color clustering thingy use FF connectivity (either implicit via joining breps or explicit) and some recursion (it works):
Hello Peter
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%.
It’s a matter of asking the right question.
Wrong (grey means bad things)
Right:
I’ll test some stuff (maybe //) in order to greatly accelerate the result (big N of regions: say 1K and up) and I’ll post the C# here when ready.
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 
Edit:
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.
Cool to see other experiments. The question of @SpatialSojourner was a good one 
The forest fire method is quite robust. I added some new tesselations to test.
Gilbert tesselation
I think also that this tool could be used to weave, to find some “roads” … TBC
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).
IM dollar idea: can we just stay on 2 colors? Who’s gonna notice it?
And what about one color? Less is more after all.
Moral: Porca Miseria (TBC)
Hey people,
If I understand it the right way this problem can be solved using the “WelshPowell”-Algorithm. Wihich isn’t that hard to implement.
I have done so within this plugin (QEDS)
A file (01_Conversion>FromLines) from the examples gives the following result.
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.
That algo works when it works. For voronoi type of regions it fails to deliver the goods
Here’s the thing (In fact the main Method of the thing):
Here’s another Method (don’t ask what it is):
Moral (and current status of things performance wise) : Porca Miseria
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 :
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
Hope it is clear and useful.
nColors_Legacy.gh (260.2 KB)
Good algorithm.
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.
nColors_Legacy_2.gh (264.8 KB)
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 
Gilbert tessellations script is here
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.
How do i do a custom C#??
