{"id":2459,"date":"2017-10-27T06:22:03","date_gmt":"2017-10-27T11:22:03","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=2459"},"modified":"2017-11-14T22:37:23","modified_gmt":"2017-11-15T03:37:23","slug":"color-your-world-more-with-maps-graphs-and-polygons","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2017\/10\/27\/color-your-world-more-with-maps-graphs-and-polygons\/","title":{"rendered":"Color Your World: More with Maps, Graphs, and Polygons"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Today, guest blogger Matt Tearle continues his investigation of the new <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/polyshape.html\"><tt>polyshape<\/tt><\/a> type (added in <a href=\"https:\/\/www.mathworks.com\/products\/new_products\/latest_features.html\">R2017b<\/a>) as a mapping tool.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#d3186d47-15db-44ac-bf98-e7e08b5dac7c\">Where were we?<\/a><\/li><li><a href=\"#74110fe4-49f5-4172-a295-f5a106a80e7f\">Start simple: a greedy coloring algorithm<\/a><\/li><li><a href=\"#795363ef-eff6-4acb-b1e7-e2bc8a8abdce\">Greed is good?<\/a><\/li><li><a href=\"#2791d9cb-5bea-47db-8f60-a691c654647c\">Adding a little intelligence (but with no guarantees)<\/a><\/li><li><a href=\"#bfa9ade3-6c6a-4dfc-82fd-ddc868c9bd00\">How far can this go?<\/a><\/li><\/ul><\/div><h4>Where were we?<a name=\"d3186d47-15db-44ac-bf98-e7e08b5dac7c\"><\/a><\/h4><p>In a <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=2456\">previous post<\/a>, I used the new <tt>polyshape<\/tt> variable type in MATLAB to determine connections between states. You can see the code in that post. I'll just load in the polygons and matrix of connections that came from that:<\/p><pre class=\"codeinput\">load <span class=\"string\">stateborders<\/span>\r\n\r\n<span class=\"comment\">% Make a graph of state connections<\/span>\r\nG = graph(border,stnames,<span class=\"string\">'lower'<\/span>);\r\n<span class=\"comment\">% Obtain centroid locations for states<\/span>\r\n[x,y] = centroid(p);\r\n<span class=\"comment\">% Plot map and connections<\/span>\r\nplot(p)\r\nhold <span class=\"string\">on<\/span>\r\nplot(G,<span class=\"string\">'XData'<\/span>,x,<span class=\"string\">'YData'<\/span>,y)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_01.png\" alt=\"\"> <p>Having made this nice visualization, it struck me that the colors from the default polygon <tt>plot<\/tt> weren't making a good map because neighboring states were often given the same color. The <tt>plot<\/tt> function, of course, doesn't know about the connections - it is just using a set of colors in the order of the polygons in the array. Using knowledge of the connections between states (stored in the matrix <tt>border<\/tt> and the graph <tt>G<\/tt>), I should be able to recolor the states so that no neighboring states have the same color.<\/p><h4>Start simple: a greedy coloring algorithm<a name=\"74110fe4-49f5-4172-a295-f5a106a80e7f\"><\/a><\/h4><p>Note that the actual color is arbitrary. The goal is actually to assign a number to each state. That number can then be used to index into a list of colors (or a colormap).<\/p><p>A simple (\"greedy\") algorithm to assign colors would be:<\/p><div><ol><li>state 1 is color 1<\/li><li>go through the states in order<\/li><li>for each state, find all the neighboring states<\/li><li>get the color values assigned to the neighboring states<\/li><li>assign the current state the smallest unused value<\/li><\/ol><\/div><p>In the last step, if colors 1 through <i>n<\/i> are used by neighbors, then the number of colors used in the map will grow to <i>n<\/i>+1. This means that the number of colors used for the whole map will depend on the connections and the order of the states. Let's see what happens if I apply this algorithm to the states in default (alphabetical) order.<\/p><pre class=\"codeinput\">n = length(p);\r\ncolor = zeros(n,1); <span class=\"comment\">% Initialize array to hold color numbering<\/span>\r\nnumcolors = 1; <span class=\"comment\">% Number of colors needed (so far)<\/span>\r\n<span class=\"keyword\">for<\/span> k = 1:n\r\n    idx = neighbors(G,k); <span class=\"comment\">% Get neighbors of the kth node<\/span>\r\n    idx = idx(idx &lt; k);   <span class=\"comment\">% But just those that have an assigned color<\/span>\r\n    neighborcolors = unique(color(idx)); <span class=\"comment\">% Get colors used by neighbors<\/span>\r\n    <span class=\"comment\">% Assign the smallest color value not used by the neighboring nodes<\/span>\r\n    thiscolor = min(setdiff(1:numcolors,neighborcolors));\r\n    <span class=\"comment\">% If there isn't one, add another color to the map<\/span>\r\n    <span class=\"keyword\">if<\/span> isempty(thiscolor)\r\n        numcolors = numcolors + 1;\r\n        thiscolor = numcolors;\r\n    <span class=\"keyword\">end<\/span>\r\n    color(k) = thiscolor;\r\n<span class=\"keyword\">end<\/span>\r\ndisp([num2str(numcolors),<span class=\"string\">' colors needed'<\/span>])\r\n<\/pre><pre class=\"codeoutput\">5 colors needed\r\n<\/pre><p>Five colors is actually common for many maps.<\/p><pre class=\"codeinput\">polygonplot(p,color)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_02.png\" alt=\"\"> <p>I'll be plotting the states with a custom color ordering a few times, so I figured it would make sense to make a short function to do that:<\/p><pre class=\"codeinput\">type(<span class=\"string\">'polygonplot'<\/span>)\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction polygonplot(p,color)\r\n% Get a list of colors (using the default plot colors)\r\nax = gca;\r\ncolors = ax.ColorOrder;\r\n% Plot the polygons and change their colors\r\nmap = plot(p);\r\nfor k = 1:length(p)\r\n    map(k).FaceColor = colors(color(k),:);\r\n    map(k).FaceAlpha = 0.8; % Make the shading darker\r\nend\r\n<\/pre><h4>Greed is good?<a name=\"795363ef-eff6-4acb-b1e7-e2bc8a8abdce\"><\/a><\/h4><p>Five colors is pretty good, but the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Four_color_theorem\">four color mapping theorem<\/a> states that you need only four colors to color any map so that no neighboring regions have the same color. However, in true pure math style, the theorem only says it <i>can<\/i> be done, not <i>how<\/i> to do it.<\/p><p>Is there an algorithm I can use to assign colors to the states to achieve a four-color map coloring? It turns out that this is a difficult problem in general. There are algorithms, but they are far more complicated than I want to deal with!<\/p><p>So instead, what about just shuffling the order of the states, then applying the greedy algorithm above? I took that code and turned it into a function that takes a graph as input and returns the color numbering and number of colors needed (equivalent to the max of the color numbering) as output.<\/p><p>Now I just need to shuffle the states and apply the function. But first, the matrix of connections is currently just the lower-triangular part. That structure will be ruined by the shuffling, so I'll make the full matrix version:<\/p><pre class=\"codeinput\">border = border + border';\r\n<\/pre><p>Now let's try shuffling and see how many colors we need:<\/p><pre class=\"codeinput\">rng(123)  <span class=\"comment\">% for reproducibility<\/span>\r\nidx = randperm(48);\r\nGperm = graph(border(idx,idx));\r\n[~,nc] = greedycolor(Gperm)\r\n<\/pre><pre class=\"codeoutput\">nc =\r\n     6\r\n<\/pre><p>OK, it's working, but that particular shuffle didn't help. It actually was worse. Well, that's random numbers for you. Maybe it's a good idea to see how the number of colors needed are distributed. Let's run the algorithm a bunch of times and see:<\/p><pre class=\"codeinput\">rng(123)\r\nnexp = 1000;\r\nnumcolors = zeros(nexp,1);\r\n<span class=\"keyword\">for<\/span> k = 1:nexp\r\n    idx = randperm(n);\r\n    Gperm = graph(border(idx,idx));\r\n    [~,numcolors(k)] = greedycolor(Gperm);\r\n<span class=\"keyword\">end<\/span>\r\nhistogram(numcolors)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_03.png\" alt=\"\"> <p>Interesting. Most of the time I get five, sometimes I need six, and about 5% of the time I do indeed get a valid 4-color mapping. So a simple way to get a 4-color mapping would be to try random permutations until only four colors were needed. A terrible algorithm? Perhaps. But I bet it works:<\/p><pre class=\"codeinput\">numcolors = Inf;\r\n<span class=\"keyword\">while<\/span> numcolors &gt; 4\r\n    idx = randperm(n);\r\n    Gperm = graph(border(idx,idx));\r\n    [color,numcolors] = greedycolor(Gperm);\r\n<span class=\"keyword\">end<\/span>\r\npolygonplot(p(idx),color)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_04.png\" alt=\"\"> <h4>Adding a little intelligence (but with no guarantees)<a name=\"2791d9cb-5bea-47db-8f60-a691c654647c\"><\/a><\/h4><p>Surely there's a better way, though. Right...? Well, maybe. I did encounter an algorithm for generating 5-color mappings. Basically, remove nodes from the graph one by one, until the nodes of the remaining graph all have degree greater than five. Then... do more stuff, which will color the remaining graph. Then you add the nodes back, coloring them as you go. I didn't really pay attention to the details because it seemed like there was a very good chance that you'd never get nodes with degree greater than five. Every time you remove a node, the degree of every node it's attached to goes down by one. So it seems like you could just try to repeatedly remove the lowest-degree node. Keep the list of nodes in order that you removed them, then use that (or, more precisely, the reverse of it, from last to first) as the ordering in which to color the nodes. It's not guaranteed to work, but it's probably not a bad option to try (and surely more efficient than random permutations). Also, this was for 5-color mappings, not 4, but let's just see what we get...<\/p><pre class=\"codeinput\">G = graph(border,stnames);\r\nidx = zeros(n,1);\r\n<span class=\"keyword\">for<\/span> j = 1:n\r\n    [~,k] = min(degree(G));\r\n    idx(j) = find(strcmp(G.Nodes.Name{k},stnames));\r\n    G = rmnode(G,k);\r\n<span class=\"keyword\">end<\/span>\r\nidx = flipud(idx);\r\nGperm = graph(border(idx,idx));\r\n[color,numcolors] = greedycolor(Gperm);\r\npolygonplot(p(idx),color)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_05.png\" alt=\"\"> <p>And just like that, I have a 4-color mapping for the US! In fact, it's not far from being a 3-color mapping! Only three states needed the fourth color. In fact, notice that this approach tries to use the lowest numbers as much as possible<\/p><pre class=\"codeinput\">histogram(color)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_06.png\" alt=\"\"> <p>But maybe I just got lucky. So let's try this on another map. Feeling brave, I found a world map shape file online. I applied the exact same approach: imported it with <tt>shaperead<\/tt>, converted the resulting structure array to a polygon array, used the \"pad-and-intersect\" method to build the graph of shared borders, sorted by iteratively removing the lowest-degree node, then applied the greedy coloring algorithm. The result...?<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/world4color.png\" alt=\"\"> <\/p><p>A 4-color world map! Just like that.<\/p><h4>How far can this go?<a name=\"bfa9ade3-6c6a-4dfc-82fd-ddc868c9bd00\"><\/a><\/h4><p>As I undertand it, real cartographers wouldn't have much use for my algorithm. There's a definite skew in the colors (e.g., all islands are color #1 because they have no borders), so the result isn't particularly aesthetically pleasing. Are there any amateur (or professional!) cartographers out there who want to try applying a \"real\" map-coloring algorithm using polygons and graphs? I'd love to see your results. I also know there must be maps that break my algorithm, but how well will the algorithm hold up with actual maps in practice, rather than deliberately pathological examples? If anyone has other polygonal maps they want to try coloring with this approach, I'd love to hear how it works.<\/p><p>And, of course, maps and graphs don't have to be just about physical geography - they can be abstractions of any number of things. If you have an application that could use map coloring for visualization, share your ideas in <a href=\"https:\/\/blogs.mathworks.com\/loren?p=2459#respond\">the comments<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_fbeab510094044b299cdd457c9c5fac7() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='fbeab510094044b299cdd457c9c5fac7 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' fbeab510094044b299cdd457c9c5fac7';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_fbeab510094044b299cdd457c9c5fac7()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2017b<br><\/p><\/div><!--\r\nfbeab510094044b299cdd457c9c5fac7 ##### SOURCE BEGIN #####\r\n%% Color Your World: More with Maps, Graphs, and Polygons\r\n%\r\n% Today, guest blogger Matt Tearle continues his investigation of the new\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/polyshape.html |polyshape|>\r\n% type (added in\r\n% <https:\/\/www.mathworks.com\/products\/new_products\/latest_features.html\r\n% R2017b>) as a mapping tool.\r\n\r\n%% Where were we?\r\n% In a <https:\/\/blogs.mathworks.com\/loren\/?p=2456 previous post>, I used\r\n% the new |polyshape| variable type in MATLAB to determine connections\r\n% between states. You can see the code in that post. I'll just load in the\r\n% polygons and matrix of connections that came from that:\r\n\r\nload stateborders\r\n\r\n% Make a graph of state connections\r\nG = graph(border,stnames,'lower');\r\n% Obtain centroid locations for states\r\n[x,y] = centroid(p);\r\n% Plot map and connections\r\nplot(p)\r\nhold on\r\nplot(G,'XData',x,'YData',y)\r\nhold off\r\n\r\n%%\r\n% Having made this nice visualization, it struck me that the colors from\r\n% the default polygon |plot| weren't making a good map because neighboring\r\n% states were often given the same color. The |plot| function, of course,\r\n% doesn't know about the connections - it is just using a set of colors in\r\n% the order of the polygons in the array. Using knowledge of the\r\n% connections between states (stored in the matrix |border| and the graph\r\n% |G|), I should be able to recolor the states so that no neighboring\r\n% states have the same color.\r\n\r\n%% Start simple: a greedy coloring algorithm\r\n% Note that the actual color is arbitrary. The goal is actually to assign a\r\n% number to each state. That number can then be used to index into a list\r\n% of colors (or a colormap).\r\n%\r\n% A simple (\"greedy\") algorithm to assign colors would be:\r\n%%\r\n% # state 1 is color 1\r\n% # go through the states in order\r\n% # for each state, find all the neighboring states\r\n% # get the color values assigned to the neighboring states\r\n% # assign the current state the smallest unused value\r\n%\r\n% In the last step, if colors 1 through _n_ are used by neighbors, then the\r\n% number of colors used in the map will grow to _n_+1. This means that the\r\n% number of colors used for the whole map will depend on the connections\r\n% and the order of the states. Let's see what happens if I apply this\r\n% algorithm to the states in default (alphabetical) order.\r\n%\r\nn = length(p);\r\ncolor = zeros(n,1); % Initialize array to hold color numbering\r\nnumcolors = 1; % Number of colors needed (so far)\r\nfor k = 1:n\r\n    idx = neighbors(G,k); % Get neighbors of the kth node\r\n    idx = idx(idx < k);   % But just those that have an assigned color\r\n    neighborcolors = unique(color(idx)); % Get colors used by neighbors\r\n    % Assign the smallest color value not used by the neighboring nodes\r\n    thiscolor = min(setdiff(1:numcolors,neighborcolors));\r\n    % If there isn't one, add another color to the map\r\n    if isempty(thiscolor)\r\n        numcolors = numcolors + 1;\r\n        thiscolor = numcolors;\r\n    end\r\n    color(k) = thiscolor;\r\nend\r\ndisp([num2str(numcolors),' colors needed'])\r\n\r\n%%\r\n% Five colors is actually common for many maps.\r\n\r\npolygonplot(p,color)\r\n\r\n%%\r\n% I'll be plotting the states with a custom color ordering a few times, so\r\n% I figured it would make sense to make a short function to do that:\r\n\r\ntype('polygonplot')\r\n\r\n%% Greed is good?\r\n% Five colors is pretty good, but the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Four_color_theorem four color mapping\r\n% theorem> states that you need only four colors to color any map so that\r\n% no neighboring regions have the same color. However, in true pure math\r\n% style, the theorem only says it _can_ be done, not _how_ to do it.\r\n% \r\n% Is there an algorithm I can use to assign colors to the states to achieve\r\n% a four-color map coloring? It turns out that this is a difficult problem\r\n% in general. There are algorithms, but they are far more complicated than\r\n% I want to deal with!\r\n%\r\n%%\r\n% So instead, what about just shuffling the order of the states, then\r\n% applying the greedy algorithm above? I took that code and turned it into\r\n% a function that takes a graph as input and returns the color numbering\r\n% and number of colors needed (equivalent to the max of the color\r\n% numbering) as output.\r\n%\r\n% Now I just need to shuffle the states and apply the function. But first,\r\n% the matrix of connections is currently just the lower-triangular part.\r\n% That structure will be ruined by the shuffling, so I'll make the full\r\n% matrix version:\r\n\r\nborder = border + border';\r\n\r\n%% \r\n% Now let's try shuffling and see how many colors we need:\r\n\r\nrng(123)  % for reproducibility\r\nidx = randperm(48);\r\nGperm = graph(border(idx,idx));\r\n[~,nc] = greedycolor(Gperm)\r\n\r\n%%\r\n% OK, it's working, but that particular shuffle didn't help. It actually\r\n% was worse. Well, that's random numbers for you. Maybe it's a good idea to\r\n% see how the number of colors needed are distributed. Let's run the\r\n% algorithm a bunch of times and see:\r\n\r\nrng(123)\r\nnexp = 1000;\r\nnumcolors = zeros(nexp,1);\r\nfor k = 1:nexp\r\n    idx = randperm(n);\r\n    Gperm = graph(border(idx,idx));\r\n    [~,numcolors(k)] = greedycolor(Gperm);\r\nend\r\nhistogram(numcolors)\r\n\r\n%%\r\n% Interesting. Most of the time I get five, sometimes I need six, and about\r\n% 5% of the time I do indeed get a valid 4-color mapping. So a simple way\r\n% to get a 4-color mapping would be to try random permutations until only\r\n% four colors were needed. A terrible algorithm? Perhaps. But I bet it\r\n% works:\r\n\r\nnumcolors = Inf;\r\nwhile numcolors > 4\r\n    idx = randperm(n);\r\n    Gperm = graph(border(idx,idx));\r\n    [color,numcolors] = greedycolor(Gperm);\r\nend\r\npolygonplot(p(idx),color)\r\n\r\n%% Adding a little intelligence (but with no guarantees)\r\n% Surely there's a better way, though. Right...? Well, maybe. I did\r\n% encounter an algorithm for generating 5-color mappings. Basically, remove\r\n% nodes from the graph one by one, until the nodes of the remaining graph\r\n% all have degree greater than five. Then... do more stuff, which will\r\n% color the remaining graph. Then you add the nodes back, coloring them as\r\n% you go. I didn't really pay attention to the details because it seemed\r\n% like there was a very good chance that you'd never get nodes with degree\r\n% greater than five. Every time you remove a node, the degree of every node\r\n% it's attached to goes down by one. So it seems like you could just try to\r\n% repeatedly remove the lowest-degree node. Keep the list of nodes in order\r\n% that you removed them, then use that (or, more precisely, the reverse of\r\n% it, from last to first) as the ordering in which to color the nodes. It's\r\n% not guaranteed to work, but it's probably not a bad option to try (and\r\n% surely more efficient than random permutations). Also, this was for\r\n% 5-color mappings, not 4, but let's just see what we get...\r\n\r\nG = graph(border,stnames);\r\nidx = zeros(n,1);\r\nfor j = 1:n\r\n    [~,k] = min(degree(G));\r\n    idx(j) = find(strcmp(G.Nodes.Name{k},stnames));\r\n    G = rmnode(G,k);\r\nend\r\nidx = flipud(idx);\r\nGperm = graph(border(idx,idx));\r\n[color,numcolors] = greedycolor(Gperm);\r\npolygonplot(p(idx),color)\r\n\r\n%%\r\n% And just like that, I have a 4-color mapping for the US! In fact, it's\r\n% not far from being a 3-color mapping! Only three states needed the fourth\r\n% color. In fact, notice that this approach tries to use the lowest numbers\r\n% as much as possible\r\n\r\nhistogram(color)\r\n\r\n%%\r\n% But maybe I just got lucky. So let's try this on another map. Feeling\r\n% brave, I found a world map shape file online. I applied the exact same\r\n% approach: imported it with |shaperead|, converted the resulting structure\r\n% array to a polygon array, used the \"pad-and-intersect\" method to build\r\n% the graph of shared borders, sorted by iteratively removing the\r\n% lowest-degree node, then applied the greedy coloring algorithm. The\r\n% result...?\r\n\r\n%%\r\n% <<..\/world4color.png>>\r\n\r\n%%\r\n% A 4-color world map! Just like that.\r\n\r\n%% How far can this go?\r\n% As I undertand it, real cartographers wouldn't have much use for my\r\n% algorithm. There's a definite skew in the colors (e.g., all islands are\r\n% color #1 because they have no borders), so the result isn't particularly\r\n% aesthetically pleasing. Are there any amateur (or professional!)\r\n% cartographers out there who want to try applying a \"real\" map-coloring\r\n% algorithm using polygons and graphs? I'd love to see your results. I also\r\n% know there must be maps that break my algorithm, but how well will the\r\n% algorithm hold up with actual maps in practice, rather than deliberately\r\n% pathological examples? If anyone has other polygonal maps they want to\r\n% try coloring with this approach, I'd love to hear how it works.\r\n%\r\n% And, of course, maps and graphs don't have to be just about physical\r\n% geography - they can be abstractions of any number of things. If you have\r\n% an application that could use map coloring for visualization, share your\r\n% ideas in <https:\/\/blogs.mathworks.com\/loren?p=2459#respond  the comments>.\r\n\r\n##### SOURCE END ##### fbeab510094044b299cdd457c9c5fac7\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2017\/polygonmaps2_06.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>Today, guest blogger Matt Tearle continues his investigation of the new <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/polyshape.html\"><tt>polyshape<\/tt><\/a> type (added in <a href=\"https:\/\/www.mathworks.com\/products\/new_products\/latest_features.html\">R2017b<\/a>) as a mapping tool.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2017\/10\/27\/color-your-world-more-with-maps-graphs-and-polygons\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[57,41,6],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2459"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=2459"}],"version-history":[{"count":3,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2459\/revisions"}],"predecessor-version":[{"id":2466,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/2459\/revisions\/2466"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=2459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=2459"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=2459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}