Быстрый поиск пересечений треугольников (для 2D и 3D)?

Question

[Vitaliy]

Какая структура данных для этого подойдет? Для малого количества треугольников можно напрямую сравнивать каждый с каждым, но если их количество значительно увеличивается (например до 1 000 и 100), тогда придется делать 100 000 проверок.

Answer 1

[Ди Ма]

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

Из книги "Сюрреализм на javaScript"

Answer 2

[Александр Павлюк]

Впишите каждый треугольник в прямоугольник и проверяйте на пересечение только те треугольники, у которых пересекаются описывающие их прямоугольники. А разом отсечь кучу лишних прямоугольников можно через quad-tree

Comments

[Vitaliy]

спасибо, попробую (кстати попробую списать в окружность/сферу). Но как правильно распределять по дереву, если прямоугольники могут частично лежать в одной и другой ветке?

[Александр Павлюк]

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

Answer 3

[SolidMinus]

Попробуй пойти в сторону задания вершин треугольников как координат в пространстве.

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

Попробуй двигаться в этом направлении: www.cleverstudents.ru/line_and_plane/parametric_eq...

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

Если я прав, то задача сведется к вычислению огромной матрицы.

Comments

[Vitaliy]

Если я прав, то задача сведется к вычислению огромной матрицы.

а значит это не поможет уменьшить количество операция?!

[SolidMinus]

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