主题：【原创】最近为公司开发了一个小软件，挺好玩的 -- 温雅颂

建立“地捞泥”三角网对我来说只是小菜一碟，玩它玩了十多年了。用它处理过上百万点的数据，现在这区区七百多个点就更不在话下了。

建好三角网，首先来解决网络技术的分组，这个容易点。

我先利用三角网，求出每个基站到周围基站的平均距离。然后取所有基站平均距离中的最大值，用它的一半作为分组的界线，将基站分为两组，并以两种颜色将基站显示在地图上。用目视的办法判断这个分组是否合适。如果不合适（一开始就合适的可能性几乎可以忽略不计），那么这个分界是太大还是太小呢？如果太大，那么取它的一半再重新分组；如果太小则取它的一倍半重新分组。直到基站的分组基本符合城郊范围为止。

解决了网络技术分组后，下一个目标就是对基站做运营商的分组，也就是“四色定理”的应用。

“四色定理”还是“四色猜想”的时候，描述的是对地图行政区划的染色。任意一张地图，不管有多少行政区，也不管其边界线多复杂，只要没有“飞地”，这张地图用最多四种颜色就可以对所有行政区染色，并保证相邻行政区的颜色不同。

如果把问题抽象出来，所谓的地图，其实就是图论或拓扑学中的“图”，所不同之处在于，地图中的行政区域，变成了图论中“图”中的节点，而相邻行政区之间的界线，变成了“图”中节点之间的连线。“地捞泥”三角网，从拓扑学的角度看，就是一个标准的“图”。因此，对三角网中每个点的染色，完全符合“四色定理”的条件，因此四个颜色就足够了。落实到我做的这个模拟软件上，就是对三角网中每个基站进行“染色”，也就是赋给它四个运营商中的一个。

这个算法本身并不复杂，无非是在对当前基站“染色”时先要检查其周围基站的“颜色”，保证赋给当前基站的颜色没有与周围任何基站的颜色相同。当周围基站四种颜色都已用过，无法对当前基站染色的情况下，程序就要后退一步，对前一个基站重新染色，然后再试。如果前一个基站重新染色后依然不行，或者前一个基站没有另外颜色可选，程序就要再后退一步，直到以前某个基站改变颜色后可以使当前基站有色可染。总之，这个“染色”程序就是“摸着石头过河”。摸着石头了就往前走一步，摸不着就后退一步，换个方向继续摸，直到过了河为止。

因为四色定理的存在，因此不用担心摸不着石头，但有时河都过了一多半了，却发现怎么也摸不着石头了，只好一步一步往后退，甚至几乎要退到下河的地方了。因此这个程序处理两百点以下的数据还好，在处理七百多点时着实花了不少时间。

染完色之后还有一步要做的是将四种颜色平均一下。由于程序中染色时都是先试第一种颜色，最后才试第四种颜色，因此第四种颜色的使用频率最低，所以要在不产生染色错误的情况下增加一些第四色的数量。虽然理论上讲第一种颜色的出现频率最高，第二种颜色其次，第三种颜色再次，第四种颜色最少。但实际上前三种颜色的出现频率相差不大，只是第四种颜色明显比其它颜色少。也就是说，在染色过程中，大多数情况下三种颜色就够，只是在很少情况下才会用到第四种颜色。

到这时，每个基站都已经有了固定的运营商和网络技术，可以说是：万事俱备，只欠东风了。

我用的词大概不太准确。我所说的“分组”，目的是给基站赋一个属性。比如基站A属于运营商X，提供的网络技术是L，而基站B属于运营商Y，网络技术是M。我所做的模拟软件里只给基站赋了两种属性，一个是运营商，一个是网络技术。

但是，对于某个基站来说，在赋这两种属性的时候，考虑的因素是不同的。在赋运营商属性时，要求相邻基站分别属于不同的运营商。而在赋网络技术时，要求将全部基站分为两大组，城里组和郊外组，城里组为新网络技术，郊外组为旧网络技术。而城里组和郊外组的区分，就在于基站的密度，密度大的地区为城里，密度小的地区为郊外。

由此可见，赋运营商属性时，需要掌握当前基站与周围基站之间的相邻关系，赋网络技术属性时，则需要掌握当前基站与周围基站的平均距离。二者都离不开当前基站与周围基站的相邻关系。

那么，如何确定两个基站是否相邻，这并不是一个简单的数字计算的问题，而变成了一个几何问题和拓扑学问题。举个例子：假设基站A，在它北面有个基站B，距基站A有一百米。而B的北面还有一个基站C，距B一百米，距A二百米。显然，B和A相邻，而C和A不相邻。但是，在基站A的南面二百五十米处，有个基站D，A与D之间没有其它基站，而且在A的东南和西南方向上都没有基站，那么D与A就是相邻的，尽管D距A比C距A还远。因此简单说来，相邻关系既取决于距离，也取决于方位。

“地捞泥”三角网的特点在于：网内任意一个三角形，其外接圆内都只有三角形的三个顶点，不可能再有第四点。因此，“地捞泥”三角网中的三角形都比较“胖”，是所有组成三角网的方法中最“胖”的，最接近等边三角形的三角网。

在一个有限点数的三角网里，三角形的数量大体是点数的两倍（有个具体公式，但我一下想不起来了）。不管以什么方式组网，三角形的数量不变。那么，如果三角形很“瘦”，就会导致有些点是很多三角形的顶点，而有些点只是很少几个三角形的顶点。如果我们用同在一个三角形内来定义点与点之间的相邻关系，显然“地捞泥”三角网是最理想的，因为它的三角形最“胖”，因此每个点所拥有的相邻点数最均匀，空间分布也最合理。

在我弄到了这七百多基站的位置后，公司里同事们的兴趣也被挑起来了，有人就提出来新的要求：现在城里的基站所使用的技术类型一般比郊外的要高，比如GSM在城里是HSPA，而郊外可能只是EDGE，希望我能把它们区分出来。

这玩艺手工分不难，在地图上画个范围，然后用这个范围去套所有的基站，在范围内的用新技术，范围外的用老技术就行了。

可是，到这个时候，我已经有了如何将这七百多基站组织管理起来的办法了。解决这个问题也就成了顺手牵羊的事。

那么，这个对七百多基站，既能按技术分组，又能按运营商分组的办法到底是什么呢？

呵呵，它就是Delaunay Triangulation。它的另一种表示方法则叫Voronoi Diagram。

图里面虚线表示的是“地捞泥”，实线表示的就是“佛肉泥”。

具体它的特性我就不在这里罗嗦，大家可以摆渡，也可以放狗，再不行还可以围鸡。

有了这玩艺，就可以很快地从中找出距离当前位置最近的一个基站，从而提高计算信号强度的速度。其次，在这个三角网里，可以方便地计算出每个基站和周围基站的平均距离。显然，城里基站密，郊外基站稀，那么找出一个合适的距离，就可以将基站分成“城里组”和“郊外组”。

而将基站按照运营商分组，使其相邻基站分属不同的运营商，就变成了图论中著名的“四色定理”问题了，也就是只用四种颜色给三角网中的结点染色，就可以保证相邻的结点分属不同的颜色！

哈哈，这才是本软件最好玩的地方。

渴了。。。。。。

到目前为止，户外工作人员的行车路线模拟已经基本就绪，剩下的一个关键问题就是模拟无线广域网的信号强度了。一开始，公司里的同事们因为不懂GIS，对空间方面的事一窍不通，提不出像样的要求，所以我一开始也没往深了琢磨，只想着看起来像那么回事就行了。

在做这个模拟软件之前，我接触过一些实地采集的信号强度数据。我发现即使你站在原地不动，你所接收到的信号强度也在一定范围内波动。刚开始考虑这个模拟软件时，我曾想过用一定范围内的随机数模拟这个信号强度。可后来发现不合适，因为信号强度只是波动，不是跳动。一个人接收到的信号强度一般不太可能从-60一下子跳到-130。显然，这样使用随机数不行。

随后，我就开始琢磨如何模拟信号强度的波动。我想到这样一种办法：在初始状态时，给路径起点一个在正常范围内的随机的信号强度值，然后随着时间的推移，对每个坐标点上的信号强度值，以前一个坐标点上的信号强度为基准做随机改动，改动的幅度在-2到+2之间。这样一来，信号强度就会随着时间的推移显示出一条波动的曲线。

但是后来我又对自己提出来新的要求：能不能模拟一套发射塔的位置数据，然后根据发射塔到路径坐标点之间的距离来计算信号强度呢？显然是可以的。不过我得先模拟发射塔的位置数据，这却不容易。虽然我知道一般城里发射塔比较密集，郊外比较稀疏。但城里的密会密到什么程度，郊外的稀又会稀到什么程度？我对此却一点概念都没有。虽说是模拟数据，不需要多高的真实度，但发射塔的密度分布总要合理，大体符合实际情况才好。

到这时，格言的重要性开始显现：外事不决问孤狗！网上一搜，居然找到几个网站，上面有全美国的发射塔数据。花了两个小时的时间，总算把华盛顿州主要的发射塔位置整理出来了，一共有七百多座。听同事讲实际比这要多，但这对我已经够了，足以显示出城乡地区塔的分布特点了。

因为我要模拟的是一个有几千员工的大公司，员工们使用的网络服务分别来自几个不同的运营商，因此我需要把搜集来的七百多发射塔按不同的运营商分组。一开始我就把它们随机地分了三组，一组是AT&T，一组是Sprint，一组是Verizon。但我仔细一看发射塔的分组情况，发现效果不够好，因为这样随机分组虽然可以保证组与组之间发射塔数量不会相差很多，但因为这个随机分组没有考虑到它们的空间分布状况，所以有些紧挨在一起的塔却被分在了同一组，这显然不符合实际情况，因为运营商肯定不会把两座发射塔建在一起。

那么如何分组才能使各组之间数目相差不多，而又使同一组的发射塔不会挤在一起呢？

手工分组当然可以，但那就没意思了，公司给你开的工资不低，可不想看你干小工的活。咱要么不干，干就要干得有点层次，这才好去忽悠不是？

喝水去了。。。。。。