多边形渐变色的实现

1. 相关概念

1.1. Drop shadow

1.2. Signed Distance Field（有向距离场）

1.3. Straight skeleton（直骨架）

渐变效果能够实现多种颜色之间的自然过渡，一般情况下，渐变往往与某种场强度相关，或者说某一个在二维空间内连续变化的数值相关，比如某片地区的气温，海拔高度，一条路径的畅通程度。地图中常见的渐变效果是热力图，分层设色也算渐变吧，只要分的够多。

渐变色也能用于实现阴影的效果，也就是从灰色过渡为透明的形式，从而使得 2D 的地图更加立体。下图是 iOS 中地图应用的截图，右上角的控件实际上就有阴影，用于与地图做区分。仔细观察的话，地图中水系的边缘也是有向内的阴影的，用于与陆地做区分。

CSS3 的渐变效果在地图中的应用也是有的。比较常见的方式是，先将 CSS3 的径向渐变效果绘制在 canvas 上，再将 canvas 叠加到地图上。这样可以实现圆形的渐变效果，可以用于展示点的缓冲区范围。

然而问题在于，CSS3 的径向渐变只能以圆形或者方形呈现，碰上不规则的多边形，效果就不是那么好看了。以下图为例：圆形的渐变效果贴在了各个行政区的表面，但是与行政区的轮廓不匹配。

在一些桌面端的 GIS 软件中，是有多边形渐变的效果的，比如 QGIS。在 QGIS 里这一效果叫“shapeburst fill”。用来突出显示一个区域，或者显示水系的阴影。

相关概念

在寻找多边形渐变的实现方案时，我了解到一些相关概念，在此记录一下。

Drop shadow

根据维基页面，drop shadow 是一种能够让对象看起来像是被抬升的效果，常用于窗口或者菜单这样的图形交互界面。能够有效的让文本或者图标看起来与背景做区分。下方的示例是 CSS 中 drop-shadow() 的效果。

drop-shadow 比 box-shadow 能够更好的处理不规则多边形的情况。

Signed Distance Field（有向距离场）

不同几何形状的 SDF，可以参考这篇文章：https://iquilezles.org/articles/distfunctions2d/

下面是多边形的 SDF 可视化的结果。SDF 的关键在于计算屏幕上的各个点到对象的最短距离。对于规则的多边形而言，计算可以通过公式完成，但是对于任意形状的多边形，这样的计算开销就有点大了。

下面是每个点的距离计算方式。

float sdPolygon( in vec2[N] v, in vec2 p )
{
    float d = dot(p-v[0],p-v[0]);
    float s = 1.0;
    for( int i=0, j=N-1; i<N; j=i, i++ )
    {
        vec2 e = v[j] - v[i];
        vec2 w =    p - v[i];
        vec2 b = w - e*clamp( dot(w,e)/dot(e,e), 0.0, 1.0 );
        d = min( d, dot(b,b) );
        bvec3 c = bvec3(p.y>=v[i].y,p.y<v[j].y,e.x*w.y>e.y*w.x);
        if( all(c) || all(not(c)) ) s*=-1.0;  
    }
    return s*sqrt(d);
}

很多文章也提到了 SDF 在光照，阴影方面的用途，这个之后有机会再展开讲。

Straight skeleton（直骨架）

可以先来看一下多边形直骨架的定义：

从每一条多边形的轮廓边上向多边形内部穿过一个三维的平面，所有的这些平面与多边形的夹角都是相等的，比如：45度，这些平面在三维空间上相交，相交所产生的三维的包围多面体上的边就相当于是多边形的屋顶的棱（可以认为原简单多边形是你家房子的墙壁，然后所生成直骨架就相当于你家的屋顶），然后包围多面体上的所有边和顶点在原简单多边形上进行投影，投影所得到的点和边就是简单多边形的骨架边和骨架顶点。

多边形直骨架和多边形渐变有什么关系呢？多边形的直骨架的生成结果，加上线性的渐变后，能够实现多边形渐变的效果。

多边形直骨架在 GIS 上的应用还有很多，例如：提取多边形的中心线，进而解决多边形内部文本摆放的问题。或者由上方定义可以联想到，多边形直骨架可以用于3D房屋屋顶的生成，或者地形的生成。

实现方案

最终采用了多边形直骨架的方案。多边形直骨架能够更好的应对复杂的多边形，例如带孔多边形以及非凸多边形。SDF 的方案在面对大数据量时，计算效率不高。至于在 canvas 上实现 shadow 效果，限制太多，不适用于地图的场景。

直骨架也存在一些缺点，例如：大于180°的角所产生的直骨架线会很长，这一点和绘制带宽度的线类似，需要处理线段拐角的情况。从右边的对比图中可以看出，SDF 输出的是圆形拐角，直骨架算法输出的是尖角形拐角。

可以在直骨架算法输出的基础上做些修改，实现类似圆形拐角的效果。依次检查大于 180° 的轮廓顶点，过轮廓顶点做轮廓边的垂线，与内部平分线相交，会产生如下图中所示的淡蓝色的多边形（不一定是三角形），淡蓝色的多边形实际上就是需要处理成圆角的区域，此时需要对淡蓝色多边形做进一步的拆分，并重新计算顶点值即可。

这套方案并不完善，尤其是当尖角形状干扰到对面的边时，会导致最终的输出结果看起来缺了一块。

最终效果

右边的是给 water 图层加了阴影效果的地图，可以和左边的对比一下。

算法不太稳定，水系的阴影效果在拖动地图后不一定能加载出来。

后续优化

算法效率。这应该是阻挡这一效果在 Mapbox 中落地的很重要的一个因素吧。
现有库的稳定性，现有的 Javascript 版本的直骨架计算库都存在一些问题，从项目的 issue 中就可以看出来了。当然也可以尝试下将 cgal 编译为 wasm 来解决。
和矢量瓦片结合的问题，如何在数据被切分后，依旧保持效果的完整性？

多边形渐变色的实现