Comment calculez-vous si 2 lignes sont tournées vers ou loin?

10

Étant donné les 4 points décrivant 2 segments de ligne, comment calculer si la ligne A est vers ou loin de la ligne B?

Les 2 lignes ont une longueur fixe et peuvent être mesurées comme la distance de x1 / y1 à x2 / y2.

entrez la description de l'image ici

mathematics geometry lines beziers curves Robinicks
la source
En quoi le cas avec la courbe de Bézier est-il différent du cas avec les lignes droites? Avez-vous une courbe qui pourrait entourer complètement l'autre ligne (de sorte que chaque direction pointe vers "vers")?
bummzack
1
Vous devez probablement clarifier vos termes. En géométrie, une "ligne" s'étend à l'infini dans les deux sens, par opposition à une demi-ligne ou un segment, donc 2 lignes se croisent toujours à moins qu'elles ne soient parallèles. Laquelle demandez-vous? Vous avez tracé une flèche, ce qui implique une direction, ce qui pour moi implique un segment ou tout au plus une demi-ligne. Et quelle est votre définition de "vers" et "loin"?
Hackworth
La courbe de Bézier peut être plus difficile à représenter dans l'égalité requise pour résoudre un test d'intersection de rayons. Soit dit en passant, je changerais le mot qui représente votre flèche en "rayon". Vous pourriez obtenir une réponse plus rapide. Je répondrai à cela si j'ai le temps pendant le déjeuner si personne d'autre ne le fait. Sinon, c'est une tâche extrêmement courante dans les jeux. Google "Test d'intersection de segments de ligne Ray". Je soupçonne que le test de la courbe de Bézier est similaire, mais je ne l'ai jamais essayé.
brandon
3
Vous devriez diviser votre question en deux. La partie avec des segments de ligne est très facile. La pièce aux courbes de Bézier est extrêmement complexe et n'a qu'une solution numérique approximative.
sam hocevar
J'ai divisé ma question en 2, comme demandé. La 2ème partie est ici: gamedev.stackexchange.com/questions/21463/…
Robinicks

Réponses:

11

Soit Aet Bsoit deux points sur la ligne noire. Laissez Cet Dsoyez votre segment bleu. Le signe de la zcoordonnée du produit croisé AB^ACvous indique si Cest "gauche" ou "droite" de la ligne noire. De même, le produit croisé AB^CDvous indique si vous CDorientez "à gauche" ou "à droite" de la ligne noire.

Nous ne voulons pas vraiment savoir si c'est à gauche ou à droite; tout ce que nous voulons, c'est nous assurer qu'ils sont dans la même direction ou dans la direction opposée, c'est pourquoi nous multiplions les deux valeurs.

Le pseudocode suivant devrait donc fonctionner:

z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

J'ai peur d'avoir besoin de temps pour écrire une solution appropriée pour la courbe de Bézier. La situation suivante est-elle proche ou éloignée?

Problème?

sam hocevar
la source
Pour la courbe, je pense que vous pourriez trouver la tangente de la courbe au point le plus proche de votre segment de ligne et l'utiliser de la même manière que vous testez vos autres segments de ligne. Probablement un peu plus difficile qu'il n'y paraît :)
Notlesh
@stephelton: Regardez à nouveau la deuxième image pour les courbes de Bézier, pointant vers une courbe qui s'éloigne. Ou considérez une courbe avec une tangente parallèle au segment qui peut se croiser, mais qui se courbe vers le segment et se croise.
Cascabel
+1 pour le trollface, et bon calcul :). Cependant, votre diagramme «vers» a toujours un «loin» - déplacez simplement le point de départ au-dessus de la ligne.
Jonathan Dickinson
@JonathanDickinson merci, j'ai mis à jour l'image pour que ce soit un peu plus clair mon interrogation!
sam hocevar
2

En supposant que le point de départ est le cercle vert et le point final est la flèche rouge

Calculez la distance entre le point de départ comme DS et le segment noir, et faites de même pour le point d'arrivée (flèche rouge) comme DE. Si DS> DE, alors le segment pointe vers. si DE> DS, il pointe loin. Si les deux sont égaux, les deux sont parallèles.

Vous pouvez trouver comment calculer la distance d'un point à un segment ici , et à une courbe de Bézier ici . Cependant, selon la forme de la courbe de Bézier, cela pourrait retourner des résultats étranges (la courbe peut se croiser)

Ravachol
la source
DS> DE ne fonctionne que pour les lignes droites. Cela peut échouer pour Béziers. De plus, vous ne connaissez pas sa définition de "vers". Si l'extension de la flèche traverserait une ligne définie par 2 points, mais pas le segment défini par les mêmes points, est-ce toujours "vers"?
Hackworth
Je parle de deux segments, pas de lignes, donc il n'y a pas "d'extension de la flèche". En outre, peu importe où pointe la flèche, car nous parlons ici des distances. Le point le plus proche sur la ligne noire pourrait être un point de début / fin de la ligne noire, cela n'a pas d'importance. Les deux segments pourraient être colinéaires, cette méthode fonctionnerait toujours comme prévu. Pour les courbes plus douces, j'ai mentionné que cela donnerait des résultats étranges selon la forme de la courbe.
Ravachol