Пересечение сегментов конус-линия 2D

Работа с полярными координатами может помочь. Здесь вместо того, чтобы представлять точку как (x, y), вы представляете ее как (r, угол), где r — это расстояние от начала координат, а угол — это угол, образованный с выбранной осью (что соответствует углу 0).

В вашем случае, если вы установите P (x, y) как источник и один из лучей конуса как угол = 0 и найдете полярные координаты конечных точек отрезка прямой, скажем (r1, ang1) и (r2, ang2), то вам необходимо, чтобы следующие четыре условия были истинными, чтобы отрезок прямой находился полностью внутри (включая границу) конуса.

r1 <= r
r2 <= r

ang1 <= theta
ang2 <= theta

где r — радиус конуса, а тета — угол зрения, и вы выбрали ось так, чтобы вращение против часовой стрелки давало соответствующий положительный угол.

Переключение между полярными и (x, y) (называемыми прямоугольными) координатами очень просто, и вы можете найти его по ссылке в вики, которую я дал выше.

Чтобы определить, пересекает ли любая точка отрезка линии кривую, вы можете использовать полярное уравнение прямой, приведенное здесь: http://mathforum.org/dr.math/faq/formulas/faq.polar.html

Мы можем использовать полярную нормальную форму

R = p sec(ang - omega)

Мы можем вычислить p и omega, учитывая две конечные точки отрезка, следующим образом:

У нас есть

p = r1 * cos(ang1-omega) = r2*cos(ang2-omega)

Используя cos(x-y) = cos(x)*cos(y) + sin(x)*sin(y), мы получаем

[r1*cos(ang1) - r2*cos(ang2)] * cos(omega) =  [r2*sin(ang2) - r1*sin(ang1)] * sin(omega)

Таким образом, вы можете вычислить tan(omega) = sin(omega)/cos(omega) и использовать arctan (обратную функцию тангенса), чтобы получить значение омеги. Как только вы узнаете, что такое омега, вы сможете найти p.

Теперь нам нужно узнать, есть ли на этой линии какая-то комбинация (R, ang), такая что

R <= r
0 <= ang <= theta
min{ang1, ang2} <= ang <= max{ang1, ang2}

(Обратите внимание, что r — радиус конуса, а тета — угол зрения, ang1 — угол P1, а ang2 — угол P2).

Уравнение можно переписать как

Rcos(ang-omega) = p

Теперь cos(ang-omega) — очень хорошая функция с точки зрения монотонности, и вам нужно рассматривать ее только в интервале [min{ang1, ang2}, max{ang1, ang2}].

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

Остальное я оставлю тебе.

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

Если вы сохраните его 2D, как указано выше, пересечение можно рассчитать следующим образом:

Начальная точка отрезка — S1, конечная — S2. Левый край кода — это вектор по ребру C1, правый край — C2, начало кода — O.

Возьмите знак компонента Z векторного произведения вектора, образованного из (O в S1) и C1.

Возьмите знак компонента Z векторного произведения вектора от (O до S2) и C1. Если знаки различаются, ваши начальная и конечная точки находятся на противоположных сторонах C1 и, следовательно, должны пересекаться. Если нет, сделайте те же сравнения с C2 вместо C1.

Если знаки ни на одной из сторон не различаются, пересечения ребер нет.

В 3D все немного сложнее. Я гуглил и находил пересечение конусообразных сфер любое количество раз. Делать это для строк было бы очень похоже, мне просто нужно немного подумать об этом :)

Быстрый поиск в Google «пересечения конусной линии» дал множество результатов. Основная идея состоит в том, чтобы сформировать плоскость из начала конуса и начальной и конечной точек линии. Получив это, вы можете взять угол между этой плоскостью и направлением нормали конуса. Если этот угол меньше угла разброса на конусе, у вас есть пересечение.