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

原来以为西西河的贴图功能与众不同，后来才发现原来是不支持PNG格式，换个GIF就行了。

这段没有看懂。能不能稍微解释一下？

我用的词大概不太准确。我所说的“分组”，目的是给基站赋一个属性。比如基站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还远。因此简单说来，相邻关系既取决于距离，也取决于方位。

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

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

不知是否解释清楚了。

这段涉及到计算几何和拓扑学的内容，感觉用文字很难讲清楚。

Computer geometry and Topology, 略懂一二，Voronoi diagram算法以前上学时写过。

确切地说，当时在帮邓太写作业。这个算法不太好写，正在抓耳挠腮之际，被导师看见。

问，“你搞Voronoi diagram干什么？与课题无关呀”

老老实实回答，是帮GF捉笔。

导师说，“哦，搞定女生不容易。我这儿有，以前我做学生时写的，应该无大碍。”

我不清楚的问题是在这个case里，Voronoi怎么用。

回头我仔细读读你的文章。

这帖得花！

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

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

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

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

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

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

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

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

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

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