Ускорьте обработку пересечений на коллекции 3D линий

Question

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

n = number of lines
for i: 1 to n-1 {
  for j: i+1 to n {
    if line(i) intersects line(j): {
      store (i,j)
    }
  }
}

Учитывая, что n будет большим, например, 1 миллион и более, какие оптимизации мы могли бы реализовать, чтобы ускорить обработку? Линии могут иметь любую длину, любую ориентацию.

Обновление 1: следующие комментарии помогли добавить это обновление:

1. Линии в нашей задаче - это "отрезки" с конечной длиной, ограниченной формой выпуклого тела.
2. Исследуется пересечение или "минимальное расстояние меньше допуска" (действительно, очень маленькое значение) между двумя линиями.

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

1. Оцените пересечение ограничивающего прямоугольника для всех линий, отметьте их пересечение. (это так быстро и дешево)
2. У теста пересечения для тех были отмечены.

Answer 1

Если линии действительно пересекаются в 3D, они также пересекаются в любой проекции в 2D. Таким образом, вы можете спроецировать все линии на плоскость и выполнить классическую линейную развертку, например алгоритм Бентли-Оттмана. Это выполняется за O((n+k) log n) времени и линейного пространства для n линий и k пересечений. Поскольку я предполагаю (как @Yves Daoust), что k должно быть очень маленьким, это кажется хорошей идеей. Очевидно, что вы можете получить некоторые ложные срабатывания, как, например, линии, которые пересекаются на плоскости, но не так в 3D. Проверка 2D пересечения в 3D - это операция с постоянным временем, поэтому в общем представлении нет большой проблемы.