Как определить точку пересечения двух линий в GDI +?

спросить др. математика

Представление линий с помощью y = mx + c проблематично для компьютерной графики, потому что вертикальные линии требуют, чтобы m было бесконечным.

Кроме того, линии в компьютерной графике имеют начальную и конечную точки, в отличие от математических линий, которые имеют бесконечную протяженность. Обычно интересует пересечение линий только в том случае, если точка пересечения лежит на обоих рассматриваемых сегментах линии.

Если у вас есть два линейных сегмента, один от векторов x1 до x1 + v1 и один от векторов x2 до x2 + v2, тогда определите:

a = (v2.v2 v1.(x2-x1) - v1.v2 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x2-x1) - v1.v1 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)

где для векторов p = (px, py), q = (qx, qy), p.q - скалярное произведение (px * qx + py * qy). Сначала проверьте, если (v1.v1) (v2.v2) = (v1.v2) ^ 2 - если да, то линии параллельны и не пересекаются.

Если они не параллельны, то если 0 <= a <= 1 и 0 <= b <= 1, точка пересечения лежит на обоих отрезках прямой и задается точкой

x1 + a * v1

Редактировать Вывод уравнений для a и b следующий. Точка пересечения удовлетворяет векторному уравнению

x1 + a*v1 = x2 + b*v2

Взяв скалярное произведение этого уравнения с v1 и с v2, мы получим два уравнения:

v1.v1*a - v2.v1*b = v1.(x2-x1)
v1.v2*a - v2.v2*b = v2.(x2-x1)

которые образуют два линейных уравнения для a и b. Решение этой системы (умножением первого уравнения на v2.v2, а второго на v1.v1 и вычитанием или иным образом) дает уравнения для a и b.

Если вы поверните систему отсчета, чтобы выровнять ее с первым сегментом линии (таким образом, начало координат теперь является началом первой линии, а вектор для первой линии простирается вдоль оси X), возникает вопрос: где находится вторая линия? ударьте по оси X в новой системе координат. На этот вопрос гораздо легче ответить. Если первая линия называется A и определяется A.O как начало линии, а «A.V» - вектор линии, то есть A.O + A.V является конечной точкой линии. Систему отсчета можно определить с помощью матрицы:

    | A.V.X   A.V.Y   A.O.X |
M = | A.V.Y  -A.V.X   A.O.Y |
    |   0       0       1   |

В однородных координатах эта матрица обеспечивает основу для системы отсчета, которая отображает линию A от 0 до 1 на оси X. Теперь мы можем определить преобразованную линию B как:

C.O = M*(B.O)
C.V = M*(B.O + B.V) - C.O

Где оператор * правильно определен для однородных координат (в данном случае проекция из 3-х пространств на 2-х пространственные). Теперь все, что осталось, это проверить и увидеть, где C попадает в ось X, что совпадает с решением стороны Y параметрического уравнения C для t:

C.O.Y + t * C.V.Y = 0
     -C.O.Y
t = --------
      C.V.Y

Если t находится в диапазоне от 0 до 1, то C попадает в ось X внутри линейного сегмента. Место, куда он попадает по оси X, задается стороной X параметрического уравнения для C:

x = C.O.X + t * C.V.X

Если x находится в диапазоне от 0 до 1, то пересечение находится на линейном сегменте A. Затем мы можем найти точку в исходной системе координат с помощью:

p = A.O + A.V * x

Вы, конечно, должны сначала проверить, имеет ли какой-либо линейный сегмент нулевую длину. Также, если C.V.Y = 0 у вас есть параллельные отрезки линии. Если C.V.X также равен нулю, у вас есть коллинеарные отрезки линии.