структура данных для хранения угловых интервалов

Question

хотят, чтобы создать структуру данных, которая может хранить угловые интервалы, например (a,b), где оба a и b представляют полярный угол из конечных точек сегмента A,B против точки Q

Эта структура данных должна поддерживать две операции. Вставьте новые интервалы, а также скажите, была ли покрыта вся точка обзора точки Q, другими словами, если объединение всех точек зрения, созданных сегментами, составляет 360 градусов.

Я попытался реализовать очень простое дерево интервалов, где процедура вставки следующая.

1. Позвольте (a,b) интервал, который вы хотите вставить.
2. Начните с корневого узла, если (a,b) полностью покрыт интервалом, хранящимся в корневом узле, если это так, возвратитесь и ничего не сделайте.
3. В противном случае, возможно, какая-то часть покрыта корневым узлом, а часть не полностью покрыта. Не более двух частей не могут быть покрыты и в зависимости от каждого случая, рекурсия влево или/и в правое поддерево.

Я не использую дополненную структуру данных, в худшем случае, чтобы вставить интервал, вам придется делать O(n) операций, что дает вам сложность O(n^2) для вставки n интервалов.

Вот и проблема. Когда вы работаете с углами, вам приходится иметь дело с циклами, полярный угол которых равен a, а полярный угол равен b. Поэтому, учитывая сегмент AB, вы находите полярные углы конечных точек против Q, но тогда как вы узнаете интервал, который вы будете хранить в своем дереве?

Можно сказать, ладно, ваш интервал может быть (min(angleAQ, angleBQ), max(angleAQ, angleBQ)).

Это, однако, не будет работать в следующих случаях:

интервал будет определяться синим углом и зеленым углом, что значительно больше, чем фактическая точка зрения, которая определяется красный угол.

Из-за этого свойства цикла гораздо сложнее управлять такими интервалами угла.

Вопрос в том, может ли такое дерево интервалов существовать, и если да, то кто-то может дать мне некоторые подсказки для преодоления этих трудностей?

спасибо заранее

Answer 1

округлость углов не является основным препятствием: вместо этого интервала, как [270, 45), который обволакивает, вставить вместо двух интервалов [270, 360), [0, 45).

Для внедрения вставки без wraparound мы можем использовать двоичное дерево поиска. Это дерево отслеживает непокрытые интервалы, сопоставляя каждую конечную точку непокрытого интервала с тем, является ли это левой или правой конечной точкой.Например, если мы покрыли интервалы [0, 45), [0, 60), [90, 120), [150, 180), [180, 270), то отображение

60: left 
90: right 
120: left 
150: right 
270: left 
360: right . 

Инициализировать отображение с

0: left 
360: right 

Для вставки интервальной [a, b) с a < b, мы следующие. Найдите предшественника x из a в отображении (наибольший ключ не более a). Если x существует и является левой конечной точкой, тогда вставьте a в качестве правой конечной точки (после x). Найдите преемника y из b в картографии (наименьший ключ не менее b). Если y существует и является правой конечной точкой, тогда вставьте b в качестве конечной точки слева (до y). Удалите все ключи, которые не только вставлены между a и b включительно. Начальный интервал покрывается полностью тогда и только тогда, когда отображение пусто.