數據抽稀演算法
❶ Mysql的GIS、GEO入門筆記
探索和學習MySQL中GIS相關功能和特性
這里記錄了學習和了解MySQL中GIS特性相關內容的過程。
MySQL官方論壇中GIS的舉例
測試數據已經導入成功，下面開始對GIS相關函數和GEOHASH進行了解和體驗；
mysql中geometry類型的簡單使用
MySQL空間數據類型
經緯度信息存儲在geometry格式的欄位中，該欄位必須非空。
MySQL8.0前按照longitude-latitude的順序存儲位置
MySQL8.0前按照longitude-latitude的順序存儲位置
MySQL8.0前按照longitude-latitude的順序存儲位置
插入數據時候可使用如下語句：
MySQL存儲geometry信息的方式採用了25bytes，相比WKB的21bytes，多了4bytes的坐標系表示，組成部分如下：
WTF字元串格式說明
select ST_GeomFromText(WTF格式字元串);
WKT(Well-known text)是一種文本標記語言,用於表示矢量幾何對象、空間參照系統及空間參照系統之間的轉換。通過WTF字元串生成geometry的方法：
點： POINT(x y)
線： LINESTRING(x1 y1, x2 y2, x3 y3...)
多邊形： POLYGON((0 0, 10 0, 10 10,0 10,0 0),(5 5,7 5,7 7,5 7,5 5))
多點集： MULTIPOINT(0 0, 20 20, 60 60) 或 MULTIPOINT((0 0),(5 5),(5 0))
多線集： MULTILINESTRING((10 10, 20 20), (15 15, 30 15))
多多邊形集： MULTIPOLYGON(((0 0,10 0,10 10,0 10,0 0)),((5 5,7 5,7 7,5 7, 5 5)))
例如兩點一線組成的幾何集： GEOMETRYCOLLECTION(POINT(10 10), POINT(30 30), LINESTRING(15 15, 20 20))
A geometry is syntactically well-formed if it satisfies conditions such as those in this (nonexhaustive) list:
Collections are not empty (except GeometryCollection)
更多內容參見
ST_PointFromText('POINT(X Y)');
ST_LineStringFromText('LINESTRING(0 0,1 1,2 2)');
ST_PolygonFromText('POLYGON((0 0,10 0,10 10,0 10,0 0),(5 5,7 5,7 7,5 7,5 5))');
ST_GeomCollFromText();
更多內容參見
參見
Point(x,y)
LineString((x1,y1),(x2,y2)...)
Polygon(LineString(),LineString()....)
參見
ST_AsText()
ST_AsBinary()
ST_AsWKT()
參見
ST_Dimension(geom) ：返回geom的維度（-1，0，1，2）
ST_Envelope(geom) ：返回geom的最小外接矩形（MBR）
ST_GeometryType(geom) ：返回geom的類型
ST_IsEmpty(geom) ：該函數並不能真實的判空，當geom為任何有效的幾何值時返回0，無效的幾何值返回1；
ST_IsSimple(geom) ：當geom無任何異常幾何點返回1（如自相交和自切線等），否則返回0
ST_SRID(geom) ：返回geom的坐標系ID
參見
ST_X(Point) ：獲取Point的X值
ST_Y(Point) ：獲取Point的Y值
參見
ST_StartPoint(linestrng) ： 線的起點
ST_EndPoint(linestring) ：返回線的最後一個點
ST_IsClosed(linestring或multilinestring) ：線是否閉合（若為線，則判斷起點與終點是否一致；若為線組，則判斷組內每個元素是否符合閉合線）
ST_Length(linestring) ：返回線的長度，若入參為線集，則返回集合內所有長度的和
ST_NumPoiints(linestring) ：返回點的數量；
ST_PointN(linestring,N) ：返回第N個點（從1開始）
參見
具體不在一一列舉，主要有計算多邊形面積、中心點、最小外接圓，最大內接圓等函數，列舉幾個可能會用到的：
ST_Area(Poly|mPoly) ：返回雙精度的面積或面積的和
'ST_Centroid(Poly|mPoly)'：返回數學上的中心點
ST_ExteriorRing(Poly) ：返回外接圓
參見
ST_Buffer說明
不再列舉，主要有：ST_Buffer（不懂幹啥用），ST_ConvexHull(geom)凸包，ST_Dfference(g1,g2)比較差異，ST_Intersecton(g1,g2)交叉點，ST_SymDifference(g1,g2)對稱差分，ST_Union(g1,g2)連接、合並等。
檢查geometry Objects之間的空間關系的方法。
參見
計算兩個Object之間的空間關系的函數，有兩個間距離、相交、不相交，包含、相等、相切、重疊、接觸、在內等等空間關系。下面列舉幾個可能會常用的方法：
ST_Contains(g1,g2) ：g1是否完全包含g2
ST_Within(g1,g2) ：g1是否包含於g2中
ST_Distance(g1,g2) ：返回g1和g2之間的距離，已坐標單位計算的
ST_Equals(g1,g2) ：返回g1和g2是否相等
參見
MBRContains(g1,g2) ：g1的mbr是否包含g2的mbr
MBRWithin(g1,g2) ：g1的mbr是否在g2的mbr內
MBRCoveredBy(g1,g2) ：g1的mbr是否被g2的mbr覆蓋
MBRCovers(g1,g2) ：g1的mbr是否覆蓋g2的mbr
MBRDisjoint(g1,g2) ：g1的mbr,g2的mbr是否不相交
MBRIntersects(g1,g2) ：g1mbr，g2mbr是否相交
MBREqual(g1,g2) ：g1的mbr,g2的mbr的外接是否相等
MBREquals(g1,g2) ：g1的mbr,g2的mbr的外接是否相等
MBROverlaps(g1,g2) ：g1mbr、g2mbr
其他函數請參看原文
GeoHash介紹
GeoHash Wiki網路
MySQL中自帶函數 st_geohash(longtude,latitude,max_length) 或 st_geohash(point, max_length) 即可生成某一點的geohash值。
返回一個geohash字元串中的latitude或longitude
返回一個geohash解析出的point數據
官方文檔
通過geometry生成一個GeoJSON Object， select st_asgeojson(geometry,max_length,options);
通過GeoJSON生成GeoMetry對象。
ST_GeomFromGeoJSON(jsonstring, [options [, srid]])
具體使用方法參見官方文檔
官方文檔
MySQL中提供的方便空間運算的函數們
select ST_Distance_Spher(geomPoint1,geomPoint2 [, radius]);
此方法用於計算兩點或多個點之間的地球上的距離（是地球球面距離而不是直線距離），返回單位為米，
select ST_IsValid(ST_GeomFromText('LINESTRING(0 0,1 1)'))
判斷入參是否是符合地理位置描述的格式。返回1（符合）或者0（不符）；
例如：
返回0：
select st_isvalid(st_geomfromtext('linestring(0 0, -0.00 0, 0.0 0)')
返回1：
select st_isvalid(st_geomfromtext('linestring(0 0,1 1)')
select st_astext(st_makeenvelope(pt1, pt2));
返回兩點構成的包絡。（此計算是基於笛卡爾坐標系而非球面）
例如：
SELECT ST_AsText ( st_makeenvelope ( st_geomfromtext ( 'point(0 0)' ), st_geomfromtext ( 'point(1 1)' ) ) );
返回結果：
POLYGON((0 0,1 0,1 1,0 1,0 0))
效果說明
JS抽稀演算法
select st_simplify(geometry, max_distance);
用道格拉斯-普克演算法（抽稀函數）簡化geometry，並返回與原格式相同格式的結果。
例如，以下點集擬合為直線，步長0.5：
SELECT st_simplify ( st_geomfromtext ( 'LINESTRING(0 0,0 1,1 1,1 2,2 2,2 3,3 3)' ), 0.5 )
返回結果：
LINESTRING(0 0, 0 1, 1 1, 2 3, 3 3)
再如，步長1.0：
SELECT st_simplify ( st_geomfromtext ( 'LINESTRING(0 0,0 1,1 1,1 2,2 2,2 3,3 3)' ), 1.0 )
返回結果：
LINESTRING(0 0, 3 3)
SELECT ST_Validate(geometry);
驗證geometry是符合正確的地理位置信息格式。例如 Point(0 0) 是合格的； Linestring(0 0) 是非法的； Linestring(0 0, 1 1) 是合格的
了解了上述MySQL中關於集合對象的功能，下面來實踐一下
由上面geohash長度-精度對應表可知，前6位表示±610米左右的誤差，這里先查詢前六位范圍之後再用上述方法精確篩選一次即可：
可將上述查詢方法封裝為MySQL函數方便和簡化程序調用.
該方法是運用了內置的幾何關系運算函數 ST_Contains 和 ST_MakeEnvelop 來實現的，0.5對應大概500米左右的范圍，具體如下；
鏈接: https://pan..com/s/1cW-kv6DIgtYMw5I3bNFzKA
❷ GPS軌跡抽稀：Douglas-Peuker演算法
在對行車軌跡在地圖上進行展示時，往往需要繪制大量的坐標點，但是設備取點的間隔往往是固定的，傳統的做法是將所有的點繪制出來，極大地消耗了瀏覽器的性能。然而在一條軌跡上，兩點便可以確定一條直線，因此在行駛路徑比較直的區域，很多坐標點都是可以舍棄的，同時，當對地圖進行縮小，使可視區域變大時，坐標點也不必繪制地十分精確，往往取一些關鍵點就能繪制出行駛軌跡。 Douglas-Peuker 正是一個對坐標關鍵點進行抽取的演算法。
1. 將軌跡的首尾點連成一條線，計算曲線上每一個點到直線的距離，找出最大距離 dmax ，看距離是否小於給定的閾值 max （及軌跡精確度）。
2. a.若 dmax < max ，則舍棄這條曲線上的所有中間點，將曲線首尾點連成的直線作為這段曲線的近似，這條線段便處理完畢。
b.若 dmax >= max ，則以 dmax 所在點作為分割點，將原來的曲線分為兩段，分出來的兩條曲線繼續直線步驟1、2，直到所有的 dmax < max 。
顯然，演算法的抽稀精讀是和閾值相關的，閾值越大，舍棄的點越多，提取的關鍵點越少。若繪制的軌跡較長，可在對地圖進行縮放時動態調整閾值。
數據點類型為類似 30.664147,104.067232 ，抽稀閾值為 0.000005 ，第一張圖為原始gps數據，共265個點，第二張圖為抽稀之後的數據，共108個點。