2D数据的最快空间索引,一旦构建,就没有更新

c# algorithm indexing geospatial spatial

1229 观看

4回复

2930 作者的声誉

  • 我有大型2D对象集合,现在只有行。
  • 我需要算法建议如何在此集合上创建最快的空间索引,以便我可以收集某些边界内的所有对象。
  • 一旦构建索引将不会更新。
  • 此数据库中的对象分布在空间上不一致。
  • C#中的算法实现。
  • 更新:当前用途是针对某个国家/地区的路线图,因此线路很小,从一个十字路口到另一个十字路口,人口密集区域的密度更大。我认为这可以很好地了解数据。

显然有很多索引方法可以实现这一点,但我需要一个最快的方法。

作者: watbywbarif 的来源 发布者: 2011 年 11 月 16 日

回应 (4)


1

21040 作者的声誉

如果要保存二维线,并且查询是二维范围查询,则可以使用“ 段”树

查询的算法复杂度为O(log ^ 2 N)。

作者: parapura rajkumar 发布者: 16.11.2011 01:26

1

476 作者的声誉

查看quadtrees ....和DotSpatial以进行空间类型处理,包括四叉树实现。

作者: timemirror 发布者: 02.07.2012 08:04

1

2509 作者的声誉

您也可以尝试使用R树http://sourceforge.net/projects/cspatialindexrt/上有一个C#实现。

R树应该具有段树的性能,并且上面的实现应该是独立的并且相当独立于许多额外的代码引用,但我还没有测试它。

作者: Ted 发布者: 15.08.2013 05:46

0

292 作者的声誉

这没有灵丹妙药。它取决于数据的类型(即,只有点,只有线,三角形,网格,它们的任意组合等)和查询类型(多边形内的点,线交点,最近邻,圆内的任何几何或盒子等)。

您有一个针对特定类型的查询和数据设计的数据结构。如果要对所有类型的查询和所有类型的数据使用单个数据结构,则必须在空间或时间或两者之间进行权衡。你可以接近合理的速度,但一般来说你不会是最佳的。

根据我的经验,数据结构一般足以处理大多数几何对象,并且可以处理几种类型的查询,我建议AABB-Tree:

https://doc.cgal.org/latest/AABB_tree/index.html

作者: Mauricio Cele Lopez Belon 发布者: 06.11.2018 11:56
32x32