空间连接

6个版本

0.1.5	2020年7月12日
0.1.4	2020年7月9日

#181 in 地理空间

MIT/Apache

135KB
3K SLoC

spatial-join 提供了在地理数据上执行流式空间连接的工具。

文档

请查看 docs.rs 上的文档。

给定两个地理空间形状序列，small 和 big，空间连接表示 small 和 big 中哪些元素相交。您可以使用嵌套循环自己计算这些值，但像任何好的空间连接包一样，这个包使用 R树来显著减少搜索空间。

我们不仅限于交集！通过传递不同的 Interaction 值，我们还可以找到 small 的元素包含 big 的元素或位于 big 元素内部的对。

邻近图

虽然空间连接是一个众所周知的术语，但邻近图不是。给定两个形状序列 small 和 big，它仅查找所有距离小于某个阈值的项对。您可以使用 max_distance 方法在 Config 结构上设置该阈值。

输入

输入是形状序列，形状必须是以下元素之一，来自 geo 包

MultiPoint、MultiLineString 和 MultiPolygon 不受支持。

虽然[geo] crate使这些类型对坐标类型进行了泛型化，但spatial-join仅支持以std::f64坐标类型参数化的[geo]类型（即，Polygon<f64>）。

那么，你可以使用什么类型的序列呢？

切片：&[T],
向量：Vec<T>或&Vec<T>，或者
&geo::GeometryCollection

此外

所有坐标值都必须是有限的
LineStrings必须至少有两个点
Polygon的外部必须至少有三个点

不符合这些条件的输入将返回一个错误。

输出

SpatialIndex::spatial_join返回Result<impl Iterator<Item=SJoinRow>, Error>，其中SJoinRow提供对small和big的索引，以找到相应的几何形状。

或者，你可以使用SpatialIndex::spatial_join_with_geos，它返回Result<impl Iterator<Item=SJoinGeoRow>, Error>。与SJoinRow不同的是，SJoinGeoRow增加了big和small Geometry字段，因此你可以直接与源几何形状一起工作，而不必保留原始序列。这种便利的代价是克隆源几何形状，这可能会在像LineString和Polygon这样的堆存储几何形状中变得昂贵。

以类似的方式，SpatialIndex::proximity_map和SpatialIndex::proximity_map_with_geos在其返回类型中提供ProxMapRow和ProxMapGeoRow迭代器。这些与它们的SJoin对应项的不同之处仅在于增加了distance字段。

示例

这里是最简单的事情：让我们验证一个点是否与自身相交。

use spatial_join::*;
use geo::{Geometry, Point};
fn foo() -> Result<(), Error> {
    // Create a new spatial index loaded with just one point
    let idx = Config::new()
        // Ask for a serial index that will process data on only one core
        .serial(vec![Geometry::Point(Point::new(1.1, 2.2))])?;
    let results: Vec<_> = idx
        .spatial_join(
            vec![Geometry::Point(Point::new(1.1, 2.2))],
            Interaction::Intersects,
        )?
        .collect(); // we actually get an iterator, but let's collect it into a Vector.
    assert_eq!(
        results,
        vec![SJoinRow {
            big_index: 0,
            small_index: 0
        }]);
    Ok(())
}
foo();

对于稍微复杂一些的情况，我们将取一个框和一个小框，并验证大框包含小框，并且我们将并行执行它。

#[cfg(feature = "parallel")] {
    use spatial_join::*;
    use geo::{Coordinate, Geometry, Point, Rect};
    use rayon::prelude::*;

    fn bar() -> Result<(), Error> {
        let idx = Config::new()
             .parallel(vec![Geometry::Rect(Rect::new(
                 Coordinate { x: -1., y: -1. },
                 Coordinate { x: 1., y: 1. },
             ))])?;
         let results: Vec<_> = idx
             .spatial_join(
                 vec![Geometry::Rect(Rect::new(
                     Coordinate { x: -0.5, y: -0.5 },
                     Coordinate { x: 0.5, y: 0.5 },
             ))],
                 Interaction::Contains,
             )?
             .collect();
         assert_eq!(
             results,
             vec![SJoinRow {
                 big_index: 0,
                 small_index: 0
             }]
         );
         Ok(())
    }
    bar();
}

crate功能

并行
- 默认启用。
- 这添加了对rayon的依赖，并提供了parallel方法，该方法返回一个ParSpatialIndex，就像SpatialIndex那样，通过serial方法返回，除了所有方法都返回Result<impl ParallelIterator>而不是Result<impl Iterator>。

地理信息

目前，这个crate假设您正在处理二维平面上的欧几里得几何。但这很不寻常：通常您有地理坐标（以十进制度量经度和纬度）。为了正确使用此包中的工具，您应该真正将您的几何形状重新投影到适当的欧几里得坐标系中。这可能需要您进行大量额外工作，如果您的几何形状范围超出了任何合理投影的处理范围。

或者，您可以将地心坐标当作欧几里得坐标。对于大部分空间连接操作，如果您的所有几何形状都远离子午线（经度=±180度）和极地地区，这将大致有效。

对于邻近地图，您需要选择一个合适的max_distance值，以十进制度量，这将同时用于经度和纬度偏移。这很具挑战性，因为虽然一度纬度始终相同（约110公里），一度经度从赤道的约110公里变化到极点的0公里。如果您的几何形状范围很窄且靠近赤道，您可能能够找到一个适用的max_distance值，但这很不可能。

性能

您会注意到我们的API以small和big来指定几何序列。为了构建一个空间索引对象，我们必须使用批量加载来构建一系列R树，每个几何类型一个。这个过程成本很高（O(n*log(n))），所以您可能会发现对较小的序列进行索引可以获得更好的整体性能。
由于空间连接和邻近地图操作实现为迭代器，您可以以低内存使用量处理非常大的数据集。但您需要在内存中保留small和large几何序列，以及为small序列的rtrees。请注意，在某些情况下，特别是当我们处理large序列的堆限制元素时（即多边形或多段线），我们将为每个此类large几何形状缓冲所有匹配的结果记录。
如果您使用非零的max_distance值，那么任何空间连接操作都会稍微慢一些，因为max_distance实际上在R树中缓冲了small几何形状。您仍然会得到正确的结果，但这可能需要更长的时间。max_distance值越大，所需时间就越长。

许可证

根据以下任一许可证授权：

Apache许可证，版本2.0（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
MIT许可证（LICENSE-MIT 或 https://open-source.org.cn/licenses/MIT）

由您选择。

贡献

除非您明确表示，否则任何有意提交以包含在作品中的贡献，如Apache-2.0许可证中定义，应双许可如上所述，没有任何附加条款或条件。

开发

随时间推移的基准结果在此处绘制。欢迎贡献！只需提交一个错误报告即可！

依赖项

约4.5MB
约91K SLoC