L'Algorithme pour Trouver le Point d'Intersection de Deux 3D Segment de Ligne

Trouver le point d'intersection de deux 2D segment de ligne est facile; la formule est simple. Mais trouver le point d'intersection de deux 3D segment n'est pas, j'ai peur.

Qu'est-ce que l'algorithme en C# de préférence qui trouve le point d'intersection de deux 3D segments de ligne?

J'ai trouvé un Implémentation C++ ici. Mais je ne vous fiez pas la solution car il fait de la préférence d'un certain plan ( à la façon de perp est mis en œuvre en vertu de la section mise en œuvre, il suppose une préférence pour z plane. Tout algorithme générique ne doit pas penser que n'importe quel plan de l'orientation ou de préférence).

Est-il une meilleure solution?

Vous trouverez peut-être utile de prendre un coup d'oeil à un article correspondant de Wikipedia - ce n'est pas un code, mais l'algorithme est décrit assez bien, à mon humble avis (mais vous devez savoir de maths de toute façon). en.wikipedia.org/wiki/Bentley%e2%80%93Ottmann_algorithm Update: c'est marrant, c'est que la version russe de la même entrée de Wikipedia contient plus de détails (et de la formule) et une description d'algorithme est de la pseudo-code. Voici un lien pour la traduction de cette entrée à l'anglais (via Google Translate): translate.google.com/...
J'aime les maths dans votre réponse, mais je ne pense pas que votre déclaration à propos d'un algorithme générique est vrai. La projection de l'lignes sur le plan xy permettra de transformer le problème en un problème 2d. Ensuite, trouver l'intersection de la suite de points ou de lignes et de tester sa validité. Le choix de z est juste de la mise en œuvre de commodité. De travail dans une dimension inférieure pourrait réduire le nombre de fonctionnement, trop.
Je ne suis pas sûr de savoir si la projection des lignes sur le plan xy est une bonne idée. Considérez ceci en supposant que les deux x-y les lignes, chacune située sur les différents z avions. Si vous projet pour les plans xy ensuite ils semblent être croisées, même s'ils ne le sont pas.
Bientôt Hui, Oui, c'est correct. Après la détermination de l'intersection dans le plan xy, vous auriez besoin de tester sa validité. C'est juste une question de "brancher les chiffres de". L'avantage est que si les chiffres ne vérifient pas, alors vous pouvez conclure que les lignes ne se croisent pas. Remarque: vous devez gérer un couple de cas particuliers (une ligne est dirigé le long de z-chapeau, des lignes parallèles). Sur une note connexe, la solution que vous avez posté ci-dessous suppose que les lignes sont infinies. Vous aurez besoin de faire un test de validation de cette solution, ainsi.
ma solution serait plus facile et plus propre à mettre en oeuvre car j'ai juste besoin de vérifier pour a et b doit être comprise entre 0 et 1
PAS de. J'ai peur d'avoir tort. La projection dans un plan 2d peut facilement échouer, même si une solution existe. Considérons deux segments de ligne, dont au moins une est parallèle à l'axe z. Maintenant, la projection sera un point.
C'était il y a quelques temps et je crois que j'ai eu tort de parler de l'infini de lignes. D'autres commentaires semblent avoir manqué la partie où j'ai dit à vérifier la projection de l'intersection. Cette procédure échoue pour deux finis segments bout à bout de ce projet pour les points et qui ne se coupent, comme les copeaux de bois, fait allusion à l'. Je m'en excuse. Mais si son infinie lignes, je pense que mon affirmation est correcte. Notez également que mon commentaire n'était pas destiné à être un algorithme efficace, juste un contre-exemple.
Btw, le problème peut être simplifié si la 3ème dimension est supprimé. Dans certains cas, vous pouvez travailler avec les projets de deux lignes 3D sur le même plan, donc de réduire le problème à sa dimensionnelle 2D équivalent.

InformationsquelleAutor Graviton | 2010-02-23

c#math

14

Plus 3D les lignes ne se croisent pas. La méthode la plus fiable est de trouver la ligne la plus courte entre deux lignes 3D. Si la ligne la plus courte a une longueur de zéro (ou quelle que soit la distance moins de tolérance que vous indiquez), alors vous savez que les deux lignes se croisent.

Une méthode pour trouver la ligne la plus courte entre deux lignes 3D, écrit par Paul Bourke est résumé /paraphrasé comme suit:
Dans ce qui suit une ligne est définie par deux points, couché sur elle, un
point à la ligne "a" défini par les points P1 et P2 est une équation
```
Pa = P1 + mua (P2 - P1)
```
de même un point sur une deuxième ligne "b", défini par les points de P4 et P4
sera écrit comme
```
Pb = P3 + mub (P4 - P3)
```
Les valeurs de mua et mub aller de négatif à positif l'infini.
Les segments de ligne entre P1 P2 et P3 P4 ont leur mu
entre 0 et 1.

Il existe deux approches pour trouver le plus court segment de ligne entre
les lignes "a" et "b".
Approche:
La première, c'est d'écrire la longueur de la ligne
segment joignant les deux lignes et ensuite trouver le minimum. Qui est,
minimiser les suivantes
```
|| Pb - Pa ||^2
```
En substituant les équations des lignes donne
```
|| P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ||^2
```
Ci-dessus peut ensuite être élargi à l' (x,y,z) des composants.

Il y a des conditions à respecter, au minimum, les dérivés avec
le respect de mua et mub doit être à zéro. ...la fonction ci-dessus uniquement a
l'un des minima et pas d'autres minima ou maxima. Ces deux équations peuvent ensuite
être résolu pour mua et mub, les réels points d'intersection trouvée par
en substituant les valeurs de mu dans les équations de la ligne.
Approche deux:
Une approche alternative, mais qui donne exactement les mêmes équations est
de réaliser que le plus court segment de ligne entre les deux lignes
être perpendiculaire à deux droites. Cela nous permet d'écrire deux
les équations pour le produit scalaire comme
```
(Pa - Pb) dot (P2 - P1) = 0
(Pa - Pb) dot (P4 - P3) = 0
```
De l'expansion de ces donné l'équation des lignes de
```
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P2 - P1) = 0
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P4 - P3) = 0
```
De l'expansion de ces en termes de coordonnées (x,y,z) ...
le résultat est comme suit
```
d1321 + mua d2121 - mub d4321 = 0
d1343 + mua d4321 - mub d4343 = 0
```
où
```
dmnop = (xm - xn)(xo - xp) + (ym - yn)(yo - yp) + (zm - zn)(zo - zp)
```
Noter que dmnop = dopmn

Enfin, la résolution de mua donne
```
mua = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )
```
et à l'arrière de substitution donne mub
```
mub = ( d1343 + mua d4321 ) / d4343
```
Cette méthode a été trouvé sur Paul Bourke du site web qui est une excellente géométrie de la ressource. Le site a été réorganisé, afin de faire défiler vers le bas pour trouver le sujet.
- +1. La seule réponse à ont clairement reconnu les problèmes.
- C'est vrai que l'on peut vouloir rapprocher de l'intersection dans l'espace 3D. Tout comme la comparaison de deux flotteurs et de dire l'un est égal à l'autre en fonction de certains epsilon facteur qui définit un intervalle de temps (et non pas une seule valeur) de l'égalité. Une autre solution (si possible selon les cas) est de faire un dump de la 3e dimension (réglage à une constante telle que 0) et aller seulement avec les deux coordonnées ainsi, à l'aide de projections et de ne pas les lignes elles-mêmes. Encore +1 pour traiter le problème.
InformationsquelleAutor Doug Ferguson

//This code in C++ works for me in 2d and 3d
//assume Coord has members x(), y() and z() and supports arithmetic operations
//that is Coord u + Coord v = u.x() + v.x(), u.y() + v.y(), u.z() + v.z()
inline Point
dot(const Coord& u, const Coord& v) 
{
return u.x() * v.x() + u.y() * v.y() + u.z() * v.z();   
}
inline Point
norm2( const Coord& v )
{
return v.x() * v.x() + v.y() * v.y() + v.z() * v.z();
}
inline Point
norm( const Coord& v ) 
{
return sqrt(norm2(v));
}
inline
Coord
cross( const Coord& b, const Coord& c) //cross product
{
return Coord(b.y() * c.z() - c.y() * b.z(), b.z() * c.x() - c.z() * b.x(), b.x() *  c.y() - c.x() * b.y());
}
bool 
intersection(const Line& a, const Line& b, Coord& ip)
//http://mathworld.wolfram.com/Line-LineIntersection.html
//in 3d; will also work in 2d if z components are 0
{
Coord da = a.second - a.first; 
Coord db = b.second - b.first;
Coord dc = b.first - a.first;
if (dot(dc, cross(da,db)) != 0.0) //lines are not coplanar
return false;
Point s = dot(cross(dc,db),cross(da,db)) / norm2(cross(da,db));
if (s >= 0.0 && s <= 1.0)
{
ip = a.first + da * Coord(s,s,s);
return true;
}
return false;
}

il y a beaucoup de problèmes avec cette réponse.

InformationsquelleAutor Bill

3

J'ai trouvé une solution: c'est ici.

L'idée est de rendre l'utilisation de vecteur de l'algèbre, de l'utilisation de la dot et cross simplement la question jusqu'à ce stade:
```
a (V1 X V2) = (P2 - P1) X V2
```
et de calculer la a.

Noter que cette mise en œuvre n'a pas besoin d'avoir des plans ou de l'axe de référence.
- Bonjour, j'ai utilisé la solution qui vous est présenté, mais j'ai parfois en miroir des résultats... vous avez eu ce problème aussi?
- Cette solution a fonctionné?
- Je n'aurais pas accepté ma propre réponse à l'encontre de ma propre question si ça ne marchait pas
- Pour quelqu'un d'autre qui trouve cela, vous devez prendre le grandeur de chaque côté. if ( |(V1 X V2)| != 0 ) a = |(P2-P1) X V2| / |V1 X V2| "a" serait votre t valeur.
- Si | V1 X V2 | est égal à zéro, ils ne sont pas coplanaires. Neat.
- Il y a des problèmes avec cette réponse. Cette solution donne de faux positifs
- Il y a des problèmes avec cette réponse. Vous pouvez obtenir miroir résultat. Voici ma correction de la solution, stackoverflow.com/a/56827469/8950836
InformationsquelleAutor Graviton
2

J'ai essayé @Bill répondre et en fait elle ne fonctionne pas à chaque fois, que je ne peux expliquer. Basé sur le lien dans son code.prenons pour exemple ces deux segments de ligne AB et CD.

A=(2,1,5), B=(1,2,5) et C=(2,1,3) et D=(2,1,2)

lorsque vous essayez d'obtenir de l'intersection, il pourrait vous dire que C'est le point A (incorrect) ou il n'y a pas d'intersection (correct). Selon l'ordre que vous mettez ces secteurs.

x = A+(B-A)s

x = C+(D-C)t

Projet de loi résolu pour s mais jamais résolu t. Et puisque vous voulez que le point d'intersection d'être sur les deux segments de ligne à la fois s et t être d'intervalle <0,1>. Ce qui se passe réellement dans mon exemple, c'est que seulement s si à partir de cet intervalle et t est de -2. Un se trouve sur la ligne définie par C et D, mais pas sur le segment de ligne CD.
```
var s = Vector3.Dot(Vector3.Cross(dc, db), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));
var t = Vector3.Dot(Vector3.Cross(dc, da), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));
```
où da est le B-A, db est D-C et dc est ca, j'ai juste conservé les noms fournis par le projet de Loi.

Puis comme je l'ai dit, vous devez vérifier si les deux s et t sont de <0,1> et vous pouvez calculer le résultat. Basé sur la formule ci-dessus.
```
if ((s >= 0 && s <= 1) && (k >= 0 && k <= 1))
{
Vector3 res = new Vector3(this.A.x + da.x * s, this.A.y + da.y * s, this.A.z + da.z * s);
}
```
Aussi un autre problème avec les Factures réponse est lorsque deux lignes sont colinéaires et il n'y a plus qu'un point d'intersection. Il y aurait une division par zéro. Vous voulez éviter que les.

InformationsquelleAutor Kapitán Mlíko
1

Mais de trouver le point d'intersection de deux 3D segment n'est pas, j'ai peur.

Je pense qu'il est. Vous pouvez trouver le point d'intersection exactement de la même manière qu'en 2d (ou tout autre dimension). La seule différence est que le système d'équations linéaires est plus susceptible de n'avoir aucune solution (ce qui signifie que les lignes ne se croisent pas).

Vous pouvez résoudre les équations générales à la main et il suffit d'utiliser votre solution, ou de le résoudre par programmation, en utilisant par exemple Gaussien elemination.
- Si nous prolongeons la 2D façon de faire les choses, vous aurez trois équations (x,y et z) pour deux inconnues (u,v). Il est certainement non négligeable pour le résoudre.
- Eh bien... aussi trivial que la 2d cas. Vous pouvez simplement utiliser les deux premières équations pour déterminer u et v, et de vérifier ensuite si la dernière équation tient avec ces valeurs de u et de v. Si c'est le cas, vous avez trouvé votre intersection. Si elle ne le fait pas, les lignes ne se croisent pas. Je ne vois pas de difficulté ici.
- En Algèbre Linéaire, cela est considéré comme négligeable. Pour un algorithme de certains soins doivent être prises, si. Par exemple, si les deux lignes à la fois vécu en x=0, y=0 ou z=0 plan, l'un de ces trois équations ne vous donnera pas toutes les informations. (En supposant que les équations sont some_point_on_line_1 = some_point_on_line_2)
- c'est quelque chose que je m'efforce de les éviter en ayant une solution générique; je ne veux pas de vérifier les cas de bord sur mon code.
- Également regarder dehors pour cela lors de l'optimisation de votre code, une bibliothèque, j'ai utilisé avait ce problème, car il a été optimisé de manière trop agressive.
InformationsquelleAutor Jens
1

La source d'origine que vous mentionnez est seulement pour le cas 2d. La mise en œuvre pour le perp est très bien. L'utilisation de x et y sont simplement des variables indique pas de préférence pour un plan spécifique.

Le même site a ce pour la 3d cas:
"http://geomalgorithms.com/a07-_distance.html"

Ressemble Eberly est l'auteur d'une réponse:
"https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf"

De mettre ce genre de choses ici parce que google les points de geomalgorithms et à ce poste.

InformationsquelleAutor user1633759

Vous devez vous connecter pour publier un commentaire.