Como faço para determinar o ponto de interseção de duas linhas em GDI +?

Question

Eu estou usando .NET para fazer uma aplicação com uma superfície de desenho, semelhante ao Visio. A interface do usuário se conecta dois objetos na tela com Graphics.DrawLine. Essa implementação simples funciona bem, mas como a superfície se torna mais complexa, eu preciso de uma maneira mais robusta para representar os objetos. Um desses requisitos robustos é a determinação do ponto de intersecção de duas linhas para que eu possa indicar a separação através de algum tipo de gráfico.

Então, minha pergunta é, alguém pode sugerir uma maneira de fazer isso? Talvez com uma técnica diferente (talvez GraphViz) ou um algoritmo?

Answer 1

A representação de linhas por y = mx + c é problemático para gráficos de computador, porque as linhas verticais exigem m de ser infinita.

Além disso, as linhas em gráficos de computador têm um ponto inicial e final, ao contrário de linhas matemáticas que são infinitos em extensão. Um é geralmente interessados ??apenas em um cruzamento de linhas se as mentiras de ponto de cruzamento em ambos os segmentos de linha em questão.

Se você tem dois segmentos de linha, um de vetores x1 para x1 + v1, e um de vetores x2 para x2 + v2, então:

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)

onde pela vetores p = (px, py), q = (qx, qy), p.q é o produto escalar (px * qx + py * qy). Primeiro verifique se (v1.v1) (v2.v2) = (v1.v2) ^ 2 -. Se assim for, as linhas são paralelas e não se cruza

Se eles não são paralelas, em seguida, se 0 <= a <= 1 e 0 <= b <= 1, situa-se no ponto de intersecção de ambos os segmentos de linha, e é dado pelo ponto

x1 + a * v1

Editar A derivação das equações para a e b é como se segue. Os satisfaz ponto de intersecção do vetor equação

x1 + a*v1 = x2 + b*v2

Ao tomar o produto escalar desta equação com v1, e com v2, temos duas equações:

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

que formam duas equações lineares para a e b. Resolver este sistema (através da multiplicação da primeira equação por v2.v2 e a segunda por v1.v1 e subtraindo, ou de outra forma) dá as equações para a e b.

Answer 2

pedir dr. matemática

Answer 3

Se você rodar o seu quadro de referência para alinhar com o primeiro segmento de linha (para que a origem é agora o início da primeira linha, e o vector para a primeira linha se estende ao longo do eixo X), a questão torna-se, de onde vem a segunda linha acertar o eixo X no novo sistema de coordenadas. Esta é uma questão muito mais fácil resposta. Se a primeira linha é chamada A e é definido por A.O como a origem da linha e 'A.V' ser o vetor da linha para que A.O + A.V é o ponto final da linha. O quadro de referência podem ser definidos pela matriz:

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

coordenadas homogéneas desta matriz constitui uma base para a estrutura de referência que mapeia o A linha de 0-1 no eixo dos X. Podemos agora definir o B linha transformado como:

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

Sempre que o operador * correctamente definida para coordenadas homogéneas (uma projecção a partir de 3 espaço para duas espaço neste caso). Agora tudo o que resta é verificar e ver onde C atinge o eixo X, que é o mesmo que resolver lado Y da equação paramétrica de C para t:

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

Se t está no intervalo de 0 a 1, então C atinge o eixo X no interior do segmento de linha. O lugar que ele cair no eixo X é dada pelo lado do X da equação paramétrica para C:

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

Se x está na faixa de 0 a 1, então a interseção está no segmento de linha A. Podemos, então, encontrar o ponto no original sistema de coordenadas com:

p = A.O + A.V * x

Você seria, naturalmente, tem que verificar primeiro para ver se qualquer segmento de linha é de comprimento zero. Além disso, se C.V.Y = 0 você tem segmentos de linha paralelos. Se C.V.X também é zero você tem segmentos de linha colineares.