Пересечение сферы и треугольника
Занимаюсь сейчас перемещением сферы в пространстве со столкновениями с другими обьектами. Возникла проблемы с решением задачи про пересечение сферы и треугольника (из которых у меня состоят многогранники).
Даны координаты центра сферы и ее радиус, а так же три точки треугольника в пространстве. Необходимо узнать, пересекает ли треугольник сферу (своей стороной или площадью).
Еще более формально: Дана точка O(x0, y0, z0) - центр сферы. Дано вещественное число r - радиус сферы. Даны три вершины треугольника: A(x1, y1, z1), B(x2, y2, z2), C(x3, y3, z3). Необходимо ответить на вопрос: имеет ли треугольник хотя бы одну общую точку со сферой?
Ответы (3 шт):
Самый простой способ:
- Сразу проверим, не лежит ли весь треугольник в сфере (ведь тогда он ее точно не пересекает). Для этого сравним расстояние от его вершин до центра сферы с ее радиусом. Если все три точки - внутри, то сразу можно давать ответ 'нет'. Иначе:
- Найдем ближайшую к центру сферы точку треугольника. Для этого проецируем центр на плоскость треугольника. Если проекция лежит внутри треугольника, то переходим к п.4.
- Иначе искомая точка лежит на сторонах треугольника. Найдем ее через поиск минимального расстояния до отрезков - тех самых сторон.
- Проверим, лежит ли найденная точка внутри сферы. Если да, то пересечение есть, иначе - нет.
Задачу можно свести к задаче "Определите, если ли общие точки у 2D фигуры и шара".
- Если все точки 2D фигуры удалены от центра шара на расстояние
<= r, то 2D фигура находится внутри шара. Если
nточек внутри, аkточек снаружи, гдеn > 0иk > 0, то 2D фигура пересекает шар.Осталось рассмотреть случай, когда все точки - снаружи. Очевидно, что пересечение будет лишь в том случае, когда самая близкая к центру окружности точка
ПЛОСКОСТИ ФИГУРЫна расстоянии<= rи когда эта точка лежит в фигуре. Если предыдущие два условия не были выполнены, то проверяйте,<= rвсе перпендикуляры к отрезкам и врезаются ли эти перпендикуляры в отрезки. Если врезаются, и длина<= r(хоть один если найдется такой), то фигура пересекает шар.
Рекомендуемая последовательность действий.
- Построить плоскость треугольника.
- Построить проекцию на эту плоскость центра сферы, а затем и окружность пересечения сферы и плоскости.
- Решить задачу наличия общей точки у треугольника и окружности на плоскости.
Для упрощения расчёта рекомендуется выполнить поворот относительно центра сферы так, чтобы плоскость треугольника была перпендикулярна одной из координатных прямых.