El algoritmo para encontrar el punto de intersección de dos segmentos de línea 3D

Question

Encontrar el punto de intersección para dos segmentos de línea 2D es fácil; the formula is straight forward. Pero me da miedo encontrar el punto de intersección para dos segmentos de línea 3D.

¿Cuál es el algoritmo, en C# preferiblemente que encuentra el punto de intersección de dos segmentos de línea 3D?

Encontré un C++ implementation here. Pero no confío en la solución porque hace la preferencia de un cierto plano (mire la forma en que se implementa perp en la sección de implementación, supone una preferencia por z plane. Cualquier algoritmo genérico no debe asumir ninguna orientación o preferencia de plano).

¿Existe una solución mejor?

Answer 1

Encontré una solución: it's here.

La idea es hacer uso del álgebra vectorial, para utilizar el dot y cross simplemente la pregunta hasta esta etapa:

a (V1 X V2) = (P2 - P1) X V2 

y calcular la a.

Tenga en cuenta que esta implementación no necesita tener ningún plano o eje como referencia.

Answer 2

Puede que le resulte útil echarle un vistazo al artículo correspondiente en Wikipedia; no tiene un código, pero el algoritmo se describe bastante bien, en mi humilde opinión (pero debe saber algunas matemáticas de todos modos).

http://en.wikipedia.org/wiki/Bentley%e2%80%93Ottmann_algorithm

Actualización: lo suficientemente curioso es que la versión rusa de la misma entrada de la Wikipedia contiene más detalles (y) y formular una descripción del algoritmo es pseudo-código. Aquí hay un enlace a la traducción de esta entrada a Inglés (a través de Google Translate):

http://translate.google.com/translate?hl=en&sl=ru&tl=en&u=http%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%259F%25D0%25B5%25D1%2580%25D0%25B5%25D1%2581%25D0%25B5%25D1%2587%25D0%25B5%25D0%25BD%25D0%25B8%25D0%25B5_%25D0%25BE%25D1%2582%25D1%2580%25D0%25B5%25D0%25B7%25D0%25BA%25D0%25BE%25D0%25B2

Answer 3

Pero encontrar el punto de intersección de dos segmentos de línea 3D no es, me temo.

Creo que es. Puede encontrar el punto de intersección exactamente de la misma manera que en 2d (o cualquier otra dimensión). La única diferencia es que el sistema resultante de ecuaciones lineales tiene más posibilidades de no tener solución (es decir, las líneas no se cruzan).

Puede resolver las ecuaciones generales a mano y solo usar su solución, o resolverla mediante programación, usando p. Ej. Gaussian elemination.

Answer 4

La mayoría de las líneas 3D no se cruzan. Un método confiable es encontrar la línea más corta entre dos líneas 3D. Si la línea más corta tiene una longitud de cero, entonces usted sabe que las dos líneas originales se cruzan.

Puede encontrar un método para encontrar the shortest line between two 3D lines en el sitio web de Paul Bourke, que es un excelente recurso de geometría. El sitio ha sido reorganizado, así que desplácese hacia abajo para encontrar el tema.

http://paulbourke.net/geometry/pointlineplane/

Answer 5

// 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; 
} 

Answer 6

me trataron @ Bill responder y que en realidad no funciona cada vez y que tiene sentido. Basado en el link in his code. Tengamos por ejemplo estos dos segmentos de línea AB y CD.

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

cuando intenta obtener la intersección que podría decirle Es el punto A (incorrecto) o no hay intersección (correcto). Dependiendo del orden ponemos aquellos segmentos en.

x = A + (B-A) s
x = C + (D-C) t

Bill resuelve para s pero nunca resuelto t. Y dado que desea que ese punto de intersección esté en ambos segmentos de línea, ambos s y t deben ser del intervalo < 0,1>. Lo que realmente ocurre en mi ejemplo es que solo s si de ese intervalo y t es -2. A se encuentra en línea definida por C y D, pero no en segmento de línea 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)); 

donde da es B-A, db es D-C y DC es nombres C-A, sólo preservadas proporcionadas por Bill.

Entonces como dije usted tiene que comprobar si ambos s y t son de < 0,1> y se puede calcular el resultado. Basado en la fórmula anterior.

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); 
} 

Otro problema con las cuentas es cuando dos líneas son colineales y hay más de un punto de intersección. Habría división por cero. Quieres evitar eso.