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

Question

Я использую .NET для создания приложения с поверхностью для рисования, аналогичной Visio. Пользовательский интерфейс соединяет два объекта на экране с Graphics.DrawLine. Эта простая реализация прекрасно работает, но поскольку поверхность становится более сложной, мне нужен более надежный способ представления объектов. Одним из этих строгих требований является определение точки пересечения для двух линий, чтобы я мог обозначить разделение с помощью некоторой графики.

Итак, мой вопрос: кто-нибудь может предложить способ сделать это? Возможно, с другой техникой (возможно, GraphViz) или алгоритмом?

Answer 1

Представление линий 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, точка пересечения лежит на обоих отрезках линии и задается точкой </p>

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.

Answer 2

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

Answer 3

Если вы поворачиваете систему отсчета, чтобы выровнять ее по первому сегменту линии (таким образом, начало координат теперь является началом первой линии, а вектор для первой линии простирается вдоль оси 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 также равно нулю, у вас есть коллинеарные отрезки.