«круглый» алгоритм дерева интервалов

Question

Мне интересно, реализовал ли кто-нибудь алгоритм интервального дерева (желательно javascript), который будет обрабатывать круговые интервалы. По кругу я имею в виду интервалы с началом> end. Обратите внимание, что это также требует ограничения, насколько велики интервалы.

Это просто подзаголовок проблемы с общим интервалом?

В ответ на вопросы, заданные в комментариях: Вот изображение (спасибо Г. Бах и википедии) о том, что я имею в виду круговой подобласти:

И (не имеющей отношения к изображению) вот пример JSON представление диапазонов: [{ID: 'диапазон1', старт: 3, конец: 34}, {ID: 'range2circular', старт: 30, конец: 6}]

Надежда

Благодаря!

Answer 1

Звуки, связанные с идеей позади 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 интервалов в дереве и удерживают асимптотические границы.