Как небольшая поправка к ответам, приведенным выше, использование трехмерных перекрестных произведений для вычисления пересечения двухмерных линий в значительной степени наименее эффективно. Перекрестные продукты не оптимизируют SIMD вообще (если только вы не пойдете на все, чтобы использовать структуру данных SOA, но даже если это чрезвычайно расточительный подход). Наилучший подход - использовать старые добрые уравнения одновременности.
Начиная с наших точек ввода, которые определяют линию:
line1: [(x1, y1), (x2, y2)]
line2: [(x3, y3), (x4, y4)]
Вычислить некоторые векторы направления:
// 1st direction
u1 = x2 - x1
v1 = y2 - y1
D1 = [u1, v1]
// 2nd direction
u2 = x4 - x3
v2 = y4 - y3
D2 = [u2, v2]
Теперь давайте переформулируем уравнения линий в виде лучей и составим уравнение для любой точки вдоль этих лучей:
// coords of a point 'd1' distance along the 1st ray
Px = x1 + d1*u1
Py = y1 + d1*v1
// coords of a point 'd2' distance along the 2nd ray
Px = x3 + d2*u2
Py = y3 + d2*v2
Давайте предположим, что линии пересекаются, что означает, что оба P будут одинаковыми, что позволяет нам утверждать:
x1 + d1*u1 = x3 + d2*u2
y1 + d1*v1 = y3 + d2*v2
Я не буду проходить каждый шаг, но переставлю оба уравнения в терминах d1, и мы получим:
d1 = x3 + d2*u2 - x1
---------------
u1
d1 = y3 + d2*v2 - y1
---------------
v1
Теперь у нас есть два уравнения для d1, поэтому давайте создадим другое уравнение для одновременного получения значения для d2:
x3 + d2*u2 - x1 y3 + d2*v2 - y1
--------------- = ---------------
u1 v1
Переставить для изоляции d2:
d2 = u1(y3 - y1) - v1(x3 - x1)
-------------------------
v1*u2 - u1*v2
Если (v1 * u2 - u1 * v2) окажется равным нулю, для этого уравнения нет решения (назовем его детерминантом, потому что это то, что есть!). Если определитель не равен нулю, то просто вычислите d2, используя приведенное выше уравнение, и вернитесь к одному из наших предыдущих уравнений, чтобы найти значение точки:
Px = x3 + d2*u2
Py = y3 + d2*v2
Некоторый непроверенный код C ++:
bool computeIntersectPoint(
float x1, float y1,
float x2, float y2,
float x3, float y3,
float x4, float y4,
float outPoint[2])
{
// compute direction vectors
// in some cases, it can be worth
// storing the lines as rays as an
// optimisation. (avoids 4 subs)
const float u1 = x2 - x1;
const float v1 = y2 - x1;
const float u2 = x4 - x3;
const float v2 = y4 - x3;
// check to see if we have a solution
// 1 mul, 1 fmsub
float determinant = v1*u2 - u1*v1;
if(determinant == 0)
return false;
// 2 sub, 1 mul, 1 fmsub
float temp = u1 * (y3 - y1) - v1 * (x3 - x1);
// 1 div
float intersectDistance = temp / determinant;
// 2 fma
outPoint[0] = intersectDistance * u2 + x3;
outPoint[1] = intersectDistance * v2 + y3;
return true;
}
Быстрое доказательство десмоса: https://www.desmos.com/calculator/gtlmnmzn6l
Здесь стоит сравнить количество команд между двумя подходами здесь. Для трехмерного перекрестного произведения требуется 3 мульт и 3 инструкции fmsub (или 6 мул + 3 суб, если FMA недоступен). Так как у нас есть 3 из них, мы до: 9 mul и 9 fmsub ops. Добавьте в 2 подразделения, и мы получим:
9 mul
9 fmsub
2 div
Подход, который я разместил, потребует:
1 div
6 sub
4 fma
2 mul
Хотя вы можете сохранить 4 из этих подводных лодок, если вам удастся сохранить линии в виде лучей.