Four Color Theorem in Grasshopper

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 :slight_smile:

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.

3 Likes

Cool to see other experiments. The question of @SpatialSojourner was a good one :tada:

The forest fire method is quite robust. I added some new tesselations to test.
Gilbert tesselation


Here a pentagonal one
With 4 colors it works well

But for 3 colors it din’t find the repetive pattern.

Using Galapagos is quite effective to find the seed that lead to color all faces. Here with a voronoi with 1000 points.

I think also that this tool could be used to weave, to find some “roads” … TBC

3 Likes

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 :

  1. Face-Face topology so it could be brep topology or mesh topology or whatever…
  2. Seed : a seed that is useful to change the patterns
  3. A number of color wanted (lowest possible =2), but with autonoumous mode the number of color will be augmented if no solutions found
  4. nextColorNotRandom, if true the next color choosen is not a random one but the lowest color number possible
  5. 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



Pentagons is now OK with 3 colors

Hope it is clear and useful.

nColors_Legacy.gh (260.2 KB)

10 Likes

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)

9 Likes

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 :fire:

1 Like

Gilbert tessellations script is here

1 Like

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#??

There are many discussions of that on this forum. Can you be more specific?

Hello everyone,
I am trying to do something similar. to be precise ,’ voxelizing a geometry in checkerboard pattern’ I did something in grasshopper, but its not a neat method. what I have in mind is something similar to cellular automata that do a checker board pattern of voxels in given mesh. I am attaching my script and algorithm. It would be great if any of you could help me. Thank you

Voxelized geometries 05112020.gh (21.7 KB)

1 Like

hello
you could use the script as it is. You just have to make a script that gives the topology connexions you want. FF is a datatree containing for each object (say i from 0 to 999) the connections with others objects index (a list of index from 0 to 999, but not containing i).
With this method you’ll be able to adapt the connectivity (one point, one edge, one face …)

Hope it helps.
If not, post just the geometry you have (not everybody as Voxelizer plugin, I haven’t)

Hello Laurent, Thank you for your reply.
I did not understand it really. sorry. I understand that your script gives face connectivity. but how to use it to make checkerboard pattern? i am attaching new script with the voxelized geometry. Thankyou
Voxelized geometries 05112020GHFORUM.gh (5.8 MB)

Hello
For just “simple” case as checkerboard pattern you just need Maths in your case.
I use a Modulo of 2 in order to have just 0 or 1 depending on the sum of index (x+y+z)%2 of the cubes. You must do that when cubes are well ordered.
You could also do other pattern depending on the equation.


Voxelized geometries 05112020GHFORUM.gh (5.8 MB)

2 Likes

Amazing. thank you verymuch!