标签: spatial-index

像大多数普通的PHP Web开发人员一样,我使用MySql作为RDBMS.MySql(也像其他RDBMS一样)提供了SPATIAL INDEX功能,但我不是很好.我已经google了它,但没有找到明确的现实世界的例子来澄清我对它的不良知识.

有人可以解释一下什么是空间索引,我什么时候应该使用它？

我有大量的矩形,有些与其他矩形重叠; 每个矩形具有绝对的z次序和颜色.(每个'矩形'实际上是粒子效果,网格或纹理的轴对齐边界框,可能是半透明的.但只要你不试图剔除其他人的矩形,它就更容易抽象地思考彩色矩形. ,所以我会在问题描述中使用它:)

改变'颜色'的成本非常高; 连续绘制两个蓝色矩形比绘制两个不同颜色的矩形要快得多.

绘制甚至不在屏幕上的矩形的成本也非常高,应该避免.

如果两个矩形不重叠,则它们相对于彼此绘制的顺序并不重要.只有当它们重叠时,z顺序才是重要的.

例如:

可以将1(红色)和4(红色)绘制在一起.2(蓝色)和5(蓝色)也可以一起绘制,如3(绿色)和7(绿色).但是必须在6(蓝色)之后绘制8(红色).所以要么我们将所有三个红色绘制在一起并绘制两组中的蓝色,要么我们将所有蓝色绘制在一起并将两个红色绘制成两组.

并且一些矩形可能偶尔移动.(不是全部;已知一些矩形是静态的;已知其他矩形移动.)

我将在JavaScript/webGL中绘制这个场景.

如何以合理的顺序绘制矩形以最小化颜色变化,通过JavaScript剔除代码与让GPU剔除的良好折衷？

(只是找出哪些矩形重叠并且哪些是可见的是昂贵的.我有一个基本的四叉树,这加速了我的场景极大地绘制(与刚刚为整个场景发射绘图操作相比);现在的问题是如何最小化OpenGL状态更改并尽可能连接属性数组)

更新我创建了一个非常简单的测试应用程序来说明问题,并作为演示解决方案的基础: http: //williame.github.com/opt_rects/

源代码在github上,可以很容易地分叉:https://github.com/williame/opt_rects

事实证明很难做出一个具有足够状态变化的小测试应用程序来实际重现我在完整游戏中看到的问题.在某些时候,你必须把它当作一个给定的状态变化可能足够昂贵.同样重要的是如何加速空间索引(演示中的四叉树)和整体方法.

我在C#中找到了一些开源的R-Tree实现,但没有一个带有文档,也没有被开发者以外的其他人使用的迹象.

赏金

这个问题提出了几个问题.赏金将回答整体上的问题.

这是我一直在玩的问题.

注意我对不在欧几里得空间的解决方案特别感兴趣.

有一组Actors形成一个大小为K的人群.d(ActorA,ActorB)对于任何两个演员来说,距离很容易计算(解决方案应该适用于'距离'的各种定义)并且我们可以找到任何给定Actor使用的N个最近邻居的集合任何一种已建立的算法.

这个邻居集在第一瞬间是正确的,但是Actors总是在移动,我想维护每个Actor的N个最近邻居的进化列表.我感兴趣的是近似解决方案,它比完美解决方案更有效.

1. 在引入错误之后,解决方案应该收敛到正确性.
2. 如果错误变得太大而有时执行完全重新计算是可以接受的,但检测这些错误应该是便宜的.

到目前为止,我一直在使用一个朋友的朋友算法:

recompute_nearest (Actor A)
{
    Actor f_o_f [N*N];
    for each Actor n in A.neighbours
        append n to f_o_f if n != A and n not in f_o_f

    Distance distances [N*N];
    for 0 <= i < f_o_f.size
        distances [i] = distance (A, f_o_f [i])

    sort (f_o_f, distances)
    A .neighbours = first N from f_o_f
}

当人群缓慢移动且N适当大时,这表现得相当好.它在小错误之后收敛,满足第一个标准,但是

• 我没有很好的方法来检测大错误, …

我正在开发一个模拟程序.有成群的动物(角马),在那群中,我需要找到一只远离牛群的动物.

在下图中,绿点远离牛群.我希望能够快速找到这些要点.

当然,有一个简单的算法来解决这个问题.计算每个点附近的点数,然后如果该邻域是空的(其中0点),那么我们知道这一点远离牛群.

问题是这个算法根本没有效率.我有一百万点,并且在每百万点上应用这个算法非常慢.

有什么东西会更快吗？也许用树木？

编辑@amit:我们想避免这种情况.A组在左上角绿点会被选择,即使他们应该不是,因为它不是一个单一的动物是从牛群离开,这是一组动物.我们只是寻找远离牛群的一只动物(不是一群人).

在Haskell中是否有任何良好的空间索引实现,如R-tree,kd-tree等...

我正在尝试为我正在处理的数据集选择一个不错的SQL Server 2008空间索引设置.

数据集是多边形,表示整个地球的轮廓.表中有106,000行,多边形存储在几何字段中.

我的问题是许多多边形覆盖了地球的很大一部分.这似乎很难获得一个空间索引,它将消除主过滤器中的许多行.例如,查看以下查询:

SELECT "ID","CODE","geom".STAsBinary() as "geom" FROM "dbo"."ContA"
WHERE "geom".Filter(
  geometry::STGeomFromText('POLYGON ((-142.03193662573682 59.53396984952896,
    -142.03193662573682 59.88928136451884,
    -141.32743833481925 59.88928136451884,
    -141.32743833481925 59.53396984952896,
    -142.03193662573682 59.53396984952896))', 4326)
) = 1

这是查询与表中只有两个多边形相交的区域.无论我选择何种空间索引设置组合,Filter()总是返回大约60,000行.

用STIntersects()替换Filter()当然只返回我想要的两个多边形,但当然需要更长的时间(Filter()为6秒,STIntersects()为12秒).

任何人都可以给我任何关于是否存在可能在60,000行上改进的空间索引设置或者我的数据集是否与SQL Server的空间索引不匹配的提示？

更多信息:

正如所建议的那样,我在地球上使用4x4网格分割多边形.我无法用QGIS看到这样的方法,所以我编写了自己的查询来做到这一点.首先我定义了16个边界框,第一个看起来像这样:

declare  @box1 geometry = geometry::STGeomFromText('POLYGON ((
-180 90,
-90 90,
-90 45,
-180 45,
-180 90))', 4326)

然后我使用每个边界框来选择和截断与该框相交的多边形:

insert ContASplit
select CODE, geom.STIntersection(@box1), CODE_DESC from ContA
where geom.STIntersects(@box1) = 1

我显然为4x4网格中的所有16个边界框做了这个.最终结果是我有一个新表~107,000行(这证实我实际上没有很多巨大的多边形).

我添加了一个空间索引,每个对象有1024个单元格,每个级别的单元格低,低,低,低.

然而,非常奇怪的是,这个具有分割多边形的新表仍然与旧表一样.执行上面列出的.Filter 仍然会返回~60,000行.我根本不理解这一点,显然我不明白空间索引实际上是如何工作的.

矛盾的是,虽然.Filter()仍然返回~60,000行,但它的性能有所提高..Filter()现在大约需要2秒而不是6秒,而.STIntersects()现在需要6秒而不是12秒.

这里要求的是索引的SQL示例:

CREATE SPATIAL INDEX [contasplit_sidx] ON [dbo].[ContASplit] 
(
    [geom]
)USING …

到目前为止,关于设计决策的一些背景......我开发了一种可以存储点的八叉树结构.我选择基于某个基本体素大小来限制"世代"的递归.只有在将点添加到该节点时才会创建子节点.这不是动态图形应用程序 - 这个八叉树及其中的对象是静态的,因此不需要考虑提高性能的预处理.

现在,我想在我的八叉树中添加"形状" - 特别是由三角形组成的表面网格.这些三角形的顶点不对应于存储在八叉树中的点.如何在八叉树中存储这些形状？我看到两个选择......

灰色节点是"空的",因为它们没有形状.在备选方案1中,形状存储在它们相交的每个节点中 - 即,节点1a包含shape1和4c和4d共享shape2.在备选方案2中,形状仅存储在它们相交的最小节点中 - 即,节点1a包含shape1而节点4包含shape2.

我见过的八角树上的大多数帖子都假设为Alt1,但他们从未解释过为什么.Alt2对我来说更有意义,只会为那些驻留在节点边界上的形状创建额外的工作.为什么Alt1更受欢迎？

编辑:为了澄清,我使用的实现语言是C++,所以我更喜欢该语言的示例实现,但问题是与语言无关.对不起,如果标签使用不正确.

编辑2:虽然与形状存储问题没有直接关系,但这个链接对问题背后的八叉树遍历有很好的讨论.我认为这可能有助于任何有兴趣研究这个问题的人.

更新:四年后,Alt2最终变得更容易实现,但速度非常慢,因为在八叉树的每次遍历中都会测试存储在较高八叉树级别的大三角形 - 在我的情况下,这意味着需要进行数百到数千次不必要的测试.我最后修改了我的代码以使用R*-Tree变体,这很容易实现并且速度更快.

我正在努力将一些空间搜索功能从Postgres与PostGIS一起移动到SQL Server,我看到一些相当糟糕的性能,即使是索引也是如此.

我的数据大约有一百万个点,我想找出哪些点在给定的形状内,所以查询看起来像这样:

DECLARE @Shape GEOMETRY = ...
SELECT * FROM PointsTable WHERE Point.STWithin(@Shape) = 1

如果我选择一个相当小的形状,我有时可以得到亚秒,但如果我的形状相当大(有时它们),我可以得到超过5分钟的时间.如果我在Postgres中运行相同的搜索,它们总是在一秒钟之内(事实上,几乎所有搜索都在200毫秒之内).

我在我的索引上尝试了几种不同的网格大小(全高,全中,全低),每个对象不同的单元格(16,64,256),无论我做什么,时间都保持不变.我想尝试更多组合,但我甚至不知道要走哪条路.每个对象更多的细胞？减？一些奇怪的网格尺寸组合？

我查看了我的查询计划,他们总是使用索引,它根本就没有帮助.我甚至试过没有索引,并没有更糟糕.

有没有人可以给出任何建议？我能找到的一切都表明"我们不能给你任何关于索引的建议,只是尝试一切,也许一个会工作",但是用10分钟创建一个索引,盲目地做这个是浪费大量时间.

编辑:我也在微软论坛上发布了这个.以下是他们在那里要求的一些信息:

我能得到的最好的工作指数就是这个:

CREATE SPATIAL INDEX MapTesting_Location_Medium_Medium_Medium_Medium_16_NDX
    ON MapTesting (Location)
 USING GEOMETRY_GRID
  WITH (
    BOUNDING_BOX = ( -- The extent of our data, data is clustered in cities, but this is about as small as the index can be without missing thousands of points
        XMIN = -12135832,
        YMIN = 4433884,
        XMAX = -11296439,
        YMAX = 5443645),
    GRIDS = ( …

我有一个包含大约100000个点的数据集和另一个包含大约3000个多边形的数据集.对于每个点我需要找到最近的多边形(空间匹配).多边形内的点应与该多边形匹配.

计算所有对距离是可行的,但需要的时间比必要的长.是否有一个R包将利用空间索引来解决这种匹配问题？

我知道sp包和over函数,但文档没有告诉任何关于索引.