¿Cómo determino el punto de intersección de dos líneas en GDI+?

Question

Estoy usando .NET para crear una aplicación con una superficie de dibujo, similar a Visio.La interfaz de usuario conecta dos objetos en la pantalla con Graphics.DrawLine.Esta implementación simple funciona bien, pero a medida que la superficie se vuelve más compleja, necesito una forma más sólida de representar los objetos.Uno de estos requisitos estrictos es determinar el punto de intersección de dos líneas para poder indicar la separación mediante algún tipo de gráfico.

Entonces mi pregunta es, ¿alguien puede sugerir una forma de hacer esto?¿Quizás con una técnica diferente (tal vez GraphViz) o un algoritmo?

Answer 1

La representación de líneas por y = mx + c es problemática para los gráficos por computadora, porque las líneas verticales requieren que m sea infinita.

Además, las líneas en los gráficos por computadora tienen un punto inicial y un punto final, a diferencia de las líneas matemáticas que tienen una extensión infinita.Por lo general, sólo nos interesa un cruce de líneas si el punto de cruce se encuentra en ambos segmentos de línea en cuestión.

Si tiene dos segmentos de línea, uno de los vectores x1 a x1+v1 y otro de los vectores x2 a x2+v2, entonces defina:

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)

donde para los vectores p=(px,py), q=(qx,qy), p.q es el producto escalar (px * qx + py * qy).Primero verifique si (v1.v1)(v2.v2) = (v1.v2)^2; si es así, las líneas son paralelas y no se cruzan.

Si no son paralelos, entonces si 0<=a<=1 y 0<=b<=1, el punto de intersección se encuentra en ambos segmentos de línea y está dado por el punto

x1 + a * v1

Editar La derivación de las ecuaciones para a y b es la siguiente.El punto de intersección satisface la ecuación vectorial.

x1 + a*v1 = x2 + b*v2

Tomando el producto escalar de esta ecuación con v1, y con v2, obtenemos dos ecuaciones:

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

que forman dos ecuaciones lineales para a y b.Resolver este sistema (multiplicando la primera ecuación por v2.v2 y la segunda por v1.v1 y restando, o de otra manera) da las ecuaciones para a y b.

Answer 2

pregunta al dr. matemáticas

Answer 3

Si gira su marco de referencia para alinearlo con el primer segmento de línea (de modo que el origen ahora es el inicio de la primera línea y el vector de la primera línea se extiende a lo largo del eje X), la pregunta es: ¿dónde está la segunda línea? golpee el eje X en el nuevo sistema de coordenadas.Ésta es una pregunta mucho más fácil de responder.Si se llama la primera línea A y está definido por A.O como el origen de la línea y siendo 'A.V' el vector de la línea, de modo que A.O + A.V es el punto final de la recta.El marco de referencia puede definirse mediante la matriz:

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

En coordenadas homogéneas, esta matriz proporciona una base para el marco de referencia que traza la línea. A a 0 a 1 en el eje X.Ahora podemos definir la línea transformada. B como:

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

Donde el * operador correctamente definido para coordenadas homogéneas (una proyección del espacio 3 al espacio 2 en este caso).Ahora sólo queda comprobar y ver dónde C golpea el eje X, que es lo mismo que resolver Y lado de la ecuación paramétrica de C para t:

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

Si t está en el rango de 0 a 1, entonces C toca el eje X dentro del segmento de línea.El lugar donde aterriza en el eje X está dado por el lado X de la ecuación paramétrica para C:

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

Si x está en el rango de 0 a 1, entonces la intersección está en la A segmento de línea.Entonces podemos encontrar el punto en el sistema de coordenadas original con:

p = A.O + A.V * x

Por supuesto, primero tendría que verificar si alguno de los segmentos de línea tiene longitud cero.También si C.V.Y = 0 tienes segmentos de recta paralelos.Si C.V.X también es cero, tienes segmentos de línea colineales.