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

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

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

Ответы

Ответ 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.

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