Обнаружение перекрытия прямоугольных призм

Question

Учитывая трехмерную систему координат и прямоугольные призмы с неотрицательной начальной точкой и неотрицательным размером (например, начинается с (0, 2, 5) и имеет размер (9, 20, 5)): как лучше всего проверить, есть ли другая прямоугольная призмапересекается с одной из призм уже в системе координат?В конечном счете, цель будет состоять в том, чтобы выполнить эту проверку для всех присутствующих призм, для того чтобы выполнить эту задачу, достаточно иметь возможность проверить одну из них.

Информация: начальные точки и размеры - это три набора неотрицательных длинЯ ищу элегантное решение, которое в меру быстрое.

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

Answer 1

Хороший алгоритмический подход для больших наборов данных

Храните свои призмы в R-Tree . Для прямоугольных коаксиальных призм поиск и вставка должны иметь порядок log(n).

Существует несколько пакетов Python для R-Trees. Используя Rtree 0.6.0 , ваш код будет таким простым:

>>> from rtree import Rtree
>>> idx = Rtree()
>>> minx, miny, maxx, maxy = (0.0, 0.0, 1.0, 1.0)
>>> idx.add(0, (minx, miny, maxx, maxy))
>>> list(idx.intersection((1.0, 1.0, 2.0, 2.0)))
[0L]
>>> list(idx.intersection((1.0000001, 1.0000001, 2.0, 2.0)))
[]

Практичный, но быстрый подход

Сохраните ваши данные в базе данных sqlite, которую можно создать в файле или в памяти с использованием очень небольшого количества строк кода (существует много реализаций Java ). Создайте таблицу с именем, скажем, prisms, столбцы которой будут id, min_x, min_y, min_z, max_x, max_y, max_z. Индексируйте каждую строку.

Вставка O(1), и проверка на пересечение следует Подход Магнуса Скога , учитывая new_min_x, new_min_y, new_min_z, new_max_x, new_max_y, new_max_z:

SELECT COUNT(*) FROM prisms
   WHERE (new_min_x BETWEEN min_x and max_x OR new_max_x BETWEEN min_x and max_x)
   AND   (new_min_y BETWEEN min_y and max_y OR new_max_y BETWEEN min_y and max_y)
   AND   (new_min_z BETWEEN min_z and max_z OR new_max_z BETWEEN min_z and max_z)

Answer 2

Допустим, у вас есть две призмы A и B. Если B пересекается с A, это отрицание того, что вы не полностью вправо, влево, вверх, вниз и т. Д.

if not (B.x > A.x+A.dx or B.x+B.dx < A.x or
        B.y > A.y+A.dy or B.y+B.dy < A.y or
        B.z > A.z+A.dz or B.z+B.dz < A.z)
        // B intersects A

Answer 3

Призма, которая начинается с (0, 2, 5) и имеет размер (9, 20, 5), заканчивается на (9, 22, 10).

Чтобы проверить наличие перекрывающихся призм (A и B), используйте начальную и конечную точкиэти.Две призмы должны перекрываться во всех измерениях.

Чтобы проверить перекрытие в измерении X, используйте это:

If (A.startX <= B.endX) and (B.startX <= A.endX) 

Следовательно:

If 
      (A.startX <= B.endX) and (B.startX <= A.endX) 
  and (A.startY <= B.endY) and (B.startY <= A.endY) 
  and (A.startZ <= B.endZ) and (B.startZ <= A.endZ) 
Then
    (A and B overlap)

Приведенная выше проверкарезультат True, когда две призмы имеют хотя бы одну общую точку.Если вы этого не хотите и хотите, чтобы перекрывающееся пространство было больше, чем просто точка, отрезок или прямоугольная поверхность, а призма, то замените <= на <.

Answer 4

Точно так же, как и для проверки сегментов на линии.Если начало или конец B находится между началом и концом A, они перекрываются.

Единственное отличие состоит в том, что они должны перекрываться во всех трех измерениях.