问题标签 [interval-tree]

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

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

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

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

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

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

编辑：

所以也许像下面这样。

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

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

我需要一个二维间隔树来在画布中存储矩形区域。
我需要识别包含单击点的区域或与矩形选择重叠的区域。

有没有为此目的的二维区间树的标准实现？

是否有一种内置方法可以获取 boost::icl::interval_map 中的间隔数？我在文档中找不到它。方法size()似乎有不同的目的。

这是我为遍历区间树而编写的函数。我注意到它无法访问某些节点。假设代码很清楚，我想知道它在哪里失败。

给定开始/结束日期时间值的列表，我需要验证三件事：

1. 对于每个间隔，开始时间在结束时间之前
2. 列表元素之间不存在重叠，每个开始/结束跨度必须代表整个列表中的离散间隔
3. 系列中不能有间隔，从最早的开始到最晚的结束，必须有连续的覆盖。

所以，给定：

给出一个成功的结果。

给定

提供一条消息，指出开始日期晚于第一个元素中的结束日期。

给定

提供说明第一和第二元素之间存在重叠的消息。

给定

提供一条消息，说明第二个和第三个元素之间存在间隙。

第一个要求很简单，问题是如何最好地将其纳入更广泛的验证。

下面的文章在一定程度上满足了第二个要求，但由于它仅适用于一对间隔，我仍然会意识到 O(n^2) 因为每个元素都需要与其他元素进行比较，对吗？确定两个日期范围是否重叠

这篇文章 -在区间列表中搜索区间重叠？- 似乎更好地解决了第二个要求，第一个可以滚动到区间树的种群中。

这样就剩下第三个要求了。是否可以使用区间树确定整个区间的间隙？

我会提到这是在 Javascript，node.js 中。然而，用 Haskell 或其他函数式语言解决这个问题会很有趣......

谢谢！

r/史蒂夫

让我们考虑下面的图片

这是一个所谓的范围树。我不明白一件事，它看起来类似于二叉搜索树，所以如果我们要插入元素，我们可以使用与二叉搜索树插入相同的过程。那么区别是什么呢？

我已经阅读了一个教程，并猜测它是 kd 树、查询搜索树（如几何点搜索等）的变体，但是如何构建它呢？像二叉搜索树还是需要额外的参数？也许像这样

在插入过程中我们必须检查

请帮助我正确理解如何构建范围树。

我有一堆可能重叠的（日期）间隔。间隔来自不同的来源。我想“展平”这个“时间线”，然后找到所有没有间隔的间隔。

如果您查看：http ://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ 到“更复杂的示例”部分。因此，我想找到没有作曲家在世的区间。

我怎么做？你将如何在 PHP 中实现这样的事情？PHP 是否也有一些简单的函数来构建树？

很多谢谢！

编辑 我的输入是一些数组（2、3 或 4），每个数组都包含开始和停止日期，如下所示：

myarray2、myarray3 等也是如此

我正在尝试使用该Set::IntervalTree模块，如果我在循环中插入元素，我认为它会给我相同的节点指针。

如果我将它们一个接一个地依次插入到循环之外，则节点插入正常，并且find/find_window调用完美运行。但是在循环中添加的节点上，find 函数给出了奇怪的结果。

这是输出。检查节点指针..从循环中添加的指针具有相同的指针并且它们返回错误的间隔（我猜这是由于相同的指针值。）

I have been reading about interval trees on wikipedia. Does anyone know how to implement the delete method in Java? The link to the delete algorithm is http://en.wikipedia.org/wiki/Interval_tree#Deletion

给定一组区间：{1-4, 6-7, 10-12} 添加一个新区间：(9,11)，以便最终解决方案“合并”：输出：{1-4, 6-7, 9-12}。合并可以发生在双方（低范围和高范围）。

我看到这个问题在多个地方得到了回答，甚至有人建议使用 Interval Tress，但没有解释他们将如何使用它。我知道的唯一解决方案是按开始时间的升序排列间隔并迭代它们并尝试适当地合并它们。

如果有人可以帮助我理解我们如何在这个用例中使用区间树，那就太好了！

[我一直在关注 CLRS 书中的区间树，但他们没有谈论合并，他们谈论的只是插入和搜索。]