[Rust开发]在Rust中使用geos的空间索引编码实例

news/2024/11/20 7:06:32/

geos的空间索引用的是STRTree,这是一种基于STR算法的四叉树索引,有如下特点:

  • 使用Sort-Tile-Recursive (STR) 算法创建的仅查询的R-tree空间索引

STR(Sort-Tile-Recursive,递归网格排序) 基本思想是将所有的矩形以“tile”的方式分配到r/n(取上界)个分组中,此处的tile和网格类似。

此算法易于实现且适用范围较广,在大多数场景下表现良好,且易于推广到高维空间。

按照MBR中心点第一维坐标对数据点进行排序,利用S=sqrt(N/b)个垂直slice切割数据空间,使每个slice包含S个节点和S*b个MBR;

在每个垂直slice中,按照MBR中心点第二维坐标进行排序,每b个MBR一组压入节点;

递归进行上述步骤,直至生成整个RTree,每个slice的MBR数据不超过b。

图片

  • 该树索引每个几何图形的边界框。树在初始化时直接构建,且一旦创建后不能添加或移除节点

  • 所有操作返回输入几何图形的索引

  • 边界框限于二维并且是轴对齐的

    • 几何图形中存在的任何Z值在树内索引时都会被忽略。

注意:使用STRTree索引的话,只会构建几何的外接矩形边界为索引区域,所以计算两个几何的时候,仅进行外接矩形相交判定,官方原文如下:

图片

https://libgeos.org/usage/c_api/

在c/cpp中,该空间索引支持相交查询和距离查询,在Rust的geos绑定中,目前仅实现了相交查询。

具体使用方式如下:

rust">let mut tree = STRtree::<&str>::with_capacity(10).unwrap();let point = Geometry::new_from_wkt("POINT(5 5)").unwrap();
let line = Geometry::new_from_wkt("LINESTRING (0 0, 10 0)").unwrap();
let polygon = Geometry::new_from_wkt("POLYGON((2 2, 8 2, 8 8, 2 8, 2 2))").unwrap();//insert可以把把几何要素放入空间索引中,附带一个唯一标识
tree.insert(&point, "Point");
tree.insert(&line, "Line");
tree.insert(&polygon, "Polygon");//对tree进行迭代,相当于把里面item(也就是标识)给迭代出来了。
tree.iterate(|item|println!("{}", item));//做查询的时候,实际上也是一个闭包迭代器,可以选择把命中的数据扔到一个hashset里面
//也可以直接在命中的流程中直接进行处理。
let mut items = HashSet::<&str>::new();
tree.query(&point, |item| {items.insert(*item);
});

注意,直接query,仅进行外接多边形判定,如下:这两个三角形本身是不想交的,但是它们的外接矩形是相交的

图片

rust">let mut tree = STRtree::<&str>::with_capacity(10).unwrap();let poly1 = Geometry::new_from_wkt("POLYGON((12 360, 360 360, 12 100, 12 360))").unwrap();
let poly2 = Geometry::new_from_wkt("POLYGON((12 90, 390 350, 390 100,12 90))").unwrap();//insert可以把把几何要素放入空间索引中,附带一个唯一标识
tree.insert(&poly1, "poly1");
tree.insert(&poly2, "poly2");
tree.query(&poly1, |item| {println!("{:?}", item);
});assert_eq!(poly1.intersects(&poly2).unwrap(), true);

查询和相交判定的结果分别如下:

空间索引查询判定通过(poly1与自身,以及与poly2都查询到了),但是相交触发了断言,判定失败

所以,空间索引仅是通过外接矩形进行判定,如果要精确的进行空间关联判定,就需要在进行二次过滤,代码如下:

rust">let mut tree = STRtree::<&str>::with_capacity(10).unwrap();
//定一个hashmap来承载所有数据
let mut poly_hash = HashMap::<&str,Geometry>::new();let poly1 = Geometry::new_from_wkt("POLYGON((12 360, 360 360, 12 100, 12 360))").unwrap();
let poly2 = Geometry::new_from_wkt("POLYGON((12 90, 390 350, 390 100,12 90))").unwrap();//insert可以把把几何要素放入空间索引中,附带一个唯一标识
tree.insert(&poly1, "poly1");
tree.insert(&poly2, "poly2");poly_hash.insert("poly1",poly1.to_owned());
poly_hash.insert("poly2",poly2.to_owned());tree.query(&poly1, |item| {//进行二次判定if poly1.intersects(poly_hash.get(*item).unwrap()).unwrap() {println!("{:?}", item);}
});

结果如下:

空间查询使用索引进行预先过滤,可以在查询结果量级不大的情况下,极大的提高效率。

下面通过一个例子来进行效率对比:

这是一个300 对 6万空间关联查询

图片

前景红色黑边的查询用的图层,后面灰度的是target图层。

核心代码如下:

读取数据

rust">//功能说明略
fn get_geometry_by_shp(shp:&str)->HashMap<i64,Geometry>{let shp = shapefile::read_as::<_,shapefile::Polygon, shapefile::dbase::Record>(shp,).expect("Could not open polygon-shapefile");let mut h:HashMap<i64,Geometry> = HashMap::new();for (polygon, polygon_record) in shp {let poly: geo::MultiPolygon<f64> = polygon.into();let geom = geos::Geometry::try_from(poly).unwrap();for record in polygon_record{if record.0 == "OBJECTID"{let oid = match record.1{FieldValue::Numeric(Some(s)) => s as i64,_=>0 as i64};h.insert(oid,geom.to_owned());}}}    h
}

使用空间索引的空间关联方法

rust">fn test_spindex_demo_useidx()->HashMap::<i64,HashSet<i64>>{let target = get_geometry_by_shp("E:\\data\\dltb\\dltb6w.shp");let query_lyr = get_geometry_by_shp("E:\\data\\dltb\\dltb300.shp");let mut tree = STRtree::<i64>::with_capacity(target.len()).unwrap();let start = SystemTime::now();//构建空间索引for (oid, geom) in target.iter() {tree.insert(geom,*oid);}let mut res = HashMap::<i64,HashSet<i64>>::new();//用query_lyr图层,逐个进行迭代关联//内层先用tree进行索引过滤一次for q in query_lyr.iter(){let mut items = HashSet::<i64>::new();tree.query(q.1, |item| {let tr_geom:&Geometry = target.get(item).unwrap();if q.1.intersects(tr_geom).unwrap(){items.insert(*item);}});res.insert(*q.0, items);}let end = SystemTime::now().duration_since(start);println!("use index 计算完成 {:?}",end); res
}

不用空间索引的方法

rust">fn test_spindex_demo_nouse() ->HashMap::<i64,HashSet<i64>>{let target = get_geometry_by_shp("E:\\data\\dltb\\dltb6w.shp");let query_lyr = get_geometry_by_shp("E:\\data\\dltb\\dltb300.shp");let start = SystemTime::now();let mut res = HashMap::<i64,HashSet<i64>>::new();//用query_lyr图层,逐个进行迭代关联//直接暴力迭代for q in query_lyr.iter() {let mut items = HashSet::<i64>::new();for hs in target.iter(){if q.1.intersects(hs.1).unwrap(){items.insert(*hs.0);}}res.insert(*q.0, items);}let end = SystemTime::now().duration_since(start);println!("不用空间索引,计算完成 {:?}",end); res
}

可以看见,两种方法,最大的不同的就是一个用了空间索引预先进行过滤,之后再用intersects进行二次判断;一个直接用intersects进行暴力迭代判断,测试方法如下:

rust">#[test]
fn test_index_demo(){let useidx = test_spindex_demo_useidx();let nouse = test_spindex_demo_nouse();//对两个结果进行对比,如果不一致,会抛出assertfor key in useidx.keys(){let u = useidx.get(key).unwrap();let n = nouse.get(key).unwrap();println!("key = {:?}  使用空间索引 = {:?}  不使用空间索引 = {:?}",key,u.len(),n.len());assert_eq!(u.len(),n.len());}
}

运行结果如下:

时间效率对比

使用空间索引(包括了构建空间索引的开销在内),比不用空间索引的效率高了10倍以上,如果数据量更大的话,差距更大。

结果对比:

没有触发断言,说明二者是一致的。

结论:空间索引真是个好东西……

图片


http://www.ppmy.cn/news/1443634.html

相关文章

Solend创始人复盘ezETH脱锚:如何应对LST风险?

近日&#xff0c;因Renzo的代币经济学过于“中心化”引发加密社区争议&#xff0c;Renzo LRT代币ezETH遭大量抛售导致脱锚。Solend创始人Rooter针对此事在X平台发文&#xff0c;对此事件进行了发声。以下为内容全文&#xff1a; 此事并不是什么黑天鹅事件。而且也不算是尾部事…

Eclipse内存分析器 Java内存分析工具MAT(Memory Analyzer Tool)的介绍与使用

1.visualvm实时监测 2.Memory Analyzer Tool打开 3.工具的使用可以参考 Java内存分析工具MAT(Memory Analyzer Tool)的介绍与使用 ------------------------ 1.我远程发现是其中一个客户端A请求服务器页面响应&#xff0c;一直得不到响应&#xff0c;然后客户端A一直请求&am…

深入理解Linux调试工具eBPF和strace、内存泄漏处理、Kubernetes容器调试以及C++协程的崩溃信息收集

在软件开发领域&#xff0c;无论是初级开发者还是资深工程师&#xff0c;都需要面对复杂的调试工作。本文将介绍几个重要的调试工具和技术&#xff0c;并提供实际调试方法的指导&#xff0c;包括Linux环境下的eBPF和strace&#xff0c;内存泄漏问题的处理&#xff0c;Kubernete…

No system certificates available. Try installing ca-certificates.

一、错误重现 Certificate verification failed: The certificate is NOT trusted. No system certificates available. Try installing ca-certificates. 具体如图 系统环境是ubuntu:22.04 ARM架构 二、解决方法 1、先不要更换镜像源 直接设置 apt update apt -y instal…

字节5面挂,恶心到了。。。

字节五面 今天脉脉看到一篇帖子&#xff1a; 楼主是 tx 的前员工&#xff0c;在字节五面&#xff08;加轮&#xff09;被挂后&#xff0c;认定&#xff08;或许私下做了一些调查&#xff09;是字节 HR 向 tx 背调&#xff0c;然后被前同事捏造虚假信息&#xff0c;导致的面试失…

“五之链”第十六期沙龙活动在呆马科技成功举办

2024年4月19日&#xff0c;由临沂呆码区块链网络科技有限公司&#xff08;呆马科技&#xff09;承办的第十六期“五之链”物流主题沙龙活动成功举办。此次活动邀请了政府相关部门、知名科研院所、物流企业等20余家单位参与&#xff0c;共同探讨物流数据要素流通与智能应用的发展…

数据结构 - 链表详解(二)—— 带头双向循环链表

链表的介绍 链表的结构一共有八种&#xff1a;带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结…

WPS的JS宏如何设置Word文档的表格的单元格文字重新编号

希望对Word文档中的表格进行统一处理&#xff0c;表格内的编号&#xff0c;有时候会出现紊乱&#xff0c;下一个表格的编号承接了上一个表格的编号&#xff0c;实际需要重新编号。 当表格比较多时&#xff0c;手动更改非常麻烦&#xff0c;而且更改一遍并不能完成&#xff0c;…