R2017b最近才发布。今天的客座博主Matt Tearle发现了一个有趣的应用许多新功能-解决基于地图的谜题。

内容

一个流动的MathWorker问题

“汽车”最近有一个由前数学工作者提交的脑筋急转弯．简短的，稍作修改的版本是:洛伦必须从特拉华州开车到美国相邻的每个州，每个州只去一次;罗兰的老板——我们姑且叫他杰克吧——提出要在最后一个州见她，那是他的出生地;但如果没有罗兰的行程安排，杰克怎么能知道最后的状态呢?

我马上就会给出答案，所以如果你想自己找出答案，现在就开始吧。没关系，我可以等。

做了什么?太好了。希望你们意识到有且只有一个州与另一个州接壤。该状态必须是任何路径的开始或结束。(你不能访问任何一个州超过一次，所以一旦你从一个相邻的州进入，你就被卡住了。)起点是特拉华州(与其他几个州接壤)，所以这个独特的“一级”州一定是罗兰史诗之旅的终点。

输入MATLAB

和往常一样，这个问题真正有趣的地方在于:我能在MATLAB中求解吗?这是一个典型的“旅行推销员”问题，所以最近添加到MATLAB的图形功能应该是有用的。但第一个问题是如何建立表示状态之间联系的图。事实证明，另一个新功能将有所帮助。

R2017b中引入了一种新的变量类型来表示2-D多边形。的polyshape函数取向量表示x而且y坐标并返回一个以这些点为顶点的多边形。碰巧的是，“映射工具箱”附带了一个数据文件，其中包含了美国各州边界的经度和纬度——这正是我所需要的。与shaperead函数我可以导入这个数据在结构数组的形式，与字段的名称和纬度/经度的边界:

状态= shaperead(“usastatehi.shp”）;移除阿拉斯加、夏威夷和华盛顿。States ([2,11,51]) = [];

的数组中提取数组对于单个状态来说非常简单X(经度)和Y(纬度)字段，并使用这些作为输入polyshape：

x =状态(1).X;y =状态(1).Y;P =多相(x,y)

p = multihape与属性:顶点:[518×2 double] NumRegions: 2 NumHoles: 0

现在，状态被表示为一个多边形，我可以使用可以与多边形工作的函数，如绘图:

情节(p)

但为了真正获得使用多边形的好处，我想获得一个多边形数组，其中每个元素都是一个多边形，代表一种状态。我可以提取x而且y组件的每个状态在循环中，但任何时候我看到自己应用操作到数组的每个元素，我认为“时间为arrayfun!”

struct2poly = @(s) polyhape (s.X,s.Y);%定义我的struct ->多形体操作P = arrayfun(struct2poly,states)%适用于struct STATES的所有元素

p = 48×1具有属性的多相数组:顶点NumRegions NumHoles

因为这是MATLAB，函数是情节应该适用于多边形数组，就像标量多边形一样，对吧?

情节(p)

这不是很好吗?每个多边形被绘制成它自己的阴影形状。如果我们放大，我们就能看到这个谜题的答案。

轴([-75 -66 42 48])

问题:谁是我的邻居?

我们可以用肉眼看到各个州是如何共享边界的，但是我们如何让MATLAB以自动的方式来确定这一点呢?让我们从最简单的问题开始:给定两个状态(多边形)，我们能否确定它们是否共享边界?

Me = p(17);Ma = p(19);Nh = p(27);Subplot (1,2,1) plot([ma nh])标题(“共同边界”) subplot(1,2,2) plot([ma me])“没有共同边界”）

多边形有a顶点属性，其中包含边界位置。因此，一个简单的方法是查看两个多边形是否有共同的顶点。然而，这有很多潜在的问题。首先，两个形状可以共享边界而不共享顶点:

A = polyhape ([0 1 1 0]，[0 0 3 3]);B =多义词([1 2 2 1]，[1 1 2 2]);subplot(1,1,1) plot([a b])相交(a. vertices,b. vertices，“行”）

Ans = 0×2空双矩阵

其次，即使所有测量点都对齐，也总有可能出现浮点精度问题:31°41'59”是如何表示的?

Lat1 = 31.6997222222222 lat2 = 31 + 41/60 + 59/3600 Lat1 == lat2 Lat1 - lat2

Lat1 = 31.7 lat2 = 31.7 ans = logical 0 ans = -3.5527e-15

更好的方法是用几何方法来考虑。如果平面上的两个区域的交点是一条直线或曲线，则它们共享一条边界。MATLAB中的新多边形有一个相交功能!然而，不幸的是，从编程的角度来看，两个多边形的交集是另一个多边形。一个面积为零的多边形(当交点是一条线时)是空的，所以没有明显的方法来区分共享边界的状态。

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

ans = multihape with properties: Vertices: [0×2 double] NumRegions: 0 NumHoles: 0 ans = multihape with properties: Vertices: [0×2 double] NumRegions: 0 NumHoles: 0

此外，这种方法仍然容易受到有限精度问题的影响。

解决办法:土地的肥肉

新的MATLAB多边形有polybuffer函数，该函数提供了一种通过将边界推出给定数量来“增肥”多边形的方法。这是马萨诸塞州，气温上升了0.1度。7-mile)边界:

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

这提供了一种相当简单但健壮的方法来确定状态是否相邻:在两个状态周围放置一个小缓冲区，然后查看是否有任何重叠。

Pfat =聚缓冲液(p,1e-4);在每个州周围增加35英尺Me = pfat(17);Ma = pfat(19);Nh = pfat(27);马马相交(nh)相交(我)

ans = multihape with properties: Vertices: [541×2 double] NumRegions: 1 NumHoles: 0 ans = multihape with properties: Vertices: [0×2 double] NumRegions: 0 NumHoles: 0

正如您对表示多边形的数据类型所期望的那样，有一个区域函数，它做的就是它的名字所暗示的:

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

Ans = 0.00035462 Ans = 0

因此，确定填充状态是否重叠应该很简单:交集是否有非零面积?但作为程序员，我有点担心:我是否应该使用一个函数，比如区域这需要一些管理费用?直接查询由交点产生的多边形的属性会更有效吗?

但是，在考虑实现细节之前，还需要考虑另一个小问题。的“四拐角”美国西南部的一个地区是科罗拉多、新墨西哥州、亚利桑那州和犹他州四个州的交汇处。科罗拉多州与亚利桑那州接壤吗?犹他州与新墨西哥州接壤吗?我们可以让哲学家和数学家就此争论。但除非一个无限瘦的罗兰开着一辆无限瘦的车，对我们来说，答案是否定的。事实上，从科罗拉多州开车到亚利桑那州，不经过犹他州或新墨西哥州是不可能的。

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

但如果我们看看“肥胖”州之间的交集，科罗拉多州和亚利桑那州之间会有一小部分重叠。请注意，它将是非常很小——只比我研究生时的公寓稍大一点，这应该被认为是一个地理面积的量子量。任何国家之间真正的边界至少要比这个大一个数量级。所以现在我们有了一个简单而可靠的方法来确定各州是否共享边界:

面积(相交(ma,nh)) > 1e-6面积(相交(ma,me)) > 1e-6

Ans =逻辑1 Ans =逻辑0

现在我只需要把它应用到每一对状态。我也许可以试着去想象一下arrayfun，但这是一个简单的情况为-loop方法可能是更好的主意。事实上，循环可以帮助我避免冗余计算。如果状态A与状态B相邻，那么状态B与状态A相邻，我不需要检查。

Border = 0 (48);为K = 1:48为J = (k+1):48k只需要j，我们还没有检查过Border (j,k) = area(cross (pfat(j)，pfat(k))) > 1e-6;结束结束

这样做的结果是一个低三角连接矩阵。现在我可以从连通性矩阵中构建一个图并解决问题。其中一个简洁的图函数是学位，它给出了到每个节点的连接数。

G = graph(边界，“低”）;直方图(学位(G))

图中有一个一级节点。这就是我们想要的。但这对应的是哪种状态呢?名称存储在的名字原始结构数组的字段。我将使用我最喜欢的MATLAB技巧之一将它们提取到一个单元格数组中。当索引产生多个结果(而不仅仅是具有多个元素的数组)时，这些结果将以逗号分隔的列表形式返回。也就是说，如果年代是一个结构数组(例如)，颇具等于(1)。事情，年代(2).Thing, ..., s(end).Thing．使用逗号分隔的列表的好处在于，MATLAB使用这种形式将元素连接到一个数组中(例如，(a, b, c)或{a, b, c})和将输入传递到函数(即，myfun (a, b, c))．因此，我可以提取所有的的名字结构数组的字段元素州然后用简单的MATLAB代码将它们连接成一个单元格数组:

stnames = {states.Name};

现在，终于，我可以找出哪个州只与另一个州接壤:

stnames{degree(G) == 1}

ans =“缅因州”

可视化结果

有了州名，我可以进一步可视化地图和连通性图。首先，可以为图中的节点命名:

G = graph(边框，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