Как найти первое пересечение луча с движущимися кругами

Question

Я некоторое время боролся с проблемой и до сих пор не нашел решения лучше, чем наивный:

даны N кругов, которые движутся по линейному закону. Для каждой из окружностей мы имеем ее начальный (в момент 0,0) радиус, начальные координаты, а также его радиус и координаты в момент 1,0 (конечный момент). У нас также есть k лучей с координатами их происхождения и вектором вдоль луча. Каждый луч существует только в данный момент t _k . Я должен быть в состоянии найти первое пересечение луча с любым из кругов. Ожидаемое число k довольно велико (миллионы или миллиарды), а также ожидаемое количество кругов (тысячи). Мне нужно решение быстрее, чем проверять все лучи на всех кругах.

Я некоторое время искал в интернете, но не нашел подходящего решения. Будут оценены даже идеи более простой проблемы, когда круги не движутся.

У меня такое ощущение, что kd-дерево должно подходить для статического случая, и, возможно, кинетическое kd-дерево решит более сложное. Тем не менее я не могу понять, как использовать kd-дерево даже для более простого.

Answer 1

Вы можете рассматривать это как статический случай в 3D со временем как дополнительную координату. Круг с траекторией стал усечённым, а луч находится в плоскости времени = t _k . Если усеченные элементы расположены не слишком плотно, чем может помочь разбиение двоичного пространства (дерево k-d, ...).

Чтобы найти все разделы, пересекаемые лучом, сначала найдите раздел, где находится начало координат, а затем пройдите (в дереве) соседом раздела в направлении луча. Это зависит от используемого метода разделения. Он является линейным по количеству пересекаемых лучом перегородок.

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

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

1  |    E   /
   |   .   /
   |   .  / 
   |  .  /
   |  . /
0  | S /
t/X

Разделение в направлении X:

   |    E : /
   |   .  :/
   |   .  : 
   |  .  /:
   |  . / :
   | S /  :
          X

Эта трапеция будет проходить в обоих разделах.

Разделение по времени:

   |    E : /
   |   .  :/
   |   .  : 
t-------------------
   |  . / :
   | S /  :
          X

Трапеция из левого раздела X будет идти в обоих временных разделах, в то время как в правом разделе X она будет идти только в верхнем разделе.

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

Answer 2

(Размышляя вслух) Возможно, вы захотите использовать сетку октодерева или мультиразрешения с алгоритмом Брезенхэма, чтобы быстро устранить множество проверок?