“圆形”间隔树算法

我想知道是否有人已经实现/知道将处理循环间隔的（优选JavaScript）区间树算法。通过循环，我的意思是开始>结束的时间间隔。请注意，这也需要限制间隔的大小。“圆形”间隔树算法

这只是一个常见区间树问题的子代？

在回答提出的问题的意见：下面是一个图片（感谢G.巴赫和维基百科）我的意思被圆形小范围：

和（无关上面的图片）这里是一个范围的例子JSON表示： [{ID： '范围1'，启动：3，端：34}，{ID： 'range2circular'，开始：30，端：6}]

希望

谢谢！

来源

2015-11-20 majorBummer

请提供一些例子。 –

您可以简单地反转每个负长度的区间，所以如果区间是'（start，end）'和'start> end'，那么存储'（end，start，R）'，其中R表示这个区间是相反的。你可以使用一个正常的区间树，然后从'R'中知道给定结果的开始和结束都是颠倒过来的。 –

您的价值观来自哪个域名？他们如何环绕？ – Bergi

与circular arc graphs背后的想法相关的声音（但不是图表本身，因为您从间隔开始并且不关心它们的圆弧图形表示）。

假设它就是这样，那就意味着该域可以用一个类似于圆的度数的周期表示。那么你有一个最小的可能值min和最大可能值max = min + 1*period，而你要做的第一件事就是找到最小的s，从而start = min + s + k*period整数k（基本上，这是一个模运算），同样你找到最小的e这样即end = min + e + j*period。

现在您可以将您的间隔表示为(s,e)仍然使用s > e。将它分成两个区间(s, max)和(min, e)，将它们放入间隔树中，并将它们引用到原始区间(start, end)。如果从n开始，可能会重叠一段时间，那么最终会在树中出现2n间隔，并且渐近边界保持不变。

来源

2015-11-20 10:41:54

“圆形”间隔树算法

回答

相关问题