1

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

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

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

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

然而话又说回来，这似乎没有任何意义。Appart 从任何其他移动间隔似乎很昂贵，并且确定在哪里添加它们似乎很复杂。

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

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

但是它完成了.Get(...)返回 a List<stored_type>。将远远少于间隔列表中的内容，但其中仍有大量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 单步执行之前，比较每个元素是否重叠所需的边界。

4

1 回答 1

2

看来，您不需要实现不是间隔树而是 KD-Tree 数据结构。如果我没记错的话，KD-Trees 为低维启用 O(log N) 搜索时间。

一个快速的谷歌返回了许多结果，例如： http: //www.codeproject.com/KB/architecture/KDTree.aspx你可以去检查它是否符合你的需要，或者如果不符合你的需要，或者找到另一个实现。

于 2012-01-08T21:36:10.730 回答