罗兰的冒险:地图、图表和多边形

R2017b最近被释放。今天的嘉宾博客马特Tearle,发现了一个有趣的应用之一许多新功能——解决地图拼图。

内容

一个旅行MathWorker问题

“汽车”最近有一个脑筋急转弯前MathWorker提交。短,略修改版本是:罗兰必须开车从特拉华州到每个州在美国连续,访问每个州到底一次;罗兰的老板——让我们称他为杰克提供了满足她在过去的状态,这是他的出生地;但是杰克知道过去的状态如何,没有等待罗兰的行程吗?

我要给出答案,所以如果你想弄明白自己,现在这样做。没关系,我将等待。

做了什么?太好了。希望你意识到有一个且只有一个国家边界只有一个其他国家。国家必须开始或者结束的路径。(你不能访问任何国家不止一次从单一相邻状态一旦你进入,你困)。一开始是特拉华州(其他几个州接壤),所以这种独特的“阶”状态必须罗兰的史诗般的旅程。

输入MATLAB

像往常一样对我来说,这个问题的真正有趣的方面是:我能在MATLAB解决它吗?这是一个经典的“旅行推销员问题,所以最近添加到MATLAB的图形功能应该使用。但第一个问题是如何构建图,代表了国家之间的联系。事实证明,另一个新特性会有所帮助。

一种新的变量类型R2017b代表介绍了二维多边形。的polyshape函数向量表示x和y与这些点坐标,并返回一个多边形的顶点。恰巧,映射工具箱提供了一个数据文件包含纬度和经度的边界的美国——就我所需要的东西。与shaperead函数可以导入这些数据结构数组的形式,与字段的名称状态和边界的纬度/经度:

州= shaperead (“usastatehi.shp”);%去除阿拉斯加与夏威夷、华盛顿特区州([2,11日,51])= [];

对一个国家来说,这是直接提取的数组X(经度)和Y(纬度)字段和使用这些输入polyshape:

x =州(1)方式;y =州(1).Y;p = polyshape (x, y)

p = polyshape属性:顶点:[518×2双]NumRegions: 2 NumHoles: 0

现在状态表示为一个多边形,我可以使用可以使用多边形的功能,如策划:

情节(p)

但是要想使用多边形的好处,我想买一个数组,其中每个元素是一个多边形代表一个州。我可以提取x和y组件对于每一个国家在一个循环中,但任何时候我看到自己将一个操作应用到数组的每个元素,我认为“时间arrayfun!”

struct2poly = @ (s) polyshape (s.X s.Y);%定义结构体- > polyshape操作p = arrayfun (struct2poly状态)%的适用于所有元素结构状态

p = 48×1 polyshape数组属性:顶点NumRegions NumHoles

因为这是MATLAB函数情节应该工作在数组的多边形,标量多边形一样,对吧?

情节(p)

那不是很好吗?每个多边形绘制为自己的阴影的形状。如果我们放大,我们可以看到解决难题。

轴([-75 -66 42 48])

问题:谁是我的邻居吗?

通过眼睛,我们可以看到国家分享边界,但是我们要如何用MATLAB来确定在一个自动化的方式吗?让我们先从最简单的问题:给定的两个州(多边形),我们可以确定他们共享一个边境吗?

我= p (17);马= p (19);nh = p (27);次要情节(1、2、1)情节(马(nh)标题(“共同边界”次要情节(1、2、2)情节(马[我])标题(“没有共同边界”)

多边形有顶点属性包含边界的位置。一个简单的方法是看这两个多边形顶点有共同之处。然而,这有很多潜在的问题。首先,两个形状可以分享没有共享顶点的边界:

= polyshape ([0 1 1 0], [0 0 3 3]);b = polyshape ([1 2 2 1], [1 1 2 2]);次要情节(1,1,1)情节([b])相交(a.Vertices b.Vertices,“行”)

ans = 0×2空双矩阵

其次,即使调查点对齐,总有潜在的浮点精度问题:如何31°41 59”代表?

lat1 = 31.699722222222222 lat2 = 31 + 41/60 + 59/3600 lat1 = = lat2 lat1——lat2

lat1 = 31.7 lat2 = 31.7 =逻辑0岁= -3.5527 e15汽油

所以一个更好的主意可能考虑几何。两个地区在平面上如果他们共享一条分界线的十字路口是一条直线或曲线。并在MATLAB有一个新的多边形相交功能!然而,不幸的是,从编程的角度来看,两个多边形的交点是另一个多边形。和一个多边形零区(十字路口时,你得到一条线)是空的,所以没有明显的方式区分,共享一个边界。

马马相交(nh)相交(我)

ans = polyshape属性:顶点:[0×2双]NumRegions: 0 NumHoles: 0 ans = polyshape属性:顶点:[0×2双]NumRegions: 0 NumHoles: 0

此外,这种方法仍然容易受到了有限精度问题。

解决方案:脂肪的土地

新MATLAB多边形polybuffer函数,它给你一种“养肥”一个多边形按给定的边界。这是马萨诸塞州(约0.1度。7-mile)边界:

马mafat = polybuffer (0.1);情节([马mafat])

这给了一个相当简单,但健壮,方法确定的国家是邻居:把一个小缓冲区,然后看到周围是否有重叠。

pfat = polybuffer (p, 1的军医);%添加~ 35英尺在每一个州我= pfat (17);马= pfat (19);nh = pfat (27);马马相交(nh)相交(我)

ans = polyshape属性:顶点:[541×2双]NumRegions: 1 NumHoles: 0 ans = polyshape属性:顶点:[0×2双]NumRegions: 0 NumHoles: 0

正如你所期望的数据类型表示多边形,有一个区域函数,什么其名:

区(相交(ma, nh))地区(相交(马,我))

= 0.00035462岁= 0

所以决定填充状态重叠应该简单:十字路口有非零的区域吗?但我的程序员有点担心:我应该使用一个函数,等等区域和一些开销,会吗?会更有效的直接查询的属性多边形交集的结果吗?

然而,还有一个小问题,需要考虑之前担心的实现细节。的“四拐角”美国西南部地区是四个州的地方触摸——科罗拉多、新墨西哥、亚利桑那、犹他。科罗拉多州边境亚利桑那州吗?犹他州边境新墨西哥吗?我们可以让哲学家和数学家争论。但除非无限薄的罗兰是无限薄的开车,答案,就我们的目的而言,是否定的。没有办法在现实中从科罗拉多开车到亚利桑那州没有经历犹他州和新墨西哥州。

情节(pfat“线型”,“没有”轴([-109.055 -109.035 36.99 37.01])

但是如果我们看一下“肥”国家之间的十字路口,会有一个小亚利桑那州科罗拉多和重叠。注意,这将是非常小,仅略大于我的公寓在研究生院,这应该被视为一个量子的地理区域。任何真正的边境州至少会比这大一个数量级。现在我们有一个简单的和健壮的方法来确定是否州边界:

区(相交(ma, nh)) > 1 e-6区域(相交(马,我))> 1 e-6

ans =逻辑1 ans =逻辑0

现在我只需要应用到每条状态。我可以试着让幻想arrayfun,但这是一个情况下,简单的为循环的方法可能是一个更好的主意。事实上,循环可以帮助我避免冗余计算。如果状态边界状态B, B边界状态,我不需要检查。

边境= 0 (48);为为止k = 1:48为j = (k + 1): 48%只需要j ks我们还没有检查边境(j, k) =区域(相交(pfat (j), pfat (k))) > 1 e-6;结束结束

这是一个下三角矩阵的结果连接。现在我可以建立一个图的连接矩阵和解决这个问题。的一个简洁的图形功能学位,使每个节点连接的数量。

图G =(边界,“低”);直方图(学位(G))

所以有一次节点图。这是一个我们想要的。但是对应于哪个州呢?中存储的名称的名字领域的原始结构数组。我将它们提取到一个单元阵列使用我最喜欢的一个MATLAB技巧。当索引产生多个结果(不仅仅是与多个元素的数组),结果回来的逗号分隔列表。也就是说,如果年代是一个结构数组(例如),颇具相当于(1)。件事,(2)。的事情,…,年代(end).Thing。好有一个以逗号分隔的是形式的MATLAB用于连接成一个数组元素(例如,(a, b, c)或{a, b, c}),通过输入一个函数(例如,myfun (a, b, c))。因此,我可以提取的名字场结构数组的元素州连接成一个单元阵列和一个简单的MATLAB线:

stnames = {states.Name};

现在,终于,我可以找出哪些国家边境只有一个状态:

stnames{学位(G) = = 1}

ans =“缅因”

可视化的结果

国家的名字,我可以进一步和可视化地图和连接图。首先,可以名称的节点图:

图G = (stnames边境,“低”);

这是非常有用的,当你想象图因为节点自动标记:

情节(G)

但这个图不显示美国物理布局。也可以指定节点的位置绘制图形时,但是我需要一个在每个州作为节点的位置。中间的状态就好了…你猜怎么着?有一个多边形函数:重心。

(x, y) =重心(p);情节(G,“XData”,x,“YData”,y)

这看起来很不错。这将是很高兴添加地图供参考。

情节(p)在情节(G,“XData”,x,“YData”,y)举行从

好了!一些酷的注意,代码:两个使用的情节,这两个“异国情调”,非数字数据类型(一个多边形数组和一个图)。这是我们的管理团队努力工作,确保功能是一致的,因此,例如,情节作品自然地对不同类型的数据。这是一个功能的MATLAB我非常感谢。作为一个MATLAB用户,这意味着我不需要消耗大脑能量的绘图功能,甚至它的变体情节,我必须使用。我可以使用情节,然后继续我实际上想做什么。

接下来去哪里?

我解决了脑筋急转弯,甚至有点进一步做出很好的可视化的状态和它们的连接。但有一件事对我的可视化,还缠着我:美国与七彩色独特的颜色的顺序,美国出现在多边形数组(这是字母的名字)。这意味着邻国有时是相同的颜色。例如,注意,内布拉斯加州和南、北达科他州元素25岁,32岁和39,这意味着他们所有相同的颜色。我碰巧有回忆一个数学定理说,任何可以彩色地图只有四个独特的颜色,这样没有邻近区域有相同的颜色。

对我来说,这听起来像一个有趣的任务多边形和图表,…但另一个故事了。与此同时,让我们知道在评论中如果你能想到的在你的工作地方polyshape类型可能是有用的。

得到了MATLAB代码

发表与MATLAB®R2017b