Spark

排序算法实践

2017-08-25T00:00:00+00:00

背景

数据结构和算法是程序员绕不过的坎儿。这两项是程序员的基本功，也是最考验编程思想的地方。单从概念上来讲，学习他们并不非常困难，真正的难处在于在编码过程中理解它、使用它。

冒泡排序

算法简述

冒泡排序的基本思路是将前后两个元素进行比较，较大的后移，较小的前置。这样，一次排序下来，最大的元素就被移动到了数组的最后一位，依次按以上逻辑循环。因此，冒泡排序的时间复杂度的最好情况是O（n），此时，数组本来就是正序排列，不需要排序，哈哈。最坏情况是O（nn），此时，数组是严格的倒叙排列。平均时间复杂度是O（nn）以下为冒泡排序的动图演示。

算法具体描述

具体算法描述如下：

<1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个； <2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； <3>.针对所有的元素重复以上的步骤，除了最后一个； <4>.重复步骤1~3，直到排序完成。

算法实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));

2017-8-27补充

–冒泡排序优化1

以上冒泡排序有可以改进的地方：冒泡排序每一次比较的目的都是为了找出最大值，将其放置到数组最后一位，然后下一次循环比较时，只比较前一次循环长度减一次，最后达到从小到大排列的顺序。假设某次循环的后半部分本来就是按照正序排列的，那么我们其实完全没有必要再进行比较，只需记录下最后一次交换数组元素的位置，比较其前面的元素大小即可（没有交换元素说明后面的元素都是按正序排列的），因此可以对冒泡排序进行优化，如下：

function bubbleSort2(arr) {
    console.time('改进后冒泡排序耗时');
    var i = arr.length-1;  //初始时,最后位置保持不变
    while ( i> 0) {
        var pos= 0; //每趟开始时,无记录交换
        for (var j= 0; j< i; j++)
            if (arr[j]> arr[j+1]) {
                pos= j; //记录交换的位置
                var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        i= pos; //为下一趟排序作准备
     }
     console.timeEnd('改进后冒泡排序耗时');
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort2(arr));

–冒泡排序优化2

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

function bubbleSort3(arr3) {
    var low = 0;
    var high= arr.length-1; //设置变量的初始值
    var tmp,j;
    console.time('2.改进后冒泡排序耗时');
    while (low < high) {
        for (j= low; j< high; ++j) //正向冒泡,找到最大者
            if (arr[j]> arr[j+1]) {
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        --high;                 //修改high值, 前移一位
        for (j=high; j>low; --j) //反向冒泡,找到最小者
            if (arr[j]<arr[j-1]) {
                tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
            }
        ++low;                  //修改low值,后移一位
    }
    console.timeEnd('2.改进后冒泡排序耗时');
    return arr3;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort3(arr));

#选择排序

##算法简介

选择排序是所有排序算法中最容易想到的。其基本思路就是循环比较所有的元素，每一次都找到数组中最小的元素，放置到队首，然后再从未排序的元素中找到最小的，放置到第二位，依次循环，直至排序完成。

##代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    console.time('选择排序耗时');
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));

结束语

一个个算法来吧，后续补充

人生得意须尽欢，莫使金樽空对月

2017-08-20T00:00:00+00:00

--题记

8月18日，临近下班时刻，正在收拾工作细节，准备下班回家，突然接到了诗文的信息，说是杨淑到了济南，要不要出去聚聚。我倒是丝毫没有犹豫，马上回复了‘好啊，周末有空’。毕业一年有余，好多同学大概也是有一年没见了。

19日上午，早起收拾了下屋子，便动身去317候车处候车。暑假的317路发车班次极少，幸得我手机里存有发车时刻表，倒是没有花费太多时间候车。车辆到站，车上的人极多，我‘左右冲突’，勉强登上公交车。

317仍是行驶的一如既往的快，四五十分钟便到了老校。中午11点，我准时到了恒隆广场，准备去约定地点会和。巧的是，方才到达恒隆广场，就看见诗文及杨淑从里面走了出来，后面还跟了一个面生的小兄弟。她们见到我也是极为惊讶，毕竟这确实是不曾预料的巧遇。经过介绍，我得知面生的小兄弟是杨淑的弟弟，才16岁。

既是相遇，便结伴同行。我们约定的地点是明湖四季餐厅，到达餐厅，报了房间号，服务人员便领着我们去到包间。我是第一次来明湖四季餐厅的，单看名字，我以为是地地道道的济南菜餐馆。一翻菜单，顿时有种目瞪口呆的感觉，清一色粤菜，偶尔穿插几个流传甚广的凉菜。疑问之下便向服务员询问，得知此处是一店两菜系，我们定的包间是粤菜菜系的。

既来之则安之，粤菜也是好吃的。粗略浏览一遍，我们便开始等人到齐。晌午，人员到齐。众人开始你一个我一个的点菜，不一会就点了一大桌子精美菜品。

大家吃一会儿聊一会儿，倒也甚是有趣。这次来的同学当中有的已是一年多未见面。谈及近来状况，也是变化颇大。有人读研、有人工作，各有所归。

饭后，众人分成两队。我与诗文、杨淑、金宵及鑫鑫带杨小兄弟去大明湖逛逛，聪敏和苗苗去恒隆。穿过芙蓉街，走过曲水亭街，到达大明湖。沿堤而行，景色宜人。上次来未曾开的荷花也是露出花朵，有粉的，有白的，煞是喜人。后面行程，大抵是遇桥上桥，遇林穿林，然后众人一同乘船到湖心小岛游玩，并从此处换乘五号船出了大明湖。

接下来，我们一行人到了宽厚里，游览早闻其名的‘萤火虫灯光展’。起初，我认为是真的萤火虫展览，后来经金宵和鑫鑫提示，得知其实是灯光展览。也是对自己的期待颇为无语。

灯光展分为两个展厅，我只去了第一个。里面大抵是大大小小的格子间，悬挂着满满的炫光灯，拍出照片倒也好看，只是我没有拍照的习惯。于是乎，我与杨小兄弟就在外面等待，女生则进去玩耍。

傍晚，众人安排行程，分道扬镳，各回各家。我因为要去老校坐车，便从世贸出发，沿着解放路前行。到了解放路与历山路十字路口，接到诗文电话，说是晚上要再聚一次。于是，走了一半红绿灯的我原路折回，引得交警同志一阵侧目。

回到世贸，却发现诗文父母也在。原来是叔叔阿姨来接杨淑和诗文回家，想着顺便与我们一起吃个便饭。可是，女生们想要去金宵和鑫鑫家开茶话会，几番商量之下，最终决定女生们去开茶话会，让杨小兄弟跟叔叔阿姨回槐荫，明天中午在火车站碰面。而我，也分得了一个艰巨的任务——帮忙照看杨小兄弟。

20号，众人在火车站送别杨淑姐弟。随后，金宵说要与鑫鑫一起去千佛山参加传说中的某聚会，一番商量之下，就变成了四人同行。

我是第一次来千佛山，想着上山看看。不巧鑫鑫穿的鞋子有所不便，于是便留下诗文与鑫鑫在山下等候，我与金宵上山观光。

可能是以前爬过两次泰山的原因，海拔258米的千佛山确实没什么难度，不消一小时，我们便上到山顶。此时，颇有种‘登泰山而小天下’的豪迈。山上视野很好，可以看到济南大部分城区，有点可惜的是天有雾霾，看的不甚清楚。山上有诸多庙宇，供奉神仙菩萨、罗汉佛陀。我们一一拜访，也算不枉上山一趟。游遍山上风景，我们便协同下山。下山途中路过万佛洞，顺道欣赏了一下没有山洞的万佛洞。

山脚会和众人，我们取道世贸，一起去吃了‘丸龟制面’，面汤浓郁，小菜也很爽口，觉得很是不错。而且，那种乌冬面的摆盘，总有种火影忍者一乐拉面的既视感，吃的也是很爽。

行文至此，已是结束了两天的行程。充实又满足，这是这两天最大的感受。我很少有乘兴而来，尽兴而归的时候，但是这次，不得不说，玩的真的尽兴。Thanks God I can choose my friends.

Openlayers2（4）Projection

2017-08-09T00:00:00+00:00

背景

笔者使用Openlayers有两年左右的时间了，一些常用的功能反反复复的使用过数遍，对一些功能的实现也有简单的了解。但是，学问不能止于此，有些概念仍然要多多学习。我对Openlayers的入门算是从这本《Openlayers Beginner》开始的，如今也想着返璞归真，重新阅读一遍原书，并尝试简单翻译。习笔拙作，难入法眼，在此贻笑大方了。

译文

When you look at a map, you are looking at a two dimensional representation of a three dimensional object (the earth). Because we are, essentially, ‘losing’ a dimension when we create a map, no map is a perfect representation of the earth. All maps have some distortion. The distortion depends on what projection (a method of representing the earth’s surface on a two dimensional plane) you use. In this chapter, we’ll talk more about what projections are, why they’re important, and how we use them in OpenLayers. We’ll also cover some other fundamental geographic principles that will help make it easier to better understand OpenLayers.

当你看一副地图的时候，实际上，你是在看一个三维物体的二维展示（此处的三维物体指的是地球）。因为我们创建地图的时候，本质上来说丢失了地球的一个维度，没有任何一张地图能够完美的呈现地球。所有的地图都有一些变形。这些变形取决于我们所选择的投影方式（投影是一种将地球三维表面展示在二维平面上的方法）。在这一章节中，我们将讨论什么是投影，为什么说投影很重要，我们如何在Openlayers中使用投影。我们也会涉猎一些基础的地理学原理，学习这些将会帮助你更容易的掌握好Openlayers。

In this chapter, we will cover:

Concept of map projections

Types of projections

Longitude, latitude, and other geographic concepts

OpenLayers projection class

Transforming coordinates

Let’s get started!

在这一章节，我们将会涉及到：

·地图投影的概念

·投影的种类

·经纬度及其他地理学概念

·Openlayers projection 类

·坐标转换

我们开始吧！

Map projections

No maps of the earth are truly perfect representations; all maps have some distortion. The reason for this is because they are attempting to represent a three dimensional object (an ellipsoid: the earth) in two dimensions (a plane: the map itself).

A projection is a representation of the entire, or parts of a, surface of a three dimensional sphere on a two dimensional plane (or other type of geometry).

地图投影

没有地图可以真实完美的展现地球；所有的地图都有一定的变形。产生变形的原因是：我们试着将一个三维的物体（一个椭球体：地球）展示为二维（一个平面：地图本身）。

投影是一种用来在二维平面上呈现整个或者部分三维空间物体表面的表现手法。

Why on earth are Projections used?

Every map has some sort of projection—it is an inherent attribute of maps. Imagine unpeeling an orange and then flattening the peel out. Some kind of distortion will occur, and if you try to fully fit the peel into a square or rectangle (like a flat, two dimensional map), you’d have a very hard time.

To get the peel to fit perfectly onto a flat square or rectangle, you could try to stretch out certain parts of the peel or cut some pieces of the peel off and rearrange them. The same sort of idea applies while trying to create a map.

There are literately an infinite amount of possible map projections; an unlimited number of ways to represent a three dimensional surface in two dimensions, but none of them are totally distortion free.

So, if there are so many different map projections, how do we decide on what one to use? Is there a best one? The answer is no. The ‘best’ projection to use depends on the context in which you use your map, what you’re looking at, and what characteristics you wish to preserve.

为什么使用投影？

每一幅地图都有一种投影，这是地图的固有属性。想象一下，剥开橘子皮，并将它展开。这时候橘子皮就会发生一些变形，如果你想让橘子皮完全符合正方形或者矩形的形状（比如一个平面的、二维的地图），你很难做到。

为了使橘子皮能够完美的契合到正方形或者矩形中，你可以试着撕下其中某些部分，或者剪下橘子皮的某一部分，重新排列组合。我们创建地图的时候应用的也是这种方法。

地图投影的方法有无数种，在一个二维平面上展示三维物体的手段也有无数种，但是没有一种是完全没有形变的。

所以，既然种类如此繁多的地图投影，我们应该如何决定使用哪一种投影呢？有没有一种投影是最好的投影？答案是否定的。‘最合适’的投影取决于你的地图的应用场景，你希望得到什么样的效果和你想保留地图的那些特性。

总结

spatialite实践（三）spatialite3.2版本后关于R*Index的修改

2017-08-05T00:00:00+00:00

背景

上一阵子笔者学习了spatialite，对其索引机制进行了略微深入一些的了解。也解决了上一篇学习笔记中提到的关于1.3版本以上的spatialite gui不能使用索引函数的问题。

总结

索引是个神奇的技术，位图索引、R树索引都是常见的索引技术，而我对此还没有深入实践，接下来有时间一定要尝试。

Andorid 获取发布版本及debug版本SHA1码

2017-08-01T00:00:00+00:00

背景

近期参与安卓项目开发，在app打包发布的过程中遇到了一些小问题：高德地图定位功能在真机测试时提示‘鉴权失败’，经排查，发现是app release版本与debug版本的SHA1码不同，导致高德密钥在真机上失效。于是便简单探究了有关app SHA1码的相关问题，记录如下。

Android Studio使用获取app release及debug版本的SHA1

1·在Android studio中查看项目的keystore

在Android Studio的build弹出菜单中，选择Generate Signed APK，可以看到该项目keystore的位置。

2·cmd（命令行）中获取SHA1

打开cmd，cd到keystore所在目录下，或者先打开keystore所在的文件夹，按住shift+鼠标右键，选择在此处打开命令行，输入

keytool -list -v -keystore keyStore.jks

再输入密码，此处输入的密码就是你的keystore的密码。就可以看到release 版本的的SHA1码。

注：最初，按照高德官方给出的SHA1获取教程一步步尝试，始终报错。最终发现是笔者弄错了命令行参数，误将-keystore的参数写成了 -key.store，应改为keyStore.Jks。下图为当时所报错误。

3·修改高德开发控制台的应用密钥

按照如图所示修改，即可获得在release版本下也可以使用的应用密钥。

参考资料

高德地图鉴权失败原因及解决方案

Android Studio 中高德地图申请key和获取sha1及配置的几点方法

Android Studio创建key-store的方法

结束语

权作记录

spatialite实践（二）spatialite R*Index 查询实践

2017-08-01T00:00:00+00:00

背景

空间查询是一种及其复杂的查询，无论是相交、邻接，还是包含关系，都需要进行复杂的图形位置计算，这对于cpu的消耗是极大地，查询的效率也是极低的。因此，我们需要借助于索引来进行查询相关的优化。

实践过程

场景描述

在spatialite中，根据手机实时定位数据，查询距离定位位置200m之内的建筑物面。下面将就是用索引与不使用索引的查询时间进行比较。

不使用索引

是用以下查询语句进行查询，与常规查询语句相似，但多了一些空间函数的使用。

SELECT ROWID, "PK_UID" as id, "X" as x, "Y" as y, "Geometry" as geometry,
	ST_Distance(Transform(MakePoint(f.x,f.y,4326),3857),
    	Transform(MakePoint(116.944,36.663,4326),3857)) as dis
FROM "fwm" as f
where dis<200
order by dis

MakePoint(f.x,f.y,4326) 是将一对x、y坐标包装秤坐标系为espg 4326的点数据结构。

Transform(MakePoint(f.x,f.y,4326),3857)是将点的坐标由4326转化为3857。我们知道，4326坐标系的单位是经纬度，3857坐标系的经纬度为米，要计算距离当然是米来的更直观。

ST_Distance(Transform(MakePoint(f.x,f.y,4326),3857), Transform(MakePoint(116.944,36.663,4326),3857))是计算两点之间的距离

这样整个语句就很明白了，下面我们来看看执行效果。

我们发现，以上的sql语句进行了全表扫描，共扫描了三万余行数据，效率非常低。共耗时4.5s，这对一次查询而言可以说是灾难了。

使用R*Index索引

使用以下语句进行查询，比较前一个sql语句，多了对索引表的查询。

SELECT ROWID, "PK_UID" as id, "Geometry" as geometry,X as x,Y as y,
	ST_Distance(Transform(MakePoint(x,y,4326),3857),Transform(MakePoint(116.944,36.663,4326),3857)) as dis
	FROM "fwm" as f
where f.id in(
	SELECT pkid
    	FROM idx_fwd_geometry
    	WHERE pkid MATCH RTreeDistWithin(116.944,36.663,0.01)
)
order by dis

spatialite若想利用空间索引，必须使用以下一句sql语句从索引表中查询，这与常规的sql查询是不同的。要注意，如果不查询索引表，即使在空间数据列上添加了空间索引，也不会对查询起到加速作用。

SELECT pkid FROM idx_fwd_geometry WHERE pkid MATCH RTreeDistWithin(116.944,36.663,0.01) 这一句是利用空间索引表进行一次过滤，筛选出某点周围1km左右的点的id集合。注意，此处的0.01是1/100 degree，大约相当于1000m。

按照如上语句查询，仅耗时0.2s就查询完成。

RIndex在海量数据时的表现

GIS行业总是与大数据量密切相关，不管是poi点数据、房屋面数据、人口数据还是交通路线，在一个市甚至一个省来讲，其体量都是巨大的。因此，GIS对数据库处理海量数据的能力有更高的要求。下面我们来测试一下50w数据量下spatialite的性能表现。

创建BUILD_AREA表，导入shp，用如下sql语句进行查询。

SELECT ROWID, "PK_UID" as id, "Geometry" as geometry,X as x,Y as y,
	ST_Distance(Transform(MakePoint(x,y,4326),3857),Transform(MakePoint(116.944,36.663,4326),3857)) as dis
	FROM BUILD_AREA as f
where f.pk_uid in(
	SELECT pkid
    FROM idx_BUILD_AREA_geometry
    WHERE pkid MATCH RTreeDistWithin(116.944,36.663,0.001)
)
order by dis

运行结果如下：

我们看到，经过空间索引过滤，即使是48w的数据量，我们进行某点周围一百米的查询仍可以做到0.2s返回。此处不得不感叹工程师们的鬼斧神工以及spatialite索引机制的玄妙。

总结

spatialite的空间查询优化是个需要耐心的工作，其中还有很多不明白的地方，这些语句多是根据spatialite cook总结的，其中仍有很多不明白的地方等待探索。

注：最新版本的spatialite gui不能使用空间索引函数，原因不明，需要使用spatialite cook中推荐的旧版本的spatialite gui才能正常使用空间索引函数。

spatialite gui旧版本下载地址

spatialite实践（一）spatialite资源汇总及基础用法

2017-07-31T00:00:00+00:00

背景

近期项目涉及到了使用patialite进行空间查询的内容，具体需求是：使用高德地图的定位功能实时获取用户位置信息，然后到spatialite数据库中查询距离当前位置最近的建筑物面，标绘在地图上，并返回该建筑物的位置信息。前几篇博客中提到的纠偏实践也是与此相关。

参考资料

spatialite资源列表 该网址包括我们开发过程中会使用到的大部分资料，包括文档、源码、编译后软件等等

spatialite cook spatialite cook，可以理解为spatialite的入门指南。外国人很喜欢把入门指南说成某某某 cook，将学习编程的过程比作做饭，著名的开源js地图软件Openlayers也有与之配套的《Openlayers cook》

spatialite gui spatialite的管理界面软件，提供了便捷的导入shp等格式的矢量文件功能，同时也提供了可视化的数据增删改查功能。

spatialite for android 适用andorid的spatialite使用指南。

spatialite android lib使用指南 一篇中文的spatialite for android 使用指南，包含了三方包的编译等，很详细，也提供了很多的资源下载。

Android Studio使用spatialite for android

1·引入三方包

在如下图所示的红框部分，创建或者拷贝相应的文件夹及文件

2·在程序中获得项目工程assets下的资源

使用官方提供的ActivityHelper和AssetHelper两个类，按照如下所示的代码，即可在android程序中访问assets文件夹下的数据库文件。MapConst类为自定义的常量类，MapConst.DB_NAME代表.splite后缀的数据文件的名字，也就是我们的数据库文件。

  private void initSqlLite(){
      try {
          AssetHelper.CopyAsset(this, ActivityHelper.getPath(this, false), MapConst.DB_NAME);
      } catch (IOException e) {
          ActivityHelper.showAlert(this,MapConst.ERROR_COPY_FAILED);
      }
      try {
          String dbFile = ActivityHelper.getDataBase(this,
                  MapConst.DB_NAME);
          Class.forName("jsqlite.JDBCDriver").newInstance();
          db = new jsqlite.Database();
          db.open(dbFile, jsqlite.Constants.SQLITE_OPEN_READONLY);
      } catch (IllegalAccessException e) {
          e.printStackTrace();
      } catch (InstantiationException e) {
          e.printStackTrace();
      } catch (ClassNotFoundException e) {
          e.printStackTrace();
      } catch (Exception e) {
          e.printStackTrace();
      }
  }

3·spatialite for android使用示例（以查询某点周围x米范围内的点为例）

sql语句的写法与常规sql并无多大区别，但是要注意一些空间函数的使用，会使你的查询语句变的很简洁。

  private void queryLocation(Double x,Double y){
      StringBuilder sqlBuilder=new StringBuilder("SELECT PK_UID as id, X as x, Y as y, AsText(Geometry) as geometry,");
      sqlBuilder.append("ST_Distance(Transform(MakePoint(f.x,f.y,4326),3857),");
      sqlBuilder.append("Transform(MakePoint(");
      sqlBuilder.append(x);
      sqlBuilder.append(",");
      sqlBuilder.append(y);
      sqlBuilder.append(",4326),3857)) as dis FROM fwm as f where dis<");
      sqlBuilder.append(MapConst.BUILD_BUFFER_DISTANCE);
      sqlBuilder.append(" order by dis");
      String querySql=sqlBuilder.toString();
      Log.i("sql statement:",querySql);

      List<BuildInfo> buildList=new ArrayList<BuildInfo>();
      try {
          Stmt stmt = db.prepare(querySql);
          while (stmt.step()) {
              BuildInfo build=new BuildInfo();
              build.setId(stmt.column_string(0));
              build.setX(Double.valueOf(stmt.column_string(1)));
              build.setY(Double.valueOf(stmt.column_string(2)));
              build.setGeometry(stmt.column_string(3));
              build.setDist(Double.valueOf(stmt.column_string(4)));
              buildList.add(build);
          }
          stmt.close();
          if(buildList.size()>0){
              BuildInfo build=(BuildInfo)buildList.get(0);
              if(build.getDist()>MapConst.BUILD_BUFFER_DISTANCE){
                  Log.i("info:","No build in "+MapConst.BUILD_BUFFER_DISTANCE+"meter buffer of current position.");
                  return;
              }else{
                  Log.i("info:",build.getId()+"-"+build.getDist());
              }
              System.out.println(build.getGeometry());
              MultiPolygon multiPolygon =transformWKT.getMULTIPOLYGONWktToJson(build.getGeometry(),4326);
              List<Double[]> rings=multiPolygon.getRings().get(0);
              LatLng[] path=new LatLng[rings.size()];
              int idx=0;
              for(Double[] lnglat : rings){
                  path[idx]=new LatLng(lnglat[1],lnglat[0]);
                  idx++;
              }
              if(marker!=null){
                  marker.remove();
                  marker.destroy();
                  marker=null;
              }
              if(polygon!=null){
                  polygon.remove();
                  polygon=null;
              }
              polygon=mapPainter.drawPolygon(path);
              marker=mapPainter.drawPoint(build.getX(),build.getY());
          }else{
              Log.i("info:","No build in "+MapConst.BUILD_BUFFER_DISTANCE+"meter buffer of current position.");
          }
      } catch (Exception e) {
          e.printStackTrace();
      }
    }

结束语

以上语句中并没有进行索引优化，这部分内容可以在spatialite cook中找到相应的介绍，这里不再赘述。近期项目赶得紧，空闲时间不多，介绍的不是很系统，只能等日后抽空再做补充。

网络上关于spatialite的中文资料不多，同志们还是多加学习英语，争取能无障碍阅读吧。

Arcgis 紧凑型瓦片格式解析

2017-07-29T00:00:00+00:00

Arcgis切片的两种形式

Arcgis切片分为两种文件组织形式:

松散型（Exploded），也就是我们常见的文件式的瓦片管理方式，将Arcgis Server切出来的瓦片图片按照行列号的规范，存储在相应的文件夹中。这种瓦片的管理方式很直观，能够可视化的查看瓦片文件。但是，文件式的文件管理方式有很大的弊端，当文件量达到一定级别时，它的检索、迁移效率会非常慢。同时，文件夹的管理方式使得文件与文件之间存在大量的空余，增加了存储文件所需的容量。

紧凑型（Compact）：紧凑型瓦片存储形式，是由Arcgis将切好的瓦片转化成以.bundle(Arcgis10.3以上，包括10.3)或者.bundlex(Arcgis10.3以下)的新文件。与松散型存储相比，它有迁移方便、创建更快、减少存储空间等诸多优点，已经成为了创建切片缓存的默认格式。

对于本身ArcGIS的产品而言，访问紧凑型存储与访问松散型存储没有任何区别，Arcgis内部会对其进行相应的处理。但是，如果第三方应用想访问新的切片格式，就需要自行解析bundle文件的格式。

官方回应不支持第三方应用使用bundle文件：

The internal architecture of the bundle is not publicly documented by ESRI. If you’ve coded your own logic to pull tiles out of a virtual directory, you should continue to use the “exploded” format which stores each tile as a single file and was the only option at ArcGIS Server versions 9.3.1 and previous.

紧凑型瓦片存储原理

Arcgis10.3以下

存储原理

紧凑型存储最主要的两种文件是bundle和bundlx文件，其中bundle文件用以存储切片数据，bundlx是bundle文件中切片数据的索引文件。

一个bundle文件中最多可以存储128×128（16384）个切片，但是创建切片缓存并不是一张张切片单独生成，而是以4096像素（无抗锯齿）或2048像素（有抗锯齿）为边长渲染的，如果我们选择的切片边长为256像素并开启了抗锯齿，那么每次ArcSOC进程创建的是一张以8×8（64）个切片拼接成的大图，然后切割后存入bundle文件中。下图中，蓝色边框代表的是bundle文件，黑色格子是生成切片时拼接的大图，具体的每个切片在黑色格子中，图中并没有显示出来。

存储格式分析

在分析紧凑型存储格式之前，我首先问自己，如果你要在一个bundle文件中存储内容，同时通过一个bundlx文件中存放索引应该怎么做？中规中矩的做法就是参考数据库的位图索引方式，在bundlx文件中用固定的几个字节标识一个切片在bundle文件中的状态（存储的偏移量和长度）。

观察ArcGIS生成的bundlx文件，每个文件都是一样的大小：81952字节。上面已经提到，每个bundle文件中最多存储16384个切片，虽然bundle文件中可能并没有这么多切片，但是，我猜测bundlx文件中必然是保留了所有者16384个切片的索引位置。粗略估计每个切片会占据大约5个字节，16384×5=81920字节，还多出32字节，猜测存储bundlx文件的标识信息。

通过对一个很存储切片很稀疏的bundlx文件的规律进行观察和猜测，确定了bundlx中文件起始16字节和文件结束16字节与索引无关，剩余的81920字节数据以5个字节的频率重复，构成了一个对bundle文件的索引。

本来以为这5个字节会保存bundle文件中切片数据的偏移和长度，但是发现5个字节表达的信息量可能不够，因此，我同时对bundle中的切片数据进行了一个分析。

我猜想文件并没有进行压缩处理，因此在文件中搜索PNG文件的文件头0x89504E47（我在创建缓存时选择了PNG24格式），发现果然如此。同时，每2个切片数据之间相隔了4个字节（切片数据我是用Exploded的图片直接进行比较的），通过猜想、尝试，发现这4个字节正好是以低位到高位的方式标示了后续这个切片数据的长度。

既然切片数据长度是在bundle文件中记录的，那么在bundlx文件中索引的必然只包括切片数据的偏移量，经过实验发现，bundlx中的5个字节也是以低位到高位的方式标示了数据的偏移量。

切片数据长度和数据偏移猜想应该是无符号的整数，后面的实践证明了这一点。还有一个问题，bundlx中的每5个字节标示的到底是哪个切片的数据偏移？实际上，bundlex中存储文件的顺序与bundle中的文件顺序是一致的。因此，我们如果知道了一个切片的级别、行号、列号，就可以通过bundlx首先找到bundle中切片内容的偏移，然后从bundle文件中取出4个字节的长度数据，再随后根据这个长度读取真实的切片数据。

代码实现（以java为例，使用了SpringMVC）

/**
   * 根据行列号从bundle及bundlx中取瓦片并返回
   * @param request
   * @param response
   * @param l
   * @param c
   * @param r
   * @throws IOException
   */
  @RequestMapping("/restBundlex/{l}/{r}/{c}")
  @ResponseBody
  public void getImageByRestBundlex(HttpServletRequest request, HttpServletResponse response, @PathVariable("l") int l, @PathVariable("c") int c, @PathVariable("r") int r) throws IOException {
      String level = Integer.toString(l);
      int levelLength = level.length();
      if (levelLength == 1) {
          level = "0" + level;
      }
      level = "L" + level;

      int rowGroup = 128 * (r / 128);
      String row = Integer.toHexString(rowGroup);
      int rowLength = row.length();
      if (rowLength < 4) {
          for (int i = 0; i < 4 - rowLength; i++) {
              row = "0" + row;
          }
      }
      row = "R" + row;

      int columnGroup = 128 * (c / 128);
      String column = Integer.toHexString(columnGroup);
      int columnLength = column.length();
      if (columnLength < 4) {
          for (int i = 0; i < 4 - columnLength; i++) {
              column = "0" + column;
          }
      }
      column = "C" + column;

      File bundleFile=new File("F:\\山东省16级\\sdBundlex\\Layers\\_alllayers\\" + level + "\\" + row + column + ".bundle");
      File bundlexFile=new File("F:\\山东省16级\\sdBundlex\\Layers\\_alllayers\\" + level + "\\" + row + column + ".bundlx");

      RandomAccessFile bundle= null;
      try {
          bundle = new RandomAccessFile(bundleFile,"r");
      } catch (FileNotFoundException e) {
          e.printStackTrace();
      }
      RandomAccessFile bundlex= null;
      try {
          bundlex = new RandomAccessFile(bundlexFile,"r");
      } catch (FileNotFoundException e) {
          e.printStackTrace();
      }

      int index=r*128+c;
      try {
          bundlex.skipBytes(16+5*index);
      } catch (IOException e) {
          e.printStackTrace();
      }
      byte[] indexBytes=new byte[5];
      try {
          bundlex.read(indexBytes,0,5);
      } catch (IOException e) {
          e.printStackTrace();
      }
      long offset = (long)(indexBytes[0]&0xff)
              + (long)(indexBytes[1]&0xff)*256
              + (long)(indexBytes[2]&0xff)*256*256
              + (long)(indexBytes[3]&0xff)*256*256*256
              + (long)(indexBytes[4]&0xff)*256*256*256*256;

      //获取切片长度索引并计算切片长度
      try {
          bundle.seek(offset);
      } catch (IOException e) {
          e.printStackTrace();
      }
      byte[] lengthBytes = new byte[4];
      try {
          bundle.read(lengthBytes, 0, 4);
      } catch (IOException e) {
          e.printStackTrace();
      }
      int length = (int)(lengthBytes[0] & 0xff) + (int)(lengthBytes[1] & 0xff)*256 + (int)(lengthBytes[2] & 0xff) * 65536
              + (int)(lengthBytes[3] & 0xff) * 16777216;

      //根据切片位置和切片长度获取切片
      ByteArrayOutputStream bos = new ByteArrayOutputStream();

      byte[] tileBytes = new byte[length];
      int bytesRead = 0;
      //文件字节长度小于3的大部分是空图片
      if(length > 3){
          try {
              bytesRead = bundle.read(tileBytes, 0, tileBytes.length);
          } catch (IOException e) {
              e.printStackTrace();
          }
          if(bytesRead > 0){
              bos.write(tileBytes, 0, bytesRead);
          }
      }
      response.setContentType("image/png");
      OutputStream tileImage = response.getOutputStream();
      tileImage.write(bos.toByteArray());
  }

Arcgis10.3以上

存储原理

2014年年底ArcGIS 10.3正式发布，Esri推出了新的紧凑型缓存格式以增强用户的访问体验。新的缓存格式下，关键的差别在于Esri将缓存的索引信息.bundlx包含在了缓存的切片文件.bundle中。

存储格式分析

既然缓存文件夹下仅包含了bundle文件，可以想见，切片的索引，切片的偏移和切片的图片流都必然包含在这一文件中。根据经验，缓存本身遵循的是16进制的形式。依照这一思路，利用UltraEdit打开bundle文件并以16进制格式进行查看。

为了便于分析，我们先创建一个在L00级只包含一个切片的缓存服务，并在UltraEdit中以16进制格式查看L00级下的R0000C0000.bundle文件。

通过对这一文件中信息存储规律的分析，可初步得出如下结论：(1) 文件中包含大量04 00 00 00 00 00 00 00的16进制字节组，共计16893组；(2) 文件中仅包含一个PNG24的文件头字节组89504E47，即第一行第一列的切片，bundle文件中唯一的一张图片。图片流紧随(1)中所提到的字节组之后，但偏移4个字节；(3) (2)中所述的4字节偏移量的数值恰等于图片流的长度；(4) 文件第5行的起始4个字节44 00 02 00按照低位到高位换算出的数值等于131140，这一值与(2)中所述的PNG文件头位置恰恰吻合。

　　综上分析：(1)起始4行是bundle的文件头信息，可忽略；(2)bundle的文件头之后记录了16384张切片的切片位置，仅4字节，从低位到高位，后4字节可忽略；(3)位置信息之后，对于切片的记录，先以4字节记录切片的长度，而后紧跟图片流信息。到此，bundle结束。

下一步呢，我们将选择一个狭长的矩形面要素发布服务并切图，以分析行列切片在bundle文件中的具体存储规律。

通过对bundle文件和对应的松散缓存在L02级别上的对比，可推断：(1)bundle中索引的存储是按行依次存储，即第1行的1至128，第2行的1至128，以此类推，直至最后一张切片即第128行128列；(2)bundle中图片流的存储仅包含非空切片。此外，通过对这一更复杂的地图缓存的分析，再次论证了前面的推论。

代码实现（以java为例，使用了SpringMVC）

/**
   * 根据行列号从bundle中取瓦片并返回
   * @param request
   * @param response
   * @param l
   * @param c
   * @param r
   * @throws IOException
   */
  @RequestMapping("/rest/{l}/{r}/{c}")
  @ResponseBody
  public void getImageByRestBundle(HttpServletRequest request, HttpServletResponse response, @PathVariable("l") int l, @PathVariable("c") int c, @PathVariable("r") int r) throws IOException {
      Long start=new Date().getTime();

      String level = Integer.toString(l);
      int levelLength = level.length();
      if (levelLength == 1) {
          level = "0" + level;
      }
      level = "L" + level;

      //Arcgis bundle的命名规则是以十六进制为基础的，所以首先要将行列号转变为十六进制
      //每个bundle存储128行，利用int类型不足1的部分自动省略的特性，r/128即可得到请求的瓦片所在的bundle的行号
      int rowGroup = 128 * (r / 128);
      String row = Integer.toHexString(rowGroup);
      int rowLength = row.length();
      if (rowLength < 4) {
          for (int i = 0; i < 4 - rowLength; i++) {
              row = "0" + row;
          }
      }
      row = "R" + row;

      //列号的计算原理同上
      int columnGroup = 128 * (c / 128);
      String column = Integer.toHexString(columnGroup);
      int columnLength = column.length();
      if (columnLength < 4) {
          for (int i = 0; i < 4 - columnLength; i++) {
              column = "0" + column;
          }
      }
      column = "C" + column;

      //根据上面计算的行列号，得到bundle文件
      String bundleFileName = "D:\\ArcgisTilesCache\\sdtf\\sdtf\\Layers\\_alllayers\\" + level + "\\" + row + column + ".bundle";

      //r - rowGroup计算的是请求的瓦片在bundle中处在第几行
      //c - columnGroup计算的是请求的瓦片在bundle中处在第几列
      //总起来看，这句代码计算出了所请求瓦片在bundle中的位置
      int index = 128 * (r - rowGroup) + (c - columnGroup);
      RandomAccessFile isBundle = new RandomAccessFile(bundleFileName, "r");


      isBundle.skipBytes(64 + 8 * index);
      //获取位置索引并计算切片位置偏移量
      byte[] indexBytes = new byte[4];
      isBundle.read(indexBytes, 0, 4);
      long offset = (long) (indexBytes[0] & 0xff) + (long) (indexBytes[1] & 0xff) * 256 + (long) (indexBytes[2] & 0xff) * 65536
              + (long) (indexBytes[3] & 0xff) * 16777216;

      //获取切片长度索引并计算切片长度
      long startOffset = offset - 4;
      isBundle.seek(startOffset);
      byte[] lengthBytes = new byte[4];
      isBundle.read(lengthBytes, 0, 4);
      int length = (int) (lengthBytes[0] & 0xff) + (int) (lengthBytes[1] & 0xff) * 256 + (int) (lengthBytes[2] & 0xff) * 65536
              + (int) (lengthBytes[3] & 0xff) * 16777216;

      //根据切片位置和切片长度获取切片
      ByteArrayOutputStream bos = new ByteArrayOutputStream();

      byte[] tileBytes = new byte[length];
      int bytesRead = 0;
      if (length > 0) {
          bytesRead = isBundle.read(tileBytes, 0, tileBytes.length);
          if (bytesRead > 0) {
              bos.write(tileBytes, 0, bytesRead);
          }
      }
      response.setContentType("image/png");
      OutputStream tileImage = response.getOutputStream();
      tileImage.write(bos.toByteArray());

      Long end=new Date().getTime();
      System.out.println(end-start+"ms,行列号："+l+"_"+r+"_"+c+",bundle_____________________________");
  }

参考

shp数据坐标系转换实践

2017-07-28T00:00:00+00:00

背景

关于shp数据的坐标转换问题，在上一篇博文中其实已经提过，但是语焉不详，估计难以看懂，所以特此补充一篇详细的转换过程博文，以供参考。

坐标转换过程中用到了‘使用ArcEngine移动Feature’的技术，受ArcEngine限制，该过程执行效率并不高，三万条数据大概处理了15分钟。此处提出一点建议：

可将移动polygon的操作另起一个线程进行，这样可以避免与主线程（绘制界面）竞争资源，提高执行效率，也避免了界面卡住。

实践过程

以下实践以polygon shp为例，个人认为polygon的坐标转换要比point和line难，所以以此为讲解素材。

在Arcgis中打开shp数据，并为shp数据添加x，y坐标属性（即添加图形要素的中心点坐标），具体操作如下：

右键点击table of contents中的图层，选择open attribute table，再点击如图所示按钮，选择Add field

弹出对话框按照如下填写，注意圈出部分，点击ok

同样的操作添加Y字段，结果如下：

右键点击X字段，选择Calculate Geometry

注意下面圈出两项的一致性

同理计算Y的坐标值

结果如图

接下来，使用ArcgisEngine开发包，解析shp并修改其数据，完成纠偏。代码如下：

private void movePolygon()
        {
            IMovePolygonFeedback m_MovePolygonFeedback = new MovePolygonFeedbackClass();
            IFeatureLayer pFeatureLayer = axMapControl1.get_Layer(0) as IFeatureLayer;
            IFeatureCursor pFeatureCursor;
            pFeatureCursor = pFeatureLayer.FeatureClass.Search(null, false);
            IFeature pFeature = pFeatureCursor.NextFeature();

            IWorkspaceEdit workspaceEdit;
            IWorkspace workspace;
            IDataset dataset = pFeatureLayer.FeatureClass as IDataset;
            workspace = dataset.Workspace;
            workspaceEdit = workspace as IWorkspaceEdit;
            //开始编辑（会开启一个session，消耗资源）
            workspaceEdit.StartEditing(true);
            workspaceEdit.StartEditOperation();

            while (pFeature != null)
            {
                int xidx = pFeature.Fields.FindField("X");//需与shp属性表中的字段对应起来
                int yidx = pFeature.Fields.FindField("Y");
                double x = pFeature.get_Value(xidx);
                double y = pFeature.get_Value(yidx);
                Console.WriteLine("原坐标：" + x + "_____" + y);
                IPoint preLocation = new ESRI.ArcGIS.Geometry.PointClass();
                preLocation.PutCoords(x, y);
                m_MovePolygonFeedback.Start(pFeature.Shape as IPolygon, preLocation);

                double[] convertLocation = projConvert.wgs84togcj02(x, y);
                Console.WriteLine("纠偏后坐标：" + convertLocation[0] + "_____" + convertLocation[1]);

                //修改xy字段值，改为纠偏后值
                pFeature.set_Value(xidx,convertLocation[0]);
                pFeature.set_Value(yidx, convertLocation[1]);

                //移动对象到当前位置
                IPoint desLocation = new ESRI.ArcGIS.Geometry.PointClass();
                desLocation.PutCoords(convertLocation[0], convertLocation[1]);
                m_MovePolygonFeedback.MoveTo(desLocation);

                IGeometry resultGeometry = m_MovePolygonFeedback.Stop() as IGeometry;
                pFeature.Shape = resultGeometry;
                pFeature.Store();
                pFeature = pFeatureCursor.NextFeature();
            }
            //结束编辑
            workspaceEdit.StopEditOperation();
            workspaceEdit.StopEditing(true);

            m_MovePolygonFeedback = null;
            MessageBox.Show("完成");   
        }

结果如图所示：

后话

此处仅仅是移动了shp数据的要素位置和修改了要素的坐标数据，并未在Arcgis中对其定义的投影坐标系进行修正，但经过检验，不影响数据的叠加使用，在修改投影坐标系方面如有需要，请自行搜索，网络上教程很多。

有时间会补充上openlayers加载高德地图叠加修正数据的例子。

看了《深夜食堂》之新餐具

2017-07-28T00:00:00+00:00

写完之后自己回头看了看，真是有点不忍卒读。说的文雅一点，就是“临表涕零，不知所言”，说的通俗一点，就是胡诌八扯，一派胡言。不过，毕竟是自己的博客，也就随手写写，当不得真。一些感悟权当牢骚，剩下的权当练笔，如此而已，仅此而已。 --题记

前一阵子看了很有名的美食剧《深夜食堂》，一共四季，我一口气看了三季。平心而论，这部日剧前三季，特别是第一季，拍的确实走心。在我的认知里，日版的《深夜食堂》突出了一个“静”字：老板在深夜独自备餐；食堂在众人都熟睡的深夜开门；每天都只有七八个人来吃饭等等。这一切都显得安静平和，抚慰人心。

夜是寂静的，街是寂静的，心也是寂静的。

每一集都是一个相对独立的小故事，每个人物都讲述自己的一段过往，每个人都彼此隔离却又有着千丝万缕的联系，所有的一切都在一个小小的食堂上演。

正如剧名《深夜食堂》所示，整部剧都是以“食”为线索，以一道菜引起你的回忆，那些回忆或许是一个人，或许是一件事物，也或许是自己的一段感悟。剧中的食物做得简单而朴实，看起来就像是一些家常菜一样。与剧中人物所表现的不同，我并不觉得哪些食物会有惊人的美味。食物仅仅是食物，真正让人沉醉的，无非是那些与食物相关的经历。

就像老妈做得鱼，无论吃几次都觉得是人间美味。其他人做得再好，在我尝来也不过尔尔。难道真的是大厨的厨艺不如我妈，并不见得，只不过是心理在作祟。

我这人没多少优点，唯一拿得出手的大概也就只有‘认真’二字。倒不是说我非常细心，只是很多事情只要我认定了，便会全心全意去做，如是而已。因此，看了《深夜食堂》，许久未有动静的“美食的心”又开始纯纯欲动。如果不是受困于一直以来的“老干部”形象，我一定要大喊一句：“美食王，我当定了！”

虽然我的厨艺不咋样，做得饭也不见得好吃，但是我还是做了很多尝试。所谓“书读百遍，其义自见”，我坚信任何事情只要付出努力去千百次的尝试，总会有掌握规律的一天。

Spark

排序算法实践

背景

冒泡排序

算法简述

算法具体描述

算法实现

结束语

人生得意须尽欢，莫使金樽空对月

Openlayers2（4）Projection

背景

译文

总结

spatialite实践（三）spatialite3.2版本后关于R*Index的修改

背景

相关资料

总结

Andorid 获取发布版本及debug版本SHA1码

背景

Android Studio使用获取app release及debug版本的SHA1

1·在Android studio中查看项目的keystore

2·cmd（命令行）中获取SHA1

3·修改高德开发控制台的应用密钥

参考资料

结束语

spatialite实践（二）spatialite R*Index 查询实践

背景

实践过程

场景描述

不使用索引

使用R*Index索引

RIndex在海量数据时的表现

总结

spatialite实践（一）spatialite资源汇总及基础用法

背景

参考资料

Android Studio使用spatialite for android

1·引入三方包

2·在程序中获得项目工程assets下的资源

3·spatialite for android使用示例（以查询某点周围x米范围内的点为例）

结束语

Arcgis 紧凑型瓦片格式解析

Arcgis切片的两种形式

紧凑型瓦片存储原理

Arcgis10.3以下

存储原理

存储格式分析

代码实现（以java为例，使用了SpringMVC）

Arcgis10.3以上

存储原理

存储格式分析

代码实现（以java为例，使用了SpringMVC）

参考

shp数据坐标系转换实践

背景

实践过程

后话

看了《深夜食堂》之新餐具