上一篇博文中,我讲了多边形注记点搜索算法的基本原理,本篇文章讲一讲如何用JS实现。

建议读者阅读本篇博文之前,一定要先了解上一篇博文中提到的算法原理。

函数接口

我们定义一个函数接口,接受一个多边形,计算其标注点:

1
2
3
4
5
6
function polylabel(polygon) {
// TODO
return [x, y]
}

module.export = polylabel

使用时,我们可以这样调用:

1
2
3
4
var polylabel = require('polylabel')

var polygon = [[[0, 0], [0, 1], [1, 1], [1, 0], [0, 0]]]
var point = polylabel(polygon)

对于polygon,我们采用geojson对多边形的坐标定义格式,即多边形由多个环组成,其中第一个环是外环,其他的为内环。所以polygon[0]表示第一个环,ploygon[0][0]表示起点坐标。

准备工作

在开始实现polylabel之前,需要一些辅助函数和库。

首先,我们定义网格对象Cell

1
2
3
4
5
6
7
function Cell(x, y, h, polygon) {
this.x = x // 中心点x
this.y = y // 中心点y
this.h = h // 中心点到网格的距离,相当于格网大小的1/2
this.d = pointToPolygonDist(x, y, polygon) // 中心点到多边形的距离
this.max = this.d + this.h * Math.SQRT2 // 网格内部区域到多边形的最大距离
}

定义网格对象的主要目的是方便求取最大距离this.max,有了网格对象Cell之后,每当我们实例化一个cell对象,我们就可以知道这个网格区域的最大距离以及它所代表的区域。

pointToPolygonDist是计算点到多边形的距离的函数,其基本原理是计算点到多边形每条边的距离,取最短距离即为点到多边形的距离。详细的算法实现我考虑专门用一篇文章来讲。

this.d + this.h * Math.SQRT2即为我们之前在算法原理中求得的最大距离dist + radius,由于格网是一个正方形,其外接圆形的半径即为中心点到任意一个顶点的距离,即this.h * Math.SQRT2

另一个需要准备的是一个优先级队列的数据结构,它与一般的队列不同在于,优先级队列中的元素都是经过排序的。每当push一个元素,并不是简单地将该元素放入队列末尾,而是会将该元素与队列中的元素进行比较,放到一个合适的位置上。

我们可以定义一个优先级队列,队列里存储的是格网对象。每push入一个格网,根据最大距离max进行排序,大的在前,小的在后。由此,我们可以分裂格网时,只需从队首pop出一个格网进行操作。

优先级队列的一个JS实现是tinyqueue,同样是Vladimir Agafonkin的作品。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
var Queue = require('tinyqueue')

function polylabel(polygon) {

// 计算bbox,为切分网格做准备
var minX, minY, maxX, maxY
for (var i = 0; i < polygon[0].length; i++) {
var p = polygon[0][i]
if (!i || p[0] < minX) minX = p[0]
if (!i || p[1] < minY) minY = p[1]
if (!i || p[0] > maxX) maxX = p[0]
if (!i || p[1] > maxY) maxY = p[1]
}

// 计算长和宽,初始格网大小和高度
var width = maxX - minX
var height = maxY - minY
var cellSize = Math.min(width, height)
var h = cellSize / 2

// 初始化一个存储Cell的优先级队列,按距离从大到小排列
var cellQueue = new Queue(null, function(a, b) {
return b.max - a.max
})

// 将多边形切分
for (var x = minX; x < maxX; x += cellSize) {
for (var y = minY; y < maxY; y += cellSize) {
cellQueue.push(new Cell(x + h, y + h, h, polygon));
}
}

// 取对首为最优格网
var bestCell = cellQueue.peek()

while (cellQueue.length) {
var cell = cellQueue.pop()

if (cell.d > bestCell.d) bestCell = cell

// 最大距离小于最优格网的距离,直接淘汰
if (cell.max <= bestCell.d) continue

// 将格网裂为4个小格网
h = cell.h / 2
cellQueue.push(new Cell(cell.x - h, cell.y - h, h, polygon))
cellQueue.push(new Cell(cell.x + h, cell.y - h, h, polygon))
cellQueue.push(new Cell(cell.x - h, cell.y + h, h, polygon))
cellQueue.push(new Cell(cell.x + h, cell.y + h, h, polygon))
}

return [bestCell.x, bestCell.y]
}

算法优化

上一节描述了多边形注记点搜寻算法的基本实现,我们还需要对其进行优化,提升算法效率。

为了提升效率,我们可以增加一个容差参数,允许最后的注记点有一定的误差,以减少运算次数:

1
2
// if (cell.max <= bestCell.d) continue
if (cell.max - bestCell.d <= precision) continue

另外,我们可以在初始时,用centroid作为初始最优点,因为大多数凸多边形的centroid就是最佳注记点:

1
2
// var bestCell = cellQueue.peek()
var bestCell = getCentroidCell(polygon)

当然,多变形的centeroid怎么求,估计又得用一篇博文来说了。

感觉给自己挖了好多坑。