颜色你的世界:更多的地图,图表,和多边形

今天,客人的新博客马特Tearle继续他的调查polyshape类型(中添加R2017b)作为映射工具。

内容

我们在哪里?

在一个以前的文章,我使用了新的polyshape变量类型在MATLAB来确定状态之间的联系。你可以看到那篇文章中的代码。我就负载连接的多边形和矩阵来自:

负载stateborders%的图连接状态图G = (stnames边境,“低”);%获得国家重心位置(x, y) =重心(p);%绘制地图和联系情节(p)在情节(G,“XData”,x,“YData”,y)举行从

这个很好的可视化,它让我的颜色从默认的多边形情节没有做一个好的地图,因为邻国通常是相同的颜色。的情节函数,当然,不知道连接——这只是使用一组颜色的顺序多边形的数组。使用知识之间的连接状态(存储在矩阵边境和图G),我应该能够重新着色美国所以没有邻国有同样的颜色。

开始简单:贪婪的着色算法

请注意,实际的颜色是任意的。这样做的目的是分配一个号码,每个州。这个数字可以用于索引颜色(或colormap)的列表。

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

在最后一步中,如果颜色1n使用的邻居,然后映射中使用的颜色的数量将增长n+ 1。这意味着整个地图使用的颜色数量将取决于连接和订单的状态。看看会发生什么,如果我这个算法适用于美国违约(字母)。

n =长度(p);颜色= 0 (n, 1);%初始化数组来保存颜色编号numcolors = 1;%所需的颜色数量(到目前为止)为k = 1: n idx =邻居(G、k);% k节点的邻居idx = idx (idx < k);%,只是那些有一个指定的颜色neighborcolors =独特的(颜色(idx));%得到邻居所使用的颜色%分配最小的颜色值没有使用的相邻节点thiscolor = min (setdiff (1: numcolors, neighborcolors));%如果没有一个,另一种颜色添加到地图如果isempty (thiscolor) numcolors = numcolors + 1;thiscolor = numcolors;结束颜色(k) = thiscolor;结束disp ([num2str (numcolors),颜色需要的])

5种颜色需要

五个颜色实际上是常见的许多地图。

polygonplot (p,颜色)

我会策划美国用一个自定义颜色订购几次,所以我想将意义做一个简短的函数:

类型(“polygonplot”)

函数polygonplot (p,颜色)%获得颜色的列表(使用默认图颜色)ax = gca;颜色= ax.ColorOrder;%绘制多边形和改变他们的颜色映射=情节(p);k = 1:长度(p)地图(k)。FaceColor =颜色(颜色(k):);地图(k)。FaceAlpha = 0.8;%的阴影黑暗结束

贪婪是好事吗?

五个颜色很好,但是四个颜色映射定理州,你只需要四种颜色颜色任何地图,这样没有邻近区域有相同的颜色。然而,在真正的纯粹的数学风格,这个定理只说它可以做,而不是如何去做。

有一个算法我可以使用指定的颜色来美国实现四色地图着色?事实证明,这是一个困难的问题。有算法,但它们比我要处理复杂得多!

所以,关于刚才洗牌的顺序,然后应用上面的贪婪算法?我把这段代码,把它变成一个函数,接受一个图作为输入并返回所需的颜色编号和数量的颜色(相当于最大的颜色编号)作为输出。

现在我只需要洗牌状态和应用功能。但首先,目前的连接矩阵的下三角的部分。结构将被毁了洗牌,所以我会把完整的矩阵形式:

边境=边境+边境';

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

rng (123)%的再现性idx = randperm (48);Gperm =图(边境(idx idx));[~,数控]= greedycolor (Gperm)

数控= 6

好吧,这是工作,但这个洗牌并没有帮助。它实际上是更糟。这是为你随机数字。也许这是一个好主意,看看颜色的数量分布。让我们运行的算法很多次,看看:

rng nexp = 1000 (123);numcolors = 0 (nexp, 1);为k = 1: nexp idx = randperm (n);Gperm =图(边境(idx idx));(~ numcolors (k)] = greedycolor (Gperm);结束直方图(numcolors)

有趣。大部分时间我得到五,有时我需要6个,约5%的时间我确实得到一个有效的单调映射。这样一个简单的方法来得到一个单调映射将尝试随机排列直到需要四种颜色。一个可怕的算法?也许。但我敢打赌,它的工作原理:

numcolors =正;而numcolors > 4 idx = randperm (n);Gperm =图(边境(idx idx));(颜色、numcolors) = greedycolor (Gperm);结束polygonplot (p (idx),颜色)

添加一个小情报(但不保证)

不过,肯定有一个更好的方法。对吧……?嗯,也许吧。我遇到一个算法生成五色映射。基本上,一个接一个地从图中删除节点,直到剩下的图的节点都有程度大于5。然后……做更多的事情,剩下的图颜色。然后添加节点,着色。我没有注意细节,因为它似乎有一个非常好的机会,你从未得到节点度大于5。每次删除一个节点,每个节点的程度是在下降。 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 =(边境,stnames);idx = 0 (n, 1);为j = 1: n [~ k] = min(学位(G));idx (j) =找到(strcmp (G.Nodes.Name {k}, stnames));G = rmnode (G、k);结束idx = flipud (idx);Gperm =图(边境(idx idx));(颜色、numcolors) = greedycolor (Gperm);polygonplot (p (idx),颜色)

就这样,我有一种映射的我们!事实上,它不是远非一个三色映射!只需要三个州第四色。事实上,注意到这种方法尝试使用尽可能多的最低数字

直方图(颜色)

但也许我只是很幸运。让我们试试另一个地图。勇敢,我发现了一个世界地图形状文件在线。我应用相同的方法:用进口的shaperead多边形转换结果结构数组,数组,使用“pad-and-intersect”方法构建共享边界的图形,按迭代消除排序最低的节点,然后应用贪婪的着色算法。结果……?

一个单调的世界地图!就像这样。

这能走多远?

按照我的理解,真正的制图者不会有多大用处对我的算法。有一个明确的倾斜的颜色(例如,所有岛屿都颜色# 1,因为他们没有边界),所以结果不是特别美观。有什么业余(或专业)制图师,他们想尝试应用“真实”地图着色算法使用多边形和图形?我想看看你的结果。我也知道一定有地图,打断我的算法,但如何将该算法与实际地图在实践中,而不是故意病态的例子吗?如果有人有其他多边形地图他们想尝试着色用这种方法,我很想听听它是如何工作的。

当然,地图和图表不必自然地理——他们可以抽象的任何数量的东西。如果你有一个应用程序,该应用程序可以使用可视化地图着色,分享你的想法的评论。

得到了MATLAB代码

发表与MATLAB®R2017b