使用一维区间树的二维区间树

Question

我正在使用这里的 C# 间隔树集合类 http://intervaltree.codeplex.com/ SourceControl/list/changesets ->右手边->下载。

我需要从与给定的集合重叠的集合中获取间隔。使用 .Get(left, right) 这似乎很容易。然而我需要 2D 间隔，显然从 1D 间隔开始并不难。

我听说它是​​通过嵌套来完成的。

IntervalTree<IntervalTree<stored_type, float>, float> intervals;

然而话又说回来，这似乎没有道理。除此之外，移动间隔似乎很昂贵，并且确定在哪里添加它们似乎很复杂。

IntervalTree<stored_type, float> intervals_x;
IntervalTree<stored_type, float> intervals_y;

我不确定我是否这样做了，但它会如何执行Get(left, right, upper, lower)。据推测，stored_type 的实例将存在并且属于这两个集合，但是如果这些集合随着事物的变化而重新排列，是否会出现问题？

然而，.Get(...) 完成后返回一个 List。间隔列表中的项目将远远少于间隔列表中的项目，但此 List 中仍然有大量项目需要快速处理，但独立地，它们不需要订单。我可以将 List 转换为另一个集合（例如 LinkedList 或 HashSet），以便比仅仅遍历它更快吗？

编辑：

所以也许像下面这样。

class interval_tree_2D
{
    private IntervalTree<stored_type, float> x =
        new IntervalTree<stored_type, float>();
    private IntervalTree<stored_type, float> y =
        new IntervalTree<stored_type, float>();

    public void add(stored_type n,
        float left, float right, float lower, float upper)
    {
        intervals_x.AddInterval(left, right, n);
        intervals_y.AddInterval(upper, lower, n);
    }

    public HashSet<stored_type> get(
        float left, float right, float lower, float upper)
    {
        var i1 = x.Get(left, right);
        var i2 = y.Get(lower, upper);
        var i3 = i1.to_HashSet();
        var i4 = i2.to_HashSet();
        return i3.union(i4);
    }
}

除了没有 to_HashSet() 之外，所以我必须使用双循环来找出两个集合相交的位置。每个元素的 x 和 y 也是硬编码的。

我真的很想得到一些反馈。在我使用 HashSet 和 foreach 来逐步遍历它之前，比较每个元素是否重叠所需的边界。

Answer 1

看来，您不需要实现区间树，而是 KD 树数据结构。如果我没记错的话，KD 树可以实现低维度的 O(log N) 搜索时间。

快速谷歌返回了许多结果，例如： http://www.codeproject.com/KB /architecture/KDTree.aspx 你可以去检查一下是否符合你的需求，如果不符合你就寻找其他实现。