Эффективное представление растущих кругов в 2D-пространстве?

Question

Представьте, что есть двумерное пространство, и в этом пространстве есть круги, которые растут с разной постоянной скоростью.Какова эффективная структура данных для хранения этих кругов, так что я могу запросить «Какие круги пересекают точку p в момент времени t?».

РЕДАКТИРОВАТЬ: я понимаю, что я мог бы сохранить начальное состояниеокружности в структуре пространственных данных и выполняю запрос, где я пересекаю окружность в точке p с радиусом fastest_growth * t, но это неэффективно, когда есть несколько окружностей, которые растут чрезвычайно быстро, тогда как большинство растут медленно.

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

Answer 1

Представляет круги в виде конусов в 3d, где третье измерение - время. Затем используйте дерево BSP, чтобы разделить их как можно лучше.

В общем, я думаю, что наихудший случай для проверки на пересечение - это всегда O (n), где n - количество окружностей. Большинство пространственных структур данных работают путем умного разделения пространства таким образом, чтобы часть объектов (возможно, близкая к половине) находилась в каждой половине. Однако, если объекты перекрываются, разделение не может быть идеальным; всегда будут случаи, когда в разделе находится более одного объекта. Если вы просто подумаете о случае перекрытия двух окружностей, то нет способа нарисовать линию так, чтобы один кружок был полностью с одной стороны, а другой - полностью с другой стороны. Взятый до логического предела, предполагая произвольное расположение окружностей и произвольных радиусов, невозможно разделить их так, чтобы проверка на пересечение заняла O (log (n)).

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

Answer 2

Извините, это не до конца продумано, но кажется, что вы можете посмотреть на мультипликативно-взвешенные диаграммы Вороного (MWVD). Кажется, что злоумышленник может заставить вас вычислить один с помощью ряда правильно расположенных запросов, поэтому у меня есть ощущение, что они дают нижнюю границу вашей проблемы.

Предположим, вы вычислили MWVD для ваших входных данных. Затем для запроса вам будет возвращен круг, который является «ближайшим» к вашей точке запроса. Затем вы можете определить, действительно ли этот круг содержит точку запроса во время запроса. Если это не так, значит, все готово: ни один круг не содержит вашей точки. Если это так, то вы должны вычислить MWVD без этого генератора и выполнить тот же запрос. Возможно, вы сможете вычислить новый MWVD из старого: ячейка, содержащая удаленный генератор, должна быть заполнена, и кажется (хотя я не доказал это), что единственные генераторы, которые могут заполнить его, это его соседи .

Answer 3

Это упрощенная версия другой проблемы, которую я опубликовал около недели назад: Как найти первое пересечение луча с движущимися кругами

У меня еще не было времени описать ожидаемое там решение, но я постараюсь изложить его здесь (для этого упрощенного случая)

Подход к решению этой проблемы заключается в использовании кинетического KD-дерева . Если вы не знакомы с деревьями KD, лучше сначала прочитать о их . Вам также нужно добавить время в качестве дополнительной координаты (вы делаете пространство 3d вместо 2d). Я еще не реализовал эту идею, но я считаю, что это правильный подход.

Answer 4

Если вы, как уже предлагалось, представляете растущие круги вертикальными конусами в 3d, то вы можете разделить пространство как регулярную (может быть шестиугольную) сетку упакованных вертикальных цилиндров.Для каждого цилиндра вычислите минимальные и максимальные высоты (времена) пересечений со всеми конусами.Если центр круга (вершина конуса) находится внутри цилиндра, то минимальное время равно нулю.Затем сортируйте конусы по минимальному времени пересечения.В результате такой индексации для каждого цилиндра у вас будет упорядоченная последовательность записей с 3 значениями: минимальное время, максимальное время и номер круга.

Когда вы проверяете некоторую точку в трехмерном пространстве, вы берете цилиндр, которому она принадлежит, и повторяете его последовательность, пока сохраненное минимальное время не превысит время данной точки.Все полученные конусы, максимальное время которых также меньше заданного времени, гарантированно содержат заданную точку.Только конусы, где заданное время лежит между минимальным и максимальным временем пересечения, необходимы для пересчета.

Существует классический компромисс между индексированием и затратами времени выполнения: чем меньше диаметр цилиндра, тем меньше диапазон пересечений, поэтому в каждой точке требуется пересчет меньшего числа конусов, но нужно индексировать больше цилиндров.Если центры окружностей распределены неравномерно, то, возможно, стоит поискать лучшую конфигурацию размещения цилиндров, чем обычную сетку.

PS Мой первый ответ здесь - только что зарегистрировался, чтобы опубликовать его.Надеюсь, еще не поздно.

Answer 5

Чтобы бороться с несколькими кругами, которые быстро растут, вы можете отсортировать круги в порядке убывания по скорости роста и проверить каждого из k самых быстрых производителей.Чтобы найти правильное k для заданного t, я думаю, что вы можете выполнить бинарный поиск, чтобы найти индекс k такой, что k * m = (t * скорость роста k) ^ 2, где m - постоянный коэффициент, который вам нужно найти поэкспериментирование.Будет сбалансирована часть, которая растет линейно с k, с частью, которая квадратично падает с темпом роста.

Answer 6

Я думаю, что можно создать бинарное дерево, которое решает эту проблему.

Каждая ветвь должна содержать растущий круг, статический круг для разбиения и самое позднее время, когда круг разбиения чисто разделил.Более того, растущий круг, содержащийся внутри узла, всегда должен иметь более высокую скорость роста, чем любой из растущих кругов дочерних узлов.

Чтобы выполнить запрос, возьмите корневой узел.Сначала проверьте растущий круг, если он содержит точку запроса во время запроса, добавьте его в набор ответов.Затем, если время, которое вы запрашиваете, больше, чем время, в которое линия разбиения разорвана, запросите обоих потомков, в противном случае, если точка попадает в круг разбиения, запросите левый узел, иначе запросите правый узел.

Я не совсем завершил детали выполнения вставок (сложная часть заключается в обновлении круга разбиения так, чтобы число узлов внутри и снаружи было приблизительно равным, а время разрыва раздела было максимально увеличено).

Answer 7

Вместо того, чтобы рассматривать круги, вы можете проверить их ограничивающие рамки, чтобы отфильтровать те, которые не содержат точку. Если все стороны вашей ограничительной рамки отсортированы, то это по сути четыре бинарных поиска.

Хитрая часть реконструирует отсортированные стороны за любое время, t. Для этого вы можете начать с исходных точек: два списка для левой и правой сторон с координатой x, и два списка для верхнего и нижнего с координатами y. В любое время, превышающее 0, все левые боковые точки будут перемещаться влево и т. Д. Вам нужно только проверить каждую позицию на одну рядом с ней, чтобы получить точки, в которых элемент и одна рядом с ним меняются местами. Это должно дать вам список моментов времени для изменения ваших упорядоченных списков. Если вы теперь сортируете эти записи изменений по времени, для любого заданного времени начала и времени окончания вы можете извлечь все записи изменений между ними и применить их к своим четырем спискам по порядку. Я не совсем понял алгоритм, но думаю, что будут граничные случаи, когда три или более последовательных элемента могут пересекаться точно в один и тот же момент времени, поэтому вам может потребоваться изменить алгоритм для обработки этих граничных случаев. Возможно, будет достаточно записи о модификации списка, которая содержит позицию в списке и количество записей, которые нужно переупорядочить.

Answer 8

Люди собираются дать много рекомендаций относительно типов пространственных индексов, но я хотел бы предложить немного ортогональных советов.

Я думаю, вам лучше построить несколько индексов, основанных на времени, то есть t_0

Если точка пересекает окружность в t_i, она также будет пересекать ее в t_ {i + 1}. Если вы знаете точку заранее, вы можете устранить все окружности, которые пересекают точку в t_i, для всех вычислений в t_ {i + 1} и позже.

Если вы заранее не знаете точку, то вы можете сохранить эти деревья точек времени (построенные на основе того, насколько большим будет каждый круг в данный момент времени). Во время запроса (например, t_query) найдите i такой, что t_ {i-1}

Это своего рода хак для структуры данных, которая "осведомлена о динамике времени", но я ничего не знаю. Если у вас есть многопоточная среда, то вам нужно только поддерживать один пространственный индекс и работать со следующим в фоновом режиме. Это будет стоить вам много вычислений для того, чтобы отвечать на запросы с низкой задержкой. Это решение следует сравнить как минимум с решением O (n) (пройти каждую точку и проверить, является ли dist (point, circle.center)

Answer 9

Как распределяются центры ваших кругов?Если они покрывают плоскость достаточно равномерно, вы можете дискретизировать пространство и время, а затем выполнить следующие действия в качестве шага предварительной обработки:

for (t=0; t < max_t; t++)
    foreach circle c, with centre and radius (x,y,r) at time t
        for (int X = x-r; X < x+r; x++)
           for (int Y = x-r; Y < y+r; y++)
               circles_at[X][Y][T].push_back (&c)

(при условии, что вы дискретизируете пространство и время вдоль целочисленных границ, масштабируете и смещаете, сколько хотитеконечно, и вы можете добавить круги позже или амортизировать стоимость, отложив расчет для отдаленных значений t)

Тогда ваш запрос для точки (x, y) в момент времени (t) может сделать грубоепринудительная линейная проверка более circles_at[x][y][ceil(t)]

Компромисс очевиден: увеличение разрешения любого из трех измерений увеличит время предварительной обработки, но даст вам меньший интервал в circles_at[x][y][t] для тестирования.

Answer 10

Какой-то пространственный индекс , такой как quadtree или BSP , даст вам время доступа O (log (n)).

Например, каждый узел в дереве квадрантов может содержать связанный список указателей на все те окружности, которые пересекают его.

Сколько кругов, кстати? Для малых n вы можете просто перебирать их. Если вам постоянно приходится обновлять свой пространственный индекс и перепрыгивать через строки кэша, это может привести к более быстрой его обработке.