15

Занимаюсь сейчас перемещением сферы в пространстве со столкновениями с другими обьектами. Возникла проблемы с решением задачи про пересечение сферы и треугольника (из которых у меня состоят многогранники).

Даны координаты центра сферы и ее радиус, а так же три точки треугольника в пространстве. Необходимо узнать, пересекает ли треугольник сферу (своей стороной или площадью).

Еще более формально: Дана точка O(x0, y0, z0) - центр сферы. Дано вещественное число r - радиус сферы. Даны три вершины треугольника: A(x1, y1, z1), B(x2, y2, z2), C(x3, y3, z3). Необходимо ответить на вопрос: имеет ли треугольник хотя бы одну общую точку со сферой?

13
  • 1
    из вашего вопроса ничего не понятно кроме того что вы чем-то занимаетесь, уточните где вы это занимаетесь перемещениями сферы, если есть код то приложите его, иначе вопрос просто закроют из-за недостатка информации :(
    – Andrew
    14 апр 2020 в 10:46
  • 3
    @Andrew, разве на stackoverflow нельзя задавать вопросы, связанные с кодом не напрямую? Мне интереснее решение, чем готовый код на определенном языке, который я скопирую. Можете посоветовать платформу, на которой за четкую постановку задачи вопрос не снимают из-за отсутствия кода?
    – KingCake
    14 апр 2020 в 11:16
  • можно конечно и не связанный с кодом, но просто очень непонятно что вы делаете, если у вас возникла проблема то есть уже какой-то код наверное
    – Andrew
    14 апр 2020 в 11:19
  • 6
    имхо это нормальный вопрос, и достаточно информации 14 апр 2020 в 11:21
  • 1

3 ответа 3

3

Рекомендуемая последовательность действий.

  1. Построить плоскость треугольника.
  2. Построить проекцию на эту плоскость центра сферы, а затем и окружность пересечения сферы и плоскости.
  3. Решить задачу наличия общей точки у треугольника и окружности на плоскости.

Для упрощения расчёта рекомендуется выполнить поворот относительно центра сферы так, чтобы плоскость треугольника была перпендикулярна одной из координатных прямых.

2

Самый простой способ:

  1. Сразу проверим, не лежит ли весь треугольник в сфере (ведь тогда он ее точно не пересекает). Для этого сравним расстояние от его вершин до центра сферы с ее радиусом. Если все три точки - внутри, то сразу можно давать ответ 'нет'. Иначе:
  2. Найдем ближайшую к центру сферы точку треугольника. Для этого проецируем центр на плоскость треугольника. Если проекция лежит внутри треугольника, то переходим к п.4.
  3. Иначе искомая точка лежит на сторонах треугольника. Найдем ее через поиск минимального расстояния до отрезков - тех самых сторон.
  4. Проверим, лежит ли найденная точка внутри сферы. Если да, то пересечение есть, иначе - нет.
6
  • Представь, что в п. 4 вся проекция сферы - внутри треугольника... так что способ-то простой - но неправильный.
    – Akina
    14 апр 2020 в 20:39
  • @Akina, никак не придумаю случая, в котором пункту 4 мешало бы то, что вся проекция сферы внутри треугольника. Если какая-то его точка лежит внутри сферы, и мы знаем, что хотя бы одна есть снаружи, то треугольник сферу пересекает, разве нет?
    – KingCake
    15 апр 2020 в 10:58
  • Если вся проекция сферы на плоскость треугольника (большой окружности, параллельной плоскости) лежит внутри треугольника - точек пересечения НЕТ.
    – Akina
    15 апр 2020 в 11:43
  • 1
    Почему же нет? Например, большой треугольник, разрезающий сферу в пространстве пополам, всю ее проекцию имеет на себе, но пересечения есть. В п.4. написано проверить наличие точки внутри сферы, а не окружности ее проекции
    – KingCake
    15 апр 2020 в 11:48
  • Приехали... то есть в твоём вопросе сфера - это тонкая оболочка, а вот треугольник - это не только его стороны, но и все внутренние точки??? блин, а указать эту (весьма неочевидную) мелочь в постановке задачи - не? Но если так - то задача-то тривиальна. См. ответ Мирона.
    – Akina
    15 апр 2020 в 11:53
1

Задачу можно свести к задаче "Определите, если ли общие точки у 2D фигуры и шара".

  1. Если все точки 2D фигуры удалены от центра шара на расстояние <= r, то 2D фигура находится внутри шара.
  2. Если n точек внутри, а k точек снаружи, где n > 0 и k > 0, то 2D фигура пересекает шар.

  3. Осталось рассмотреть случай, когда все точки - снаружи. Очевидно, что пересечение будет лишь в том случае, когда самая близкая к центру окружности точка ПЛОСКОСТИ ФИГУРЫ на расстоянии <= r и когда эта точка лежит в фигуре. Если предыдущие два условия не были выполнены, то проверяйте, <= r все перпендикуляры к отрезкам и врезаются ли эти перпендикуляры в отрезки. Если врезаются, и длина <= r(хоть один если найдется такой), то фигура пересекает шар.

4
  • Утверждение (3) - неполно. Что делать, если: все вершинные точки вовне сферы, а самая близкая к центру сферы точка плоскости вовне фигуры? ситуация допускает и наличие, и отсутствие точки пересечения.
    – Akina
    15 апр 2020 в 11:50
  • @Akina дополнил
    – Miron
    15 апр 2020 в 12:02
  • См. i.stack.imgur.com/1KvMZ.png
    – Akina
    15 апр 2020 в 12:04
  • @Akina В этом случае столкновения не происходит. Если вы даже чуть левее подвинете(чтобы было столкновение), то с моим дополнением по алгоритму выйдет, что общие точки есть
    – Miron
    15 апр 2020 в 12:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.