新手学c还是java(web编程基础)

前工作中有不少涉及到地图的项目，我参加了几次技术评审，前端伙伴们在 WebGIS 方面的知识储备稍有不足，这次分享的主要目的是科普一些在前端领域比较常用的 WebGIS 知识。另外，我之前的工作中积攒了一些从零开始搭建 WebGL 地图引擎的微薄经验，虽然最终遗憾没有上线，但在其中学到的一些WebGL知识还是值得分享一下。WebGL 可以说是前端可视化技术领域难度最大的一项图形编程技术，所以今天就结合 WebGIS 这个话题顺带分享一些 WebGL 的相关知识，不会太深入，很细节的技术点在后续文章里再讲解。

一 WebGIS 常用概念

在前端领域需要关注的 WebGIS 知识最主要的是搞清楚电子地图中的各种坐标系，其次需要对路网有一些基本的认知，包含路网的特征以及寻路算法的复杂度量级，其中对算法复杂度的了解不用精确到数字，只需要有一个大致的概念即可。

路网寻址是一套非常复杂的算法，除了路网本身的有向图特征以外，还需要将路况、天气甚至民生、政治等因素考虑在内。这是一项单独的研究课题，前端研发不需要关注太细节的东西。

1.1 坐标系

我们日常接触的地理坐标最多的是经纬度坐标，地球是一个椭球体，经纬度是球面坐标系。但是我们平时使用的电子地图都是平面的，如何把球面坐标系下的经纬度坐标映射为电子地图的平面坐标系（数学上称谓是笛卡尔直角坐标系）呢？这个映射过程就是投影变换，目前在 WebGIS 领域国际上统一使用墨卡托投影实现。

下面就分别介绍一下以上两种坐标系以及映射原理。

经纬度坐标

表面上看是两种，经纬度和墨卡托，但准确的说应该是三种（甚至N种）。因为我们日常接触到的经纬度坐标都是经过加密算法处理之后的偏移坐标，与地理上真实的经纬度坐标有一定的偏移量。

真实的地理经纬度坐标系是国际标准，称为WGS84标准，此标准下的坐标系称为地球坐标系或地理坐标系。绝大多数电子地图服务商都不会（或者说不准）直接使用 WGS84 坐标，因为地理信息是涉及国家安全的重要信息，所以一般都需要进行加密。

我们国家目前使用的加密标准是国家测绘局2002年制定GCJ02 标准，经过加密后的坐标系被称为火星坐标系。在我国的所有电子地图都必须至少经过 GCJ02 加密一次才可以上线使用。请注意，至少的意思是经过 GCJ02 加密之后，地图厂商还可以进行二次甚至三次加密，比如百度地图使用的 BD09 标准就是在 GCJ02 加密之后进行二次加密的结果。

下图显示的是同一个经纬度坐标在不同地图上的位置：

球面的经纬度坐标经过墨卡托投影之后是一张二维的平面图，图中的大部分内容的变动频率是非常低的，比如上图中展示的大陆和海洋板块，除非遇到地壳运动，否则基本不会变动。为了持久化存储，在webgis领域引入了「瓦片」的概念，意思是将墨卡托坐标系的二维地图按照既定的规则切成一个个小方块保存到服务器，然后前端的应用程序在绘制地图时将这些方块按顺序拼接为完整的地图，这些小方块被称为瓦片-tiles。

Tile 直接翻译是“瓷砖”，倒是很贴切，电子地图就是用一个个 tile 拼起来的，至于为啥被翻译成“瓦片”我也不清楚，行业术语，跟着叫就是了。

还记得前面提到的墨卡托投影的第二个假设吗？将地球假设为正球体，投影之后得到的平面地图是一个正方形，被切割成一个个瓦片也是正方形，这样能够大大降低计算复杂度。因为长方形需要考虑长和宽两个计算因子，而正方形只需要考虑边长一个因子即可。

瓦片的尺寸是固定的，普清瓦片边长是256像素，高清瓦片边长在普清基础上乘以2也就是512像素。但即便是高清瓦片在浏览器中渲染的时候也是被压缩成256像素，这里我先不解释为什么，大家也先不要看下文，先思考一下为什么这么做。

留空思考时间..

5…
4…
3…
2…
1…
下面揭晓答案。

所谓高清和普清的区别在于：在相同物理尺寸上的像素密集程度。高清瓦片是为了让地图在高清屏幕上看起来更清晰，高清电子屏幕的准入标准是DPR=2（retina屏），当然目前市面上有很多高清屏已经突破了这个值。DPR是屏幕物理像素与独立像素的比值，前端开发者应该清楚 DPR 对于图形的影响，也就能够理解为何高清瓦片被压缩一倍了，我就不在赘述了。

看到这里，前端伙伴们是不是觉得 WebGIS 其实也并没有那么神秘？其实跟我们日常开发所用的技术有很多共同点和相似性。

上面介绍了瓦片的基本概念，在地图中还有另外一个重要概念：比例尺-Scale。可以类比成望远镜的放大倍数，倍数越大，看到的东西就越多越清晰，地图比例尺就类似望远镜的放大倍数。在墨卡托投影的平面地图中比例尺代表每个像素等价的以米（meter）为单位的地理距离。

地图从宏观到微观被切分为不同的级别（level），相邻level的比例尺一般成两倍关系（并不绝对，下文解释）。请再次参考上面的图片，每放大一个级别（即level+1），每个瓦片都会被切割为4张新瓦片，比如level 1 的1号瓦片在level 2中被切割为1-0、1-1、1-2、1-3四张瓦片，但这四张瓦片代表的地理范围与 level 1和1号瓦片是完全相同的，只是细节更多了（类比望远镜就是看到的东西更清楚了）。

在这样的切割规则下，从宏观到微观，瓦片的数量随着地图 level 的增长成四倍增长关系（4^n），以数量为维度，所有的瓦片构成了一个金字塔结构，这就是 WebGIS 领域的术语：瓦片金字塔 – Tiles Pyramid。如下图：

上面介绍的其实是理论上的行业标准，但在现实工作中一般不会严格按照这份标准落地。在瓦片切割方面一般由3 个不同于标准的地方：

1. 相邻 level 不一定是严格的两倍关系；
2. 基于第一点，各level的瓦片不一定是无耦合的，部分瓦片可能被相邻的2个甚至N个 level 共享使用；
3. 不同的地图厂商（准确的说应该是地图数据服务商）使用的 level 上下限边界可能不同，以搜狗地图为例，level 最小值=3，最大值=19。

基于以上3点区别，不同的地图在一些涉及瓦片和level的计算规则上也有差异，另外再加上坐标加密算法的区别，所以大部分地图的数据是无法共通的。

路网结构

对于路网这部分知识的科普，主要目的是让大家对路网寻址算法的复杂程度和计算量级有一个大概的认知，从而针对目前以及后续项目中涉及到寻址功能的需求大家能够对技术上的可行性、成本以及排期有更加理性的评估。

下面这张图是在电子地图上的某个区域的路网示意图：

路网在数学上的模型是图（Graph）。图论是离散数学的一个分支，在计算机应用科学领域，《数据结构与算法》这门课中有专门的图论算法，而且占比非常大。但由于相比较其他内容，图论算法的复杂度高出很多，所以即便教材里有这一部分的内容，但很多高校在实际教学中不会教也不会考（反正我当时没学~囧）。

最简单的图是一个二元组，由顶点（vertex）和边（edge）组成，表达式为：

G = (V,E)

在 WebGIS 领域，路网在是一种有向带权图。所谓带权图可以简单的理解为每条边有一些额外的属性，比如路况、方向等等。

路网寻址的需求主要是用在路径规划和导航场景下，这两种场景有一个共同点：起点和终点是确定。在这个前提下，路网寻址其实就是图论中经典的最小路径寻址算法，这种算法已经非常成熟了，而且复杂度也已经被很多前人反复验证和改良过，目前各家地图使用的此类算法都是在时间复杂度和空间复杂度之间权衡的最优解，而且还要综合考虑出行方式、交通、天气等现实因素（这些在数学模型中都是带权图结构中edge的「权」）。

但是（没错，什么都有但是），高效的寻址算法背后，请一定要注意「起点和终点是确定的」这个重要的前提。如果没有了这个前提，复杂度会呈指数型增长，甚至可以说以现在的计算机硬件技术，这个复杂度是没有上限的。为什么这么讲，且看下文。

在地图的业务场景中还有一个非常典型的功能：POI检索。比如以某个点为中心在指定半径的圆形区域内检索特定类型的POI。或者在地图上自定义指定几个点，然后在以这些点为顶点的不规则图形内进行POI检索。这两种都是典型的POI检索场景，跟路网寻址一毛钱关系都没有。

然而有时候我们还期望另外一种检索方式：

1. 指定某个点为起点坐标；
2. 指定出行的方式以及最长出行时长或者最长出行距离；
3. 在前面两条要求下，找到在出行范围之内的特定类型（比如酒店、加油站等）的POI。

针对这种需求，我在搜狗工作期间写了一个专利，但是在商业软件领域基本不具备可行性，因为计算量太大了。这个专利纯粹是为了完成老板交付的任务~哈哈。

我们可以设想一下应该按照什么样的流程去解决这个需求。

第一种是正向解法：从起点开始沿着路网图的边递进检索，直到到达出行范围的最远边界。这是符合现实规律的一种方法，就好比我想找一家便利店，最远不能超过步行30分钟，然后我就从当前位置开始沿着路走啊走，遇到路口就随机选一个方向接着走，运气好的话选的路边有家店，运气不好的话只能回到路口再随机选一个方向试着找找，以此类推。当然现实跟算法的区别就是人的体力有限，一是不可能多线程，二是体力坚持不了走所有的路。

第二种是逆向解法。就是在进行寻址算法之前尽量做减法，以给定的条件尽量缩小检索范围。比如指定步行最长距离是5公里，起点在中关村科贸大厦，按照以下步骤进行：

1. 首先以科贸大厦为圆心，5公里为半径，检索圆形区域内的所有指定类型的POI，得到一个list；
2. 然后依次以list中的每个POI为终点，科贸大厦为起点进行路径规划，得到所有POI与起点的真实地理距离，筛选出小于等于5公里的POI。

事实上，前文提到的两种POI检索场景（圆形和自定义多边形）都是逆向解法。POI在数据库中的模型除了坐标以外，还有其他附加属性，比如国家、城市、行政区域、甚至在哪条路等信息，就是为了缩小检索范围从而减轻计算量。

逆向解法比正向解法的计算量小很多，但是两种解法的计算量都会随着出行时长和距离的增加呈指数型增长，几乎没有上限（当然这么说不准确，肯定是在地球范围之内~）。

如果地图厂商自己想要不计成本地实现这个需求还是有一定可行性的，因为他们自己拥有路网和POI数据。但是如果我们想实现就很困难了，首先我们没有数据，所以正向解法绝无可能；其次，我们是采买的地图厂商的服务，而商业化的服务都是有限制的，比如每天的POI检索量上限，如果限制在比较小的范围内同时检索量没有超过上限，逆向解法是有一定可行性的。但是（是的，还有但是），对于我们来说，这个可行性必须建立两个前提下：

• 第一，如果是以出行距离为边界，可行性相对高一些；
• 第二，如果是以出行时间为边界，则必须约束出行方式为步行或骑行。这两种方式下的路网寻址算法一般不需要考虑交通等影响出行时长的因素，这样在任何一方向上的最远边界距离都是一致的，即半径=速度 x 时长。而如果是机动车出行，则必须考虑交通因素，不仅复杂度高，而且每个方向上的最远边界距离很大可能不一致，也就是说先圈定一个圆形区域的逆向解法中的“减法”不成立。

路网相关的知识分享到这里，大家应该对寻址算法的计算量级有大概的认知了吧。作为科普，对 WebGIS 的了解到这个程度就可以了，其中还有很多WebGIS领域内的技术细节，篇幅有限就不一一列举了。下半部分是跟前端技术相关性比较高内容，以电子地图的渲染流程为引，介绍一下 WebGL 的一些基础知识。

二 WebGIS 与前端

这块内容分为两部分，第一部分介绍一下电子地图的渲染流程，期间按照瓦片的两种类型（静态/动态）分别讲一下涉及的前端技术；第二部分以当前主流的矢量地图为引，简单介绍一下 WebGL 的一些基础知识。关于 WebGL 的知识不会很深入，目的是让大家的对 WebGL 以及图形编程有大概的认知，后续前端组会制定一套数据可视化技术的系列课程，到时再深入到各项技术的细节知识。

2.1 地图渲染流程

先讲一点预备知识，电子地图涉及几种坐标系，每种坐标的计量单位如下：

• 经纬度是球面坐标，我们日常使用经纬度单位的是角度（deg），在进行投影计算时需要换算为弧度（rad）；
• 墨卡托投影得到的二维坐标单位是米（m）；
• 电子屏幕坐标的单位是像素（px）。

前端拿到的地图数据中绝大多数是墨卡托坐标，很小一部分是经纬度坐标。墨卡托或经纬度坐标需要先被换算成屏幕坐标，最后被CSS拼接或WebGL渲染。

这里的屏幕坐标准确的说应该是画布（canvas）坐标，前端常规认知的屏幕坐标是CSS坐标，在栅格地图中CSS坐标与canvas坐标是相等的，在矢量地图中根据屏幕的DPR值，CSS坐标与canvas坐标成倍数关系。

web地图的渲染流程大致如下：

地图在进入渲染流程之前有一些必要的前置条件：

• 地图level，可以从缓存中读取或者使用默认值；
• 地图的中心点坐标，可以通过浏览器的地理定位API获取，也可以从缓存中读取，如果都取不到，就必须有一个默认值；
• 浏览器画布的尺寸，如果是高清屏还需要DPR值。

以上几个条件的目的是为了计算地图当前的视野范围（bounds），进而计算出当前视野包含的瓦片编号列表。

栅格地图

前半部分介绍了瓦片切图，准确地说应该是「瓦片切割」，早期web地图使用的瓦片是一张张静态的png图片，前端开发者使用CSS position按照瓦片编号拼接成一张完整的二维地图。对前端来说，瓦片就等同于是图片，所以“瓦片切图”这个叫法一直被延续下来。

但地图数据本身是一个个坐标值并不是图片，之所以将瓦片保存为图片格式是因为早期的浏览器没有能够绘制海量数据的图形技术，也就是大家熟知的 WebGL。在这个前提下，地图厂商会在服务端搭建一套瓦片切图预处理的流程，简单理解就是先用 OpenGL 将地图数据可视化，然后按照既定的规则把每个 level的地图切割成一张张 256 * 256 的图片托管到静态文件服务器，最后前端开发者取图片拼接。以图片拼接而成的web地图叫做「栅格地图」。

注意上图里的切图服务中包含「瓦片-data」和「瓦片-png」，两者的内容一般是不同的。瓦片data的功能一方面是为了瓦片图片切割，另一方面是提供给其他支持矢量图形技术的平台使用，比如 app。

栅格地图的优点是：

• 前端的计算量非常小，性能相对高一点，对用户体验很友好；
• 浏览器兼容性很好，由于技术原始，所以很多老旧浏览器都能够兼容，比如搜狗的PC地图即便是现在也能在 IE5 里无bug运行（这可能是唯一值得吹一下的优点了~囧）。

基于以上两个优点，目前仍然有很多地图的JavaScript SDK使用栅格瓦片或者栅格混合矢量数据（一般是底图用栅格瓦片，建筑物和poi用矢量数据）的形式。不过栅格地图也有很明显的缺点：

• 相对于数据，图片的体积更大，储存成本相对更高一些；
• 位图是非矢量的，缩放会失真，视觉体验不佳；
• 基于上一条，每个瓦片图片都不能被相邻level共享，否则会严重失真，这进一步加大了图片数量和储存成本；
• 无法3D化。

矢量地图

随着大部分主流浏览器对 WebGL实现了支持，很多地图厂商都陆续开始研发并上线了矢量地图。矢量地图同样需要预处理的切图服务，但是预处理的产出并不是图片格式的瓦片，而是与app一样的瓦片data，换句话说，矢量web地图可以与app地图使用同一份数据，这意味着所有平台的地图数据可以统一维护和迭代。

“可以”的意思是可行但不一定，分业务场景。比如导航是app地图独有的功能，导航场景使用的地图数据称为“市街图-street map”，这些数据是web地图用不到的。

矢量地图说白了就是把原本OpenGL干的活交给了WebGL干，说起来简单做起来难，WebGL 是非常底层的图形编程技术，几乎没有任何上层封装，接近纯粹的计算机图形学。相关的研发人才非常稀缺，图形编程本身就是一个相对小众的垂直领域，WebGL 图形编程则更加小众，虽然同属于前端技术领域，但 WebGL 研发人员的招聘和培养难度比常规web前端研发人员要难很多，所以有能力开发 WebGL 矢量地图的厂商要么是有足够的人才储备想为产品锦上添花，比如高德和百度的WebGL地图第一个产品是自家的PC地图；要么是有充分的客户需求兑现商业价值，比如腾讯的WebGL地图第一个产品是B端的 JavaScript SDK（2020年初上线），截止到今天PC地图也没有接入WebGL。否则单纯靠爱发电很难落地，比如搜狗地图的WebGL引擎开发到80%的时候被叫停，之后再也没有捡起来过。

2.2 矢量地图与WebGL

WebGL 图形编程与常规web网站是完全不同的一套知识体系，虽然都使用JavaScript语言，但细节技术点完全不同，比如 WebGL 中被大量使用的 buffer、TypedArray、Protobuf等知识点在常规web网站中几乎不会被涉及，另外还有一套类似C++的shader语言-GLSL。这些细节知识点会在后续的文章中讲解，今天就简单科普一下WebGL的渲染管线以及WebGL矢量地图中常用的几种算法。

WebGL渲染管线

WebGL 是 canvas的一种渲染上下文（context），canvas有两种context：2D和WebGL。二者没有任何关系，相同点是都需要借助canvas输出图像。目前大部分浏览器都支持 WebGL1.0，对 WebGL 2.0 的兼容很不理想，下文的讨论都是针对 1.0 版本。

下面这段代码是创建WebGL 上下文的API以及几个常用配置项：

const canvas = <htmlcanvaselement>createElement('canvas'); const gl: WebGLRenderingContext = canvas.getContext("webgl",{ // 是否开启自动抗锯齿，建议关闭，浏览器兼容性差开了也没用，就算有用性能也很差(因为浏览器用的抗锯齿算法是效果很好同时性能很差的一种)，大多是自己写代码实现 antialias: false, // 是否开启透明通道，一般建议关闭，性能损耗严重，自己写代码根据透明值计算出混合色值更高效。如果开启的话，对研发人员的技术能力有更高要求 alpha: false, // 是否开启 stencil(模板) 缓冲区支持，数据量大的应用建议开启，配合stencil test能够减少无效渲染 stencil: true, // 是否开启 depth(深度) 缓存区支持，简易的webgl地图基本用不到depth test，一般是关闭的。像mapbox这类复杂的webgl地图引擎是开启的 depth: false });

WebGL 中有几个核心概念：

• shader – 着色器，分为两种：
  • vertex shader – 顶点着色器，用于确定图元顶点的坐标；
  • fragment shader – 片段着色器，用于处理光栅化之后的点阵像素信息，包括色值、透明度等等。

除了以上两种shader以外，OpenGL 还支持 geometry shader-几何着色器，不过也不常用。WebGL不支持几何着色器，

• program（没有准确翻译），用于绑定（attach）两种着色器。

基于上面的几个核心概念，WebGL 执行渲染的API调用流程是：分别创建两种shader -> 创建一个program -> 将program与两个shader绑定 -> 链接（link）program ->激活（use）program -> 传参给shader -> 传值&渲染。如下：

// 1.1-创建vertex shader instance const vShader:WebGLShader = gl.createShader(gl.VERTEX_SHADER); // 1.2-指定vertex shader源-vShadersStr，字符串格式 gl.shaderSource(vShader, vShadersStr); // 1.3-编译vertex shader gl.compileShader(vShader); // 2.1-创建fragmentshader instance constfShader:WebGLShader = gl.createShader(gl.FRAGMENT_SHADER); // 2.2-指定fragmentshader源-fShadersStr，字符串格式 gl.shaderSource(fShader,fShadersStr); // 2.3-编译fragmentshader gl.compileShader(fShader); // 3-创建program const program: WebGLProgram = gl.createProgram(); // 4-绑定program与两个shader gl.attachShader(program, vShader); gl.attachShader(program, fShader); // 5-链接program gl.linkProgram(program); // 6-激活program gl.useProgram(program); // 7-传值&渲染相关API下文再讲

接下来就是传值和执行渲染，这部分需要了解WebGL shader中的三种变量类型：

• attribute变量是由JavaScript API 传给顶点着色器的数据，术语为vertexBufferObject-VBO，顾名思义是一种二进制的buffer，在JavaScript中的表达是类型数组-TypedArray。根据精度的不同需求最常用的有Float32Array和Uint8Array。attitude主要是包含顶点坐标，但是并没有严格的限制，可以传递任何其他用途的数据，比如色值-color，前提是数据精度相同；
• uniform变量也是由JavaScript API传递给着色器，不过可以同时被顶点和片段着色器访问，通常用于传递所有顶点共用的数据，比如MVP矩阵（下文介绍）、画布分辨率、色值等等。uniform不是常量，着色器中有常量的定义规范-defined，语法类似C++如下：

#define PI 3.1415926538

• varying变量不是由JavaScript API传入着色器，而是在顶点着色器中根据其他数据（attribute/uniform/defined）计算出来，然后传递给片段着色器中同名varying变量。目的有两种：减少GPU的计算压力。因为顶点着色器只会计算指定图元的顶点数量，而片段着色器需要在图元覆盖的所有像素点都计算一次；片段着色器无法访问attribute数据，varying变量可以传递一些与attribute相关的数据。

结合上文的几种变量类型，WebGL的渲染流程大致如下图所示（条纹框表示GPU内部流程，开发者无法干预）：

1. 在CPU侧（也就是JavaScript侧）计算出必要的数据，包括VBO和uniform，然后传递给着色器；
2. 顶点着色器计算出制定图元的顶点坐标和必要的varying变量；
3. 接下来是开发者不可控的GPU内部逻辑，包括图元装配和光栅化：
   1. 图元装配：根据JavaScript调用的绘图API所指定的图元类型（点/线段/三角形）和顶点坐标组装成对应的几何图形；
   2. 光栅化：将装配好的几何图形转化为二维图像，图像中的每个点都对应一个物理像素点，叫做片元或片段（fragment）；
4. 片段着色器在图元覆盖的像素点依次计算出色值结果；
5. 接下来是测试混合（Test&Blending）阶段，之后会生成帧缓存FBO，这部分也是开发者不可控的；
6. 最后电子屏幕取帧缓存数据进行展示。

MVP矩阵

简单聊一下上文提到的 MVP 矩阵，细节的技术实现方案后续的分享中再说。

MVP 矩阵是仿射变换过程中三种变换矩阵的统称：

• M代表Model，Model矩阵即模型矩阵，可以简单理解为图形本身的变换矩阵，经过Model矩阵变换后得到顶点在世界空间中的坐标值；
• V代表View，View矩阵即观察矩阵，作用是将世界空间的顶点坐标映射到可以简单理解为摄像机（即观察者，camera是一个抽象对象）为中心的观察空间中；
• P代表Projection，Projection矩阵即投影矩阵，图形编程中两种投影方式：正向投影和透视投影。Projection矩阵的作用是将观察空间的三维坐标映射到二维的裁剪空间中，可以理解成将三维的图形投影到二维的画布上。

顶点的原始坐标需要依次经过Model矩阵、View矩阵和Projection矩阵变换（左乘）之后才能够得到它在裁剪空间中的最终坐标值。如下代码所示：

precision mediump float; attribute vec2 a_position; uniform vec2 u_resolution; uniform mat4 u_mMatrix; uniform mat4 u_vMatrix; uniform mat4 u_projMatrix; void main() { position = (u_vMatrix*u_mMatrix*vec4(a_position,0,1)).xy; gl_Position = u_projMatrix*vec4((position / u_resolution * 2.0 - 1.0)*vec2(1,-1), 0, 1); }

上面代码中的u_resolution是画布的尺寸，Model和View矩阵的数值一般是与画布的坐标使用相同的计量单位（px），Projection矩阵一般是归一化的矩阵。

三种矩阵在数学上没有区别只是计算逻辑上的三种抽象，都是4*4矩阵，都可以包含位移、缩放、斜切等形变信息。一般Projection矩阵是单独的，Model和View矩阵可以分开也可以在CPU侧计算之后得到一个Model&View矩阵再传入顶点着色器。

WebGIS常用算法

最后这部分介绍两种 WebGIS 领域常用的算法，准确地说应该是 WebGIS 绘图领域，一种是多边形三角剖分算法，一种是R-Tree算法。这两种算法与 WebGIS本身并没有太大关系，属于计算机图形学通用的算法。

三角剖分算法

计算机图形学中只有三种基本图元：点、线段、三角形。点和线段的适用面很窄，极少被使用，

绘图过程中绝大部分的图形底层都是一个个三角形组成的，如下图所示：

喜欢玩3D游戏的人可能知道，建模对游戏的视觉效果影响很大，除了模型本身的设计风格以外，建模的精细度也很重要，而衡量精细度的核心指标之一便是三角形的数量。虽然数量不是唯一指标，但细致的3D模型的三角形数量一定非常庞大，一般数量越多，模型的边缘越平滑，视觉效果越好。反面例子比如下图展示学动画三年系列，人物（姑且算是个人吧）模型边缘有非常明显的棱角，过渡非常不顺滑。

回到 WebGIS 领域，我们看到的电子地图是由一个个不规则的多边形（Polygon）和线（Line）组成，三角剖分算法的作用就是把这些多边形分割成一个个三角形，然后才能够被 WebGL 绘制出来。

其实线也是多边形，因为 WebGL 1.0 不支持宽于1像素的线，所以宽线必须以多边形的形式绘制。

三角剖分算法有两种类型，一种是多边形三角剖分，一种是点集三角剖分，后者在图形编程领域不常用，我们只需要关注多边形三角剖分。

三角剖分是典型的动态规划算法，对于多边形三角剖分最简单的场景就是三个点，也就是三角形，这种根本不需要分割。再复杂一点就是矩形，前端小伙伴们可以想像一下我们常用的 CSS盒子，html布局就是一个个矩形拼起来的，对于一个矩形来说需要2个三角形组成。然后依次再递增多边形的顶点个数，比如6个：

这时候需要4个三角形。

很细节的算法实现就不讲了，其实我也没搞太懂哈哈。对于前端工程师来说，从零实现这套算法的代价太大，更别提还要很细化地调优，我们直接使用经过大量实践验证的开源算法和工具就可以了。WebGL图形编程常用的三角剖分工具是Libtess，这套算法也是OpenGL编程常用的，非常高效。

R-Tree算法

R-Tree是一种树状数据结构，在 GIS领域主要用于空间数据的储存。在绘图方面，R-Tree较多地被用于图形冲突检测。

栅格地图的POI点坐标是在瓦片预处理过程中被计算好的，哪个显示哪个不显示都被预定义好了，前端拿到数据之后按照既定的坐标渲染出来即可。而矢量地图则不然，前文提到，矢量地图实际上就是让WebGL干了OpenGL的活，不单是绘图，绘图过程中的任何事情都变成了前端的事情，POI冲突检测就是其中一项。

先看下面这张图：

图中有两个POI点：微电子与纳电子学系（下文简称POI点A）和超导量子信息处理实验室（下文简称POI点B），每个点都有图标和文本两部分，点A和点B的文本都位于图标的下方。

POI有一个「权重-rank」的属性，绘图时要保障权重高的优先渲染，如果画布空间有限则要合理地调整低权重POI的布局甚至不渲染。仍然以上图为例，假设点A的权重高于点B：

1. 先渲染点A，图标必须渲染出来；
2. （伪）随机选一个方位放置文本，图中选的是图标下方；
3. 渲染点B，点B的图标与点A的图标和文本都不冲突，正常渲染；
4. 渲染点B的文本，可选四个方位-上下左右（复杂情况下可选八个方位），使用R-Tree描述文本的矩形盒子，检测发现上左右都会与点A的文本发生位置冲突，只有下方可行。

以上便是使用R-Tree进行位置冲突检测的简易流程。除了POI位置检测以外，绘图中R-Tree另一个使用场景是道路名称的位置标注算法，如下图中的「双清路」「荷清路」文本：

R-Tree冲突检测的开源工具推荐rbush。

POI的位置布局（POI Placement）算法也是单独的一项研究课题，有大量论文，大家有兴趣可以自行查阅相关资料。

其实R-Tree不仅仅适用于图形编程，在常规前端领域也有可借鉴的场景。比如下图展示的一个报表看板：

图中的布局乱了，报表之间存在遮挡情况，如果这种情形需要前端实现一个自动布局，也就是图中的「一键美化」功能，你可能考虑怎么办？

这时候就可以尝试用R-Tree解决，每个报表的容器都是一个个矩形盒子，使用rbush可以检测出所有矩形的冲突情况，然后再尝试自动调整布局直到rbush检测不冲突为止。R-Tree提供了一种解决思路和搭配的工具，在此基础之上可以进一步完善细化的布局调整逻辑。

三 总结

以上是今天分享的全部内容，简单总结一下。

第一部分介绍了 WebGIS 领域的一些基础知识，包括坐标体系、制图绘图流程和路网结构。对于日常工作中涉及地图的项目，对这些基础知识有个大概了解可以对工作有辅助作用比如技术评审。

第二部分介绍了两种地图类型以及矢量地图所使用的图形技术WebGL，简单分享了WebGL的渲染管线和常用的两种算法。电子地图不像游戏、动画等高复杂度图形应用对WebGL技术有很苛刻的要求，地图引擎顶多发挥了WebGL 三分之一的能力，我们日后在数据可视化方面的技术需求，可能涉及WebGL的部分甚至不如地图那么复杂，所以今天我们对WebGL先有一个大概的认知，后续再一步步学习内部的细节知识。