Comment déterminer le point d'intersection de deux lignes dans GDI +?

Question

J'utilise .NET pour créer une application avec une surface de dessin similaire à Visio. L'interface utilisateur connecte deux objets à l'écran avec Graphics.DrawLine. Cette implémentation simple fonctionne bien, mais à mesure que la surface devient plus complexe, j'ai besoin d'un moyen plus robuste de représenter les objets. L’une de ces exigences robustes consiste à déterminer le point d’intersection de deux lignes afin que je puisse indiquer la séparation via une sorte de graphique.

Donc ma question est la suivante: quelqu'un peut-il suggérer un moyen de le faire? Peut-être avec une technique différente (peut-être GraphViz) ou un algorithme?

Answer 1

La représentation des lignes par y = mx + c est problématique pour l’infographie, car les lignes verticales exigent que m soit infini.

De plus, les lignes de l’infographie ont un point de départ et de fin, contrairement aux lignes mathématiques dont l’étendue est infinie. On ne s’intéresse généralement à un croisement de lignes que si le point de croisement se trouve sur les deux segments de ligne en question.

Si vous avez deux segments de droite, l'un des vecteurs x1 à x1 + v1 et l'autre des vecteurs x2 à x2 + v2, définissez:

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)

où pour les vecteurs p = (px, py), q = (qx, qy), p.q est le produit scalaire (px * qx + py * qy). Commencez par vérifier si (v1.v1) (v2.v2) = (v1.v2) ^ 2 - si c'est le cas, les lignes sont parallèles et ne se croisent pas.

Si elles ne sont pas parallèles, alors si 0 < = a < = 1 et 0 < = b < = 1, le point d'intersection est situé à la fois sur les segments de ligne, et est donné par le point

x1 + a * v1

Modifier La dérivation des équations pour a et b est la suivante. Le point d'intersection vérifie l'équation vectorielle

x1 + a*v1 = x2 + b*v2

En prenant le produit scalaire de cette équation avec v1 et avec v2, nous obtenons deux équations:

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

qui forment deux équations linéaires pour a et b. La résolution de ce système (en multipliant la première équation par v2.v2 et la seconde par v1.v1 et en soustrayant, ou autrement) donne les équations pour a et b.

Answer 2

demander à dr. maths

Answer 3

Si vous faites pivoter votre cadre de référence pour l'aligner sur le premier segment de ligne (de sorte que l'origine est maintenant le début de la première ligne et que le vecteur de la première ligne s'étend le long de l'axe des abscisses), la question devient la deuxième ligne a frappé l'axe des X dans le nouveau système de coordonnées. C'est une question beaucoup plus facile à répondre. Si la première ligne est appelée A, elle est définie par A.O comme origine de la ligne et "A.V" comme vecteur de la ligne, de sorte que A.O + A.V soit le point final de la ligne. Le référentiel peut être défini par la matrice:

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

En coordonnées homogènes, cette matrice fournit une base pour le cadre de référence qui mappe la ligne B à 0 à 1 sur l’axe des X. Nous pouvons maintenant définir la ligne transformée * comme suit:

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

Où l'opérateur C correctement défini pour des coordonnées homogènes (une projection de 3 espace sur 2 espace dans ce cas). Il ne reste plus maintenant qu’à vérifier où Y se situe sur l’axe des X, ce qui revient à résoudre le côté t de l’équation paramétrique de x pour C.V.Y = 0:

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

Si C.V.X est compris entre 0 et 1, alors <=> frappe l'axe des X situé à l'intérieur du segment de ligne. La position sur l'axe X est donnée par le côté X de l'équation paramétrique pour <=>:

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

Si <=> est compris entre 0 et 1, l'intersection se trouve sur le segment de ligne <=>. Nous pouvons ensuite trouver le point dans le système de coordonnées d'origine avec:

p = A.O + A.V * x

Vous devez bien sûr vérifier d’abord si l’un ou l’autre segment de ligne a une longueur nulle. Également si <=> vous avez des segments de ligne parallèles. Si <=> est également égal à zéro, vous avez des segments linéaires colinéaires.