Déterminer si les deux rayons se croisent
J'ai deux rayons sur un plan en 2D qui s'étendent à l'infini, mais tous les deux ont un point de départ. Ils sont tous deux décrits par un point de départ et un vecteur dans la direction des rayons s'étendant à l'infini. Je veux savoir si les deux rayons se croisent, mais je n'ai pas besoin de savoir où ils se croisent (il fait partie d'un algorithme de détection de collision).
Tout ce que j'ai regardé jusqu'à présent décrit les trouver le point d'intersection de deux lignes ou segments de ligne. Est-il un algorithme rapide pour résoudre ce problème?
- En 2D ou en 3D? Si le premier simplement vérifier et voir si la pente est la même pour les deux: si oui, ils sont en parallèle ou la même ligne. Sinon, ils vont se croisent.
- Ce sont les rayons, pas de lignes, alors? Toutes les lignes se coupent en deux dimensions, sauf si elles sont parallèles.
- désolé, plan 2D. Modifié pour refléter cela.
- Norum: Oui, votre droit. Désolé, vous avez raison
- sauf que, depuis qu'ils sont demi-lignes, le point d'intersection n'a pas besoin de s'allonger sur l'un d'eux. Si c'est en 3D, il est préférable de penser plus sérieusement à ce qui "coupe" les moyens.
- Un rayon implique qu'elles proviennent d'une source commune, et, par conséquent, se croisent à la source...?
- Deux rayons? De toute façon ils sont une ligne qui va dans un seul sens. Vers l'extérieur à partir d'un point de départ dans la direction d'un vecteur connu. J'ai deux paires de point de départ/vecteur des combos.
- En fait, avoir un rething, prendre un sens différent à votre question que les autres réponses: vos lignes ont une fin, et l'autre " fin " s'en va à l'infini. Par conséquent, il pourrait être qu'ils ne sont ni parallèles, ni se croisent (si le 'carrefour' point est derrière l'un des connus des fins de ligne). Je n'ai pas posté une réponse que je n'ai pas eu le temps de le résoudre, mais en utilisant les différents gradients de théories ci-dessous ne sont pas suffisantes. Vous avez probablement besoin de résoudre à l'intersection, puis travailler si cette intersection correspond à une quantité positive pour les vecteurs pour les deux lignes.
- Sont-ils vraiment de la moitié des lignes? Ou tout simplement pas comme infini comme de véritables lignes? 🙂
- Oui! C'est ce que je demande. Ils peuvent à la fois être ni parallèle et de ne pas les croiser. Je suis à la recherche d'une façon simple de vérifier si elles se croisent ou pas, mais sans calculer le point d'intersection (a probablement quelque chose à voir avec les vecteurs et les produits croix comme ils font habituellement, moins de avec la logique réelle).
- Il est tentant, au premier coup d'oeil, pour chercher un peu de fantaisie utilisation de produits vectoriels et en comparant les angles, mais réfléchir sur les calculs nécessaires pour obtenir ces produits et de regarder Adam ou de Pierre de la solution. Calculer les déterminants de l'équation jeu est presque le même que le calcul de vecteur de produits
Vous devez vous connecter pour publier un commentaire.
Donné: deux rayons a, b avec des points de départ (origine des vecteurs) as, bs, et la direction des vecteurs ad, bd.
Les deux droites se coupent si il y a un point d'intersection p:
Si ce système d'équation a une solution pour u>=0 et v>=0 (le sens positif est ce qui fait d'eux des rayons, les rayons se croisent.
Pour le x/y les coordonnées des vecteurs 2d, cela signifie:
D'autres mesures:
Résoudre contre v:
De l'insertion et de la résolution contre la grippe:
Calculer u, puis calculer v, si les deux sont positifs, les rayons se croisent, d'autre pas.
as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x)
àu := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)
?Je suis désolé d'être en désaccord avec la réponse de Peter Walser. La résolution des équations donne sur mon bureau:
L'affacturage de la commune de termes, cela revient à:
Cinq soustractions, six multiplications et deux divisions.
Si vous avez seulement besoin de savoir si les rayons se croisent, les signes de u et v sont assez, et ces deux divisons peut être remplacé par num*denom<0 ou (signe(num) != signe(denom)), selon ce qui est le plus efficace sur votre machine cible.
Veuillez noter que les rares cas de det==0 signifie que les rayons ne se croisent pas (une comparaison).
Un rayon peut être représenté par l'ensemble des points
A + Vt
, oùA
est le point de départ,V
est un vecteur indiquant la direction du rayon, ett >= 0
est le paramètre. Ainsi, afin de déterminer si les deux rayons se croisent, ce faire:Lignes sont représentées par un point p et un vecteur v:
Rayons (le positif), la moitié de cette ligne:
Pour déterminer si deux droites se coupent, leur égalité et de résoudre:
Résoudre pour un1 et2 - si ils sont à la fois non-négative, ils se croisent. Si l'un est négatif, ils ne se coupent.
GeomAlgorithms.com a quelques très doux algorithmes traitant avec des lignes en 3D... de façon générale toutefois, la probabilité que deux lignes se croisant dans l'espace 3D est vraiment très faible.
En 2D, vous avez pour vérifier la pente. Si la pente n'est pas égal alors qu'ils se croisent. Si la pente est égale, ils se croisent si un point a la même abscisse ou la même abscisse.
Je veux seulement de vérifier si les deux rayons se croisent. Je vais aller à ce sujet par le calcul de la direction de rotation de deux "triangles" créé à partir de deux rayons. Ils ne sont pas vraiment des triangles, mais à partir d'un point de vue mathématique, si je ne voulais calculer la rotation du triangle, j'ai seulement besoin de deux vecteurs avec un point de départ commun, et le reste n'a pas d'importance.
Le premier triangle sera formé par les deux vecteurs et un point de départ. Le point de départ sera le premier rayon du point de départ. Le premier vecteur sera le premier rayon du vecteur de direction. Le second vecteur sera vecteur forme le premier rayon du point de départ de la deuxième rayon du point de départ. De là, nous prenons le produit vectoriel des deux vecteurs et notez le signe.
Nous le faisons à nouveau pour le deuxième triangle. Encore une fois, le point de départ est le second rayon du point de départ. Le premier vecteur est le second rayon de la direction et le deuxième vecteur est à partir de la deuxième ray de point de départ pour le premier rayon du point de départ. Nous prenons le produit croisé de nouveau des vecteurs et notez le signe.
Maintenant nous suffit de prendre les deux signes et vérifier si elles sont les mêmes. Si elles sont les mêmes, nous n'avons pas d'intersection. Si elles sont différentes, nous avons une intersection. Ça y est!
Voici quelques psudo code:
Qu'il travaille à cinq multiplications, six soustractions, et une comparaison.
Si les lignes sont d'une longueur infinie, alors ils seront toujours se croisent, sauf si elles sont parallèles. Pour vérifier si elles sont parallèles, trouver la pente de chaque ligne et de les comparer. La pente va être juste (y2-y1)/(x2-x1).