Нахождение минимального расстояния между объектами и их пересечения - Алгоритмы - Ответ 17207208

Для примера рассмотрим два тетраэдра ABCD и KLMN. Нужно найти минимальное расстояние между всеми парами граней (треугольниками), выбрать наименьшее - это и будет минимальный просвет.

F1 - Функция нахождения расстояния "грань-грань"

1.1. Фиксируем, ABC и KLM параллельны или нет.

1.2 Находим минимальные расстояния между ребрами AB, BC, AC и гранью KLM, а также между ребрами KL, LM, KM и гранью ABC. То есть шесть раз запускаем функцию F2.

1.3 Если ABC и KLM непараллельны, выбираем наименьшее расстояние из шести минимальных.

1.4 Если ABC и KLM параллельны, то один из вызовов функции F2 может прерваться при условии нахождения нормали к грани.

F2 - Функция нахождения расстояния "ребро-грань"

2.1. Фиксируем, AB и KLM параллельны или нет.

2.2 Находим минимальные расстояния между вершинами A, B и гранью KLM, а также между ребром AB и ребрами KL, LM, KM. То есть два раза запускаем функцию F4 и три раза - функцию F3.

2.3 Если AB и KLM непараллельны, выбираем наименьшее расстояние из пяти минимальных.

2.4 Если AB и KLM параллельны, то один из вызовов функций F3, F4 может прерваться при условии нахождения нормали к грани или ребру.

F3 - Функция нахождения расстояния "ребро-ребро"

3.1. Фиксируем, AB и KL параллельны или нет.

3.2 Находим минимальные расстояния между вершинами A, B и ребром KL, а также между ребром AB и вершинами K, L. То есть четыре раза запускаем функцию F5.

3.3 Если AB и KL непараллельны, выбираем наименьшее расстояние из четырех минимальных.

3.4 Если AB и KL параллельны, то один из вызовов функций F5 может прерваться при условии нахождения нормали к ребру.

F4 - Функция нахождения расстояния "вершина-грань"

4.1. Находим проекцию точки A на неограниченную плоскость KLM.

4.2. Если проекция точки на плоскости находится внутри многоугольника KLM, то искомое расстояние - это расстояние между точкой A и неограниченной плоскостью KLM. Конец функции F4.

4.3 Если точка проецируется вне грани KLM, то находим минимальные расстояния между вершиной A и ребрами KL, LM, KM. То есть три раза запускаем функцию F5.

4.4 Выбираем наименьшее расстояние из трех минимальных.

F5 - Функция нахождения расстояния "вершина-ребро"

5.1. Находим проекцию точки A на неограниченную прямую KL.

5.2. Если проекция точки на прямой находится на отрезке KL, то искомое расстояние - это расстояние между точкой A и неограниченной прямой KL. Конец функции F5.

5.3 Если точка проецируется вне отрезка KL, то находим минимальные расстояния между вершинами A и K, L. То есть два раза запускаем функцию F6.

5.4 Выбираем наименьшее расстояние из двух минимальных.

F6 - Функция нахождения расстояния "вершина-вершина"

R^2 = (X1-X2)^2 + (Y1-Y2)^2 + (Z1-Z2)^2

Корень необязательно вычислять, все равно минимальное число ищем.

Добавлено через 6 минут

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

Вернуться к обсуждению:

Нахождение минимального расстояния между объектами и их пересечения Алгоритмы