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

Question

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

Итак, мой вопрос в том, может ли кто-нибудь предложить способ сделать это?Возможно, с помощью другой техники (возможно, 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, точка пересечения лежит на обоих отрезках прямой и задается точкой

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 также равен нулю, у вас есть коллинеарные отрезки.