色彩你的世界:更多与地图，图表和多边形

今天，客座博主Matt Tearle继续他的新调查polyshape类型(添加)R2017b)作为绘图工具。

内容

我们说到哪里了?

在一个以前的文章我用的是新的polyshape变量类型在MATLAB中确定状态之间的连接。你可以在那篇文章中看到代码。我将加载由此产生的多边形和连接矩阵:

负载stateborders绘制状态连接图G = graph(border,stnames，“低”）;%获取状态的质心位置[x,y] =质心(p);%绘制地图和连接情节(p)在情节(G,“XData”, x,“YData”, y)举行从

做了这个漂亮的可视化后，它让我震惊的是，默认多边形的颜色情节我们绘制的地图不太好，因为相邻的州经常被赋予相同的颜色。的情节函数当然不知道这些连接——它只是按照数组中多边形的顺序使用一组颜色。使用状态之间连接的知识(存储在矩阵中)边境这张图G)，我应该能够重新给状态上色，这样相邻的状态就不会有相同的颜色。

从简单的开始:贪心着色算法

注意实际的颜色是任意的。目标实际上是为每个州分配一个数字。然后可以使用该数字索引到颜色列表(或颜色映射)。

分配颜色的一个简单(“贪婪”)算法是:

在最后一步，如果颜色1到n被邻居使用，那么地图中使用的颜色数量将增长到n+ 1。这意味着用于整个地图的颜色数量将取决于连接和状态的顺序。让我们看看如果我将这个算法应用到默认(字母)顺序的状态会发生什么。

N = length(p);Color = 0 (n,1);初始化数组以保存颜色编号Numcolors = 1;%所需颜色数量(到目前为止)为k = 1:n idx = neighbors(G,k);%获取第k个节点的邻居Idx = Idx (Idx < k);只是那些有特定颜色的Neighborcolors = unique(color(idx));%获取邻居使用的颜色指定相邻节点未使用的最小颜色值Thiscolor = min(setdiff(1:numcolors,neighborcolors));如果没有，在地图上添加另一种颜色如果Isempty (thiscolor) numcolors = numcolors + 1;Thiscolor = numcolors;结束Color (k) = thiscolor;结束disp ([num2str (numcolors),“需要颜色”])

需要5种颜色

五种颜色在很多地图上都很常见。

polygonplot (p,颜色)

我将多次使用自定义颜色排序来绘制状态，因此我认为编写一个简短的函数来完成此操作是有意义的:

类型(“polygonplot”）

函数polygonplot(p,color) %获取颜色列表(使用默认的绘图颜色)ax = gca;colors = ax.ColorOrder;%绘制多边形并更改其颜色map = Plot (p);对于k = 1:长度(p)映射(k)。FaceColor = colors(color(k)，:);地图(k)。FaceAlpha = 0.8;使阴影更暗的结束

贪婪是好的吗?

五种颜色很不错，但是四色映射定理说明您只需要四种颜色来为任何地图上色，以便没有相邻区域具有相同的颜色。然而，在真正的纯数学风格中，定理只是说明了它可以做完，不做如何去做它。

我是否可以使用一种算法将颜色分配给各州以实现四色地图着色?事实证明，这通常是一个难题。有算法，但它们比我想处理的要复杂得多!

那么，如果只是改变状态的顺序，然后应用上面的贪婪算法呢?我将该代码转换为一个函数，该函数将图形作为输入，并返回颜色编号和所需颜色数量(相当于颜色编号的最大值)作为输出。

现在我只需要变换状态并应用函数。但首先，连接矩阵目前只是下三角部分。这个结构会被打乱，所以我做一个完整的矩阵版本:

Border = Border + Border ';

现在让我们试着洗牌，看看我们需要多少种颜色:

rng (123)再现率%Idx = randperm(48);Gperm = graph(border(idx,idx));[~，nc] = greedycolor(种子)

Nc = 6

好吧，它起作用了，但是那个特别的洗牌没有帮助。实际上情况更糟。对你来说，这些都是随机数。也许看看所需颜色的数量是如何分布的是个好主意。让我们把这个算法运行几次看看:

Rng (123) nexp = 1000;Numcolors = 0 (nexp,1);为K = 1:nexp idx = randperm(n);Gperm = graph(border(idx,idx));[~，numcolors(k)] = greedycolor(Gperm);结束直方图(numcolors)

有趣。大多数情况下我得到5种颜色，有时我需要6种颜色，大约5%的情况下我确实得到了有效的4色映射。因此，获得四色映射的一个简单方法是尝试随机排列，直到只需要四种颜色。一个糟糕的算法?也许。但我敢打赌它是有效的:

numcolors = Inf;而Numcolors > 4 idx = randperm(n);Gperm = graph(border(idx,idx));[color,numcolors] = greedycolor(胚芽);结束polygonplot (p (idx),颜色)

添加一点智能(但不保证)

不过，肯定有更好的办法。对吧……?嗯,也许吧。我确实遇到了一个生成5色映射的算法。基本上，一个接一个地从图中删除节点，直到剩余图中的节点的度数都大于5。然后……做更多的事情，这将使剩余的图形上色。然后你把节点加回去，给它们上色。我并没有真正注意到细节，因为看起来很有可能你永远不会得到度大于5的节点。每次移除一个节点，它所连接的每个节点的度都会下降1。 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...

G = graph(border,stnames);Idx = 0 (n,1);为j = 1:n [~，k] = min(度(G));idx(j) = find(strcmp(g.s nodes . name {k}，stnames));G = rmnode(G,k);结束Idx = flipud(Idx);Gperm = graph(border(idx,idx));[color,numcolors] = greedycolor(胚芽);polygonplot (p (idx),颜色)

就像这样，我有一个美国的4色映射!事实上，它离三色映射不远了!只有三个州需要第四种颜色。实际上，请注意，这种方法尝试使用尽可能少的数字

直方图(颜色)

但也许我只是运气好。我们在另一张地图上试试。我勇敢地在网上找到了一个世界地图的形状文件。我采用了完全相同的方法:用shaperead，将得到的结构数组转换为多边形数组，采用“垫交”法构建共享边界图，通过迭代去除最低度节点进行排序，然后应用贪心着色算法。结果……?

一张四色世界地图!就像这样。

这能走多远?

据我所知，真正的制图师不会用我的算法。在颜色上存在明显的偏差(例如，所有岛屿都是1号颜色，因为它们没有边界)，所以结果并不是特别令人赏心悦目。是否有业余(或专业)制图师想要尝试使用多边形和图形应用“真正的”地图着色算法?我很想看看你的结果。我也知道一定有地图会破坏我的算法，但在实际的地图中，算法能在多大程度上站得住，而不是故意制造病态的例子呢?如果有人有其他多边形地图，他们想尝试用这种方法上色，我很乐意听到它是如何工作的。

当然，地图和图表并不仅仅是关于自然地理的——它们可以是任何事物的抽象。如果你有一个应用程序，可以使用地图着色可视化，分享你的想法的评论。

获取MATLAB代码

使用MATLAB®R2017b发布