问题标签 [spatial]

我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个 x 和 y 坐标值，以便我可以快速检索某个矩形或圆形内的所有对象。对于小型对象集（约 100 个），简单地将它们存储在列表中并遍历它的简单方法相对较快。然而，对于更大的群体来说，这预计会很慢。我也尝试将它们存储在一对 TreeMaps 中，一个按 x 坐标排序，一个按 y 坐标排序，使用以下代码：

这也有效，并且对于较大的对象集更快，但仍然比我想要的慢。部分问题还在于这些对象四处移动，并且需要重新插入此存储中，这意味着将它们从树/列表中删除并重新添加到树/列表中。我不禁认为那里必须有更好的解决方案。我正在用 Java 实现它，如果它有什么不同的话，尽管我希望任何解决方案都将以有用的模式/算法的形式出现。

我有一大组 3D 的三阶多项式。

矩阵形式

Pn = [1,t,t ² ,t ⁴ ]*[An]

[Pn]分别[An]是1xN和4xN矩阵

每个函数都有一个权重 Wn。n, m, T对于某些人，我想t0找到第一个这样的t地方t>t0

(Wn*Wm) * |Pn-Pm| ^-2 > T

除了 O(n ² ) “尝试一切”方法之外，我什至不确定从哪里开始，就此而言，即使对于已知的 n 和 m，我也不知道如何回答这个问题。

有任何想法吗

编辑：

• 设置大小约为 10-1000
• 权重是分布的〜对数（很少大，很多小）
• 这个测试将在一个多体模拟器的内部循环中，所以它会运行很多
• 在改变一条路径后，在找到新答案方面表现良好（摊销）的版本是一件好事。

我正在尝试在 SQL Server 2008 下创建一个包含GEOMETRY列及其计算变化的表。

考虑下表，其中计算列返回缓冲几何：

问题在于它会导致以下错误：

消息 4994，级别 16，状态 1，行 2 表 'Test' 中的计算列 'BufferedGeometry' 无法持久化，因为列类型 'geometry' 是非字节排序的 CLR 类型。

我搜索了 BOL 和网络，但似乎无法找到解决问题的方法。我真的希望它能够被持久化，这样我就可以有效地索引它。我可以在代码中设置它，但是我可能会出现不一致的数据，因为我在某个时间点需要这两个值。

有人玩过这个并且知道解决方案或解决方法吗？

更新：Microsoft 在 SQL Server 2012 中添加了此功能。

我想知道处理大量移动对象（球体、三角形、框、点等）的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。

我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，而 Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。

我只是希望那里有其他更好的东西。

我感谢所有的帮助。

我有对象的集合。每个对象代表一个坐标范围（即一个块）。我想要的是在给定方向上找到另一个坐标附近的对象。

有没有办法在不遍历整个集合的情况下做到这一点？

我有大量的 2D 点，我想快速获取位于某个矩形中的点。让我们说一个'。是任意点，“X”是我想在一个矩形内找到的点，该矩形将“T”作为 TopLeft，“B”作为 BottomRight 点：

我尝试了一个带有排序函子的 std::set ，它在集合的开头对 TopLeft 点进行排序，在集合的末尾对 BottomRight 进行排序。当先按 X 值排序时，这将导致找到以下点。

这意味着我必须检查每个找到的点，它是否真的在矩形内。不是很好。

有什么更好的方法来做到这一点？

我的语言是 C++ (Windows)，我有 STL 和 boost 可用。

更新

到目前为止阅读了答案，我注意到我没有考虑到我的问题的所有参数：没有一个固定的矩形。矩形可以由用户在运行时设置。这意味着对点集进行排序有望比在此更新之前 Artelius 建议的通过所有点进行线性搜索更有效。不过，我还是会试一试！我不希望用户非常频繁地设置矩形。因此，关于实施工作，它可能对我来说是一个很好的解决方案。

Sql Server 2008 支持具有新几何和地理 UDT 的空间数据。它们都支持 AsGml() 方法以 gml 格式序列化数据。然而，它们将数据序列化为 GML3 格式。有什么方法可以告诉它将数据序列化为 GML2 格式吗？

我目前正在处理一个必须处理 sql server 2008 地理类型的项目。由于项目的大部分使用 NHibernate 作为 ORM，我想知道使用/扩展 NHibernate.Spatial 这种类型需要做多少工作（据我所知，Nh Spatial 仅支持几何类型）。顺便提一句。还有其他支持这种 sql 类型的 .net ORM 吗？谢谢

从一开始，碰撞检测就好像是一个 O(n^2) 问题。

您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道将每个对象与所有其他对象进行检查是非常低效的。如果两个球甚至彼此不靠近，为什么要在两个球之间进行相对昂贵的碰撞检查？

这是我正在处理的简单程序的示例：

如果您有 1000 个球，那么如果您使用简单的碰撞检测，您将有 1000^2 次收集检查（一百万）！这种碰撞检查很快成为我的应用程序的瓶颈。我需要实施一些广泛的阶段修剪。

使用 2d 圆形对象时，应该使用哪些技术来修剪碰撞检查？我读过关于 QuadTrees、BSP、空间散列等的信息，但很难找出最适合这个用例的方法。

有没有人知道什么可能最有效？

定义几个点如下：

现在我想获得这两点之间的最短线。我可以使用什么功能来获取这条线？（即，它应该输出一个 LINESTRING(1 2, 6 8) 或 LINESTRING(6 8, 1 2)）

我知道我可以通过将点格式化为 WKT，进行一些字符串操作，然后将其解析回来来做到这一点，但这似乎很荒谬。当然有一些方法可以直接从一系列点构造线串？

（对于“几何”类型，我可以使用@p2.STUnion(@p1).STConvexHull()，但是对于地理类型没有STConvexHull()。）