c# - segmentos - la interseccion de dos planos puede ser un segmento

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; La fórmula es sencilla . Pero me temo que encontrar el punto de intersección para dos segmentos de línea 3D no lo es.

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

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

¿Hay una solución mejor?

Answer 1

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

Creo que es. Puede encontrar el punto de intersección exactamente de la misma manera que en 2d (o en cualquier otra dimensión). La única diferencia es que es más probable que el sistema resultante de ecuaciones lineales no tenga solución (lo que significa que las líneas no se intersecan).

Puede resolver las ecuaciones generales a mano y simplemente usar su solución, o resolverla de manera programática, por ejemplo, mediante la eleminación de Gauss .

Answer 2

Encontré una solución: está aquí .

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

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

y calcular el a .

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

Answer 3

Intenté la respuesta de @Bill y en realidad no funciona cada vez, lo que puedo explicar. Basado en el enlace en su código. 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, podría indicarle que es el punto A (incorrecto) o que no hay una intersección (correcto). Dependiendo del orden en que pongas esos segmentos.

x = A + (BA) s
x = C + (DC) t

Bill resolvió por s pero nunca resolvió t . Y dado que desea que el punto de intersección esté en ambos segmentos de línea, tanto s como t deben ser del intervalo <0,1> . Lo que realmente sucede en mi ejemplo es que solo s si de ese intervalo y t es -2. A se encuentra en la línea definida por C y D , pero no en el CD del segmento de línea.

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 BA, db es DC y dc es CA, simplemente conservé los nombres proporcionados por Bill.

Luego, como dije, debes comprobar si tanto s como t son de <0,1> y puedes calcular el resultado. Basado en la fórmula de arriba.

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 la respuesta de Bills 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.

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 (o una distancia menor que la tolerancia que especifique), entonces sabe que las dos líneas originales se intersecan.

Un método para encontrar la línea más corta entre dos líneas 3D, escrito por Paul Bourke se resume / parafrasea de la siguiente manera:

En lo que sigue una línea se definirá por dos puntos que se encuentran en ella, un punto en la línea "a" definido por los puntos P1 y P2 tiene una ecuación

Pa = P1 + mua (P2 - P1)

de manera similar, un punto en una segunda línea "b" definida por los puntos P4 y P4 se escribirá como

Pb = P3 + mub (P4 - P3)

Los valores de mua y mub varían de negativo a positivo infinito. Los segmentos de línea entre P1 P2 y P3 P4 tienen su mu correspondiente entre 0 y 1.

Hay dos enfoques para encontrar el segmento de línea más corto entre las líneas "a" y "b".

Enfoque uno:

Lo primero es anotar la longitud del segmento de línea que une las dos líneas y luego encontrar el mínimo. Es decir, minimizar lo siguiente.

|| Pb - Pa ||^2

Sustituyendo las ecuaciones de las líneas da.

|| P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ||^2

Lo anterior se puede expandir en los componentes (x, y, z).

Hay condiciones que deben cumplirse como mínimo, la derivada con respecto a mua y mub debe ser cero. ... la función anterior solo tiene un mínimo y ningún otro mínimo o máximo. Estas dos ecuaciones se pueden resolver para mua y mub, los puntos de intersección reales encontrados sustituyendo los valores de mu en las ecuaciones originales de la línea.

Enfoque dos:

Un enfoque alternativo pero que proporciona las mismas ecuaciones es darse cuenta de que el segmento de línea más corto entre las dos líneas será perpendicular a las dos líneas. Esto nos permite escribir dos ecuaciones para el producto punto como

(Pa - Pb) dot (P2 - P1) = 0
(Pa - Pb) dot (P4 - P3) = 0

Expandiendo éstos dada la ecuación de las líneas.

( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P2 - P1) = 0
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P4 - P3) = 0

Expandiendo estos en términos de las coordenadas (x, y, z) ... el resultado es el siguiente

d1321 + mua d2121 - mub d4321 = 0
d1343 + mua d4321 - mub d4343 = 0

dónde

dmnop = (xm - xn)(xo - xp) + (ym - yn)(yo - yp) + (zm - zn)(zo - zp)

Tenga en cuenta que dmnop = dopmn

Finalmente, resolviendo para mua da.

mua = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )

y la sustitución hacia atrás da mub

mub = ( d1343 + mua d4321 ) / d4343

Este método se encontró 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.

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