Solution-specific Visio Discussions > Artistic and Graphical Effects

Applying the Four Color Theorem in VISIO?

<< < (2/4) > >>

Bald Eagle:
An interesting, logical, step-wise process that could be implemented in code.

Looks like thing guy has whanged something together in JAVA.
Code available on SourceForge:
https://sourceforge.net/projects/maps-coloring/

JuneTheSecond:
Yacine knows well about Visio, and Bald Eagle knows well about 4-colors.
Y+B might be the best combination.

However I think Visio is not good tool, Visio cannot shortly find a couple of adjacent shapes.
For example in the case shown picture below, SpatialNeighbors and SpatialRelation could not find  correct couples. Red shape A has only 6 adjacent green shapes around A. But SpatialNeighbors and SpatialRelatio find 12 shapes around shape A with any of VisSpatialRelationCodes. 6 red shapes have to be removed. They are touching to shape A at a point. Any magic is required.

Bald Eagle:
Indeed, June, I hear what you are saying.
Although I'm unfamiliar with the Spatial functions you're using, I also never thought that there would be any native "Visio-only" functions which would be able to unravel this interesting problem that has such a long and complicated history.   It's "solution" is still a matter of conjecture.

I think that it's something that might require VB, and possibly even the daisy-chaining of several tools to get the job done.  Progress with one software package may shine a light on a path in another software package.

Perhaps the first line of attack is to puzzle out a way to identify if shapes are adjacent.
In POV-Ray, I could probably try to use something like TRACE which would tell me where the edge of an object is.
I'm wondering if there's a way to use the shape operations like difference to test if objects are next to each other.
If two "countries" border each other, and I change the size by 1.001, then there ought to be a remainder upon intersecting them.  Some sort of Boolean result if there's something generated or not. "is there a _new_ shape where there was not before?"
Perhaps there are examples to be learned from in basic video-game collision detection and newer particle systems.
That Visio Guy Chris Roth worked out his polyline generating sheet.  Can it be determined programmatically if one irregular polygon borders the other within a given range?  Less than some distance normal to the edge's curve?

Maybe there's a way to use the line connecting center pins of 2 shapes and see if the bounding box of all other shapes are between them.

June has a very disciplined mind, can see and understand the core of many problems, and has the artistic and technical skills and talent to address these things in beautiful ways.   I'm just a guy with a (donated) laptop and neurotic desire to play with math and science and computers   ;)
Y+B+J+ ... x+y+z  will likely be the "best" combination.
In any event, there's likely to be a lot of fun and exploration and invention, and fruitful discussion along the way.

Yacine:
So here's a proof of concept.
I implemented the 2 routines as previously described: 1) finding the borders, 2) coloring.

For the coloring I did use the first trivial idea that came in my mind:
for each shape on the page, if it is not colored, then check if its neighbors are and eliminate all the colors found, then take the first left color in the row.

In the 2 first examples it did not work perfectly, as it left some shapes (the black ones) without solution.
A backtracking algorithm could eliminate the problem.
Considering, that I did not use any "academic" algorithm at all, an already impressive result.

HOW TO USE?
Run the macro getNeighbors.

MIND:
Finding the neighbors was implemented with brute force - no intelligence involved and accordingly slow. Remove the doevents lines to increase the speed.
Play with the variable sqrSize for coarser or finer scanning results.

Enjoy and improve the code.
Cheers,
Y.

Yacine:
.