Конус-Лайн Сегмент Пересечение 2D

Question

Я хотел бы знать, есть ли способ определить, пересекается ли конус с (конечным) отрезком. Конус - фактически круг, расположенный в P (x, y) с полем зрения тета-градуса и радиусом r:

Иллюстрация http://img180.imageshack.us/img180/3461/conevision.png

Я пытаюсь сделать это в C #, но я понятия не имею, как это сделать, так что сейчас это то, что я делаю:

1. Проверьте, пересекается ли отрезок с окружностью;
2. Если отрезок прямой пересекается с окружностью, тогда я проверяю каждую точку отрезка, используя найденную мной функцию .

Но я не думаю, что это лучший способ сделать это. У кого-нибудь есть идея?

Для получения дополнительной информации мне нужна эта функция, чтобы создать какой-то простой симулятор зрения.

Answer 1

Работа с Полярные координаты может помочь. Здесь, вместо того, чтобы представлять точку как (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}].

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

Я оставлю вам остальное.

Answer 2

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

Начальная точка сегмента линии - S1, конечная точка - S2. Левый край кода - это вектор вдоль края C1, правый край - C2, источник кода - O.

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

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

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

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

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

Answer 3

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