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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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] для тестирования.

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Ответ 8

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

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

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

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

Ответ 9

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

Ответ 10

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

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

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

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