「圓形」間隔樹算法

我想知道是否有人已經實現/知道將處理循環間隔的（優選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

「圓形」間隔樹算法

回答

相關問題