Interseção de linha de avião 3D

Se for dada uma linha (representada por um vetor ou dois pontos na linha), como faço para encontrar o ponto em que a linha intercepta um plano? Eu encontrei muitos resources sobre isso, mas não consigo entender as equações (eles não parecem ser padrão algébrico). Eu gostaria de uma equação (não importa quanto tempo) que possa ser interpretada por uma linguagem de programação padrão (estou usando Java).

Você precisará considerar três casos:

  • O plano é paralelo à linha e a linha não está no plano (sem interseção)
  • O plano não é paralelo à linha (um ponto de intersecção)
  • Plano contém a linha (a linha cruza em cada ponto)

Você pode expressar a linha em forma de parágrafo, como aqui:

http://answers.yahoo.com/question/index?qid=20080830195656AA3aEBr

As primeiras páginas desta palestra fazem o mesmo para o avião:

http://math.mit.edu/classs/18.02/notes/lecture5compl-09.pdf

Se a normal para o plano é perpendicular à direção ao longo da linha, então você tem um caso de borda e precisa ver se ele se cruza ou se está dentro do plano.

Caso contrário, você tem um ponto de intersecção e pode resolvê-lo.

Eu sei que isso não é código, mas para obter uma solução robusta, você provavelmente vai querer colocar isso no contexto do seu aplicativo.

EDIT: Aqui está um exemplo para o qual há exatamente um ponto de interseção. Digamos que você comece com as equações parametrizadas no primeiro link:

x = 5 - 13t y = 5 - 11t z = 5 - 8t 

O parâmetro t pode ser qualquer coisa. O conjunto (infinito) de todos (x, y, z) que satisfazem essas equações compõe a linha. Então, se você tiver a equação de um avião, diga:

 x + 2y + 2z = 5 

(tirado daqui ) você pode replace as equações de x , y acima na equação do plano, que agora está apenas no parâmetro t . Resolva por t . Este é o valor particular de t para aquela linha que se encontra no plano. Então você pode resolver para x , y voltando para as equações de linha e substituindo t novamente.

Aqui está um exemplo do Python que encontra a interseção de uma linha e um plano.

Onde o plano pode ser um ponto e um normal, ou um vetor 4d (forma normal), Nos exemplos abaixo (código para ambos é fornecido) .

Observe também que esta function calcula um valor que representa onde o ponto está na linha (chamado fac no código abaixo). Você pode querer retornar isso também, porque os valores de 0 a 1 cruzam o segmento de linha – o que pode ser útil para o chamador.

Outros detalhes observados nos comentários de código.


Nota: Este exemplo usa funções puras, sem nenhuma dependência – para facilitar a migration para outros idiomas. Com um tipo de dados Vector e sobrecarga de operadores, ele pode ser mais conciso (incluído no exemplo abaixo).

 # intersection function def isect_line_plane_v3(p0, p1, p_co, p_no, epsilon=1e-6): """ p0, p1: define the line p_co, p_no: define the plane: p_co is a point on the plane (plane coordinate). p_no is a normal vector defining the plane direction; (does not need to be normalized). return a Vector or None (when the intersection can't be found). """ u = sub_v3v3(p1, p0) dot = dot_v3v3(p_no, u) if abs(dot) > epsilon: # the factor of the point between p0 -> p1 (0 - 1) # if 'fac' is between (0 - 1) the point intersects with the segment. # otherwise: # < 0.0: behind p0. # > 1.0: infront of p1. w = sub_v3v3(p0, p_co) fac = -dot_v3v3(p_no, w) / dot u = mul_v3_fl(u, fac) return add_v3v3(p0, u) else: # The segment is parallel to plane return None # ---------------------- # generic math functions def add_v3v3(v0, v1): return ( v0[0] + v1[0], v0[1] + v1[1], v0[2] + v1[2], ) def sub_v3v3(v0, v1): return ( v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2], ) def dot_v3v3(v0, v1): return ( (v0[0] * v1[0]) + (v0[1] * v1[1]) + (v0[2] * v1[2]) ) def len_squared_v3(v0): return dot_v3v3(v0, v0) def mul_v3_fl(v0, f): return ( v0[0] * f, v0[1] * f, v0[2] * f, ) 

Se o plano é definido como um vetor 4d (forma normal) , precisamos encontrar um ponto no plano e calcular a interseção como antes (consulte a atribuição p_co ).

 def isect_line_plane_v3_4d(p0, p1, plane, epsilon=1e-6): u = sub_v3v3(p1, p0) dot = dot_v3v3(plane, u) if abs(dot) > epsilon: # calculate a point on the plane # (divide can be omitted for unit hessian-normal form). p_co = mul_v3_fl(plane, -plane[3] / len_squared_v3(plane)) w = sub_v3v3(p0, p_co) fac = -dot_v3v3(plane, w) / dot u = mul_v3_fl(u, fac) return add_v3v3(p0, u) else: return None 

Para referência adicional, isso foi retirado do Blender e adaptado para Python. isect_line_plane_v3() em math_geom.c


Para maior clareza, aqui estão as versões usando a API mathutils (que pode ser modificada para outras bibliotecas matemáticas com sobrecarga de operadores) .

 # point-normal plane def isect_line_plane_v3(p0, p1, p_co, p_no, epsilon=1e-6): u = p1 - p0 dot = p_no * u if abs(dot) > epsilon: w = p0 - p_co fac = -(plane * w) / dot return p0 + (u * fac) else: return None # normal-form plane def isect_line_plane_v3_4d(p0, p1, plane, epsilon=1e-6): u = p1 - p0 dot = plane.xyz * u if abs(dot) > epsilon: p_co = plane.xyz * (-plane[3] / plane.xyz.length_squared) w = p0 - p_co fac = -(plane * w) / dot return p0 + (u * fac) else: return None 

Usando numpy e python:

 #Based on http://geomalgorithms.com/a05-_intersect-1.html from __future__ import print_function import numpy as np epsilon=1e-6 #Define plane planeNormal = np.array([0, 0, 1]) planePoint = np.array([0, 0, 5]) #Any point on the plane #Define ray rayDirection = np.array([0, -1, -1]) rayPoint = np.array([0, 0, 10]) #Any point along the ray ndotu = planeNormal.dot(rayDirection) if abs(ndotu) < epsilon: print ("no intersection or line is within plane") w = rayPoint - planePoint si = -planeNormal.dot(w) / ndotu Psi = w + si * rayDirection + planePoint print ("intersection at", Psi) 

Com base nesse código do Matlab (menos as verificações de interseção), em Python

 # n: normal vector of the Plane # V0: any point that belongs to the Plane # P0: end point 1 of the segment P0P1 # P1: end point 2 of the segment P0P1 n = np.array([1., 1., 1.]) V0 = np.array([1., 1., -5.]) P0 = np.array([-5., 1., -1.]) P1 = np.array([1., 2., 3.]) w = P0 - V0; u = P1-P0; N = -np.dot(n,w); D = np.dot(n,u) sI = N / D I = P0+ sI*u print I 

Resultado

 [-3.90909091 1.18181818 -0.27272727] 

Eu verifiquei graficamente que parece funcionar,

insira a descrição da imagem aqui

Isso eu acredito é uma implementação mais robusta do link compartilhado antes

Essa pergunta é antiga, mas como existe uma solução muito mais conveniente, achei que poderia ajudar alguém.

As interseções de plano e linha são bastante elegantes quando expressas em coordenadas homogêneas, mas vamos supor que você só quer a solução:

Existe um vetor 4×1 p que descreve o plano tal que p ^ T * x = 0 para qualquer ponto homogêneo no plano. Em seguida calcule as coordenadas do depurador para a linha L = ab ^ T – ba ^ T onde a = {point_1; 1}, b = {point_2; 1}, ambos 4×1 na linha

compute: x = L * p = {x0, x1, x2, x3}

x_intersect = ({x0, x1, x2} / x3) onde, se x3 é zero, não há interseção no sentido euclideano.

Se você tem dois pontos p e q que definem uma linha e um plano na forma cartesiana geral ax + by + cz + d = 0, você pode usar o método paramétrico.

Se você precisasse disso para fins de codificação, aqui está um snippet de javascript:

 /** * findLinePlaneIntersectionCoords (to avoid requiring unnecessary instantiation) * Given points p with px py pz and q that define a line, and the plane * of formula ax+by+cz+d = 0, returns the intersection point or null if none. */ function findLinePlaneIntersectionCoords(px, py, pz, qx, qy, qz, a, b, c, d) { var tDenom = a*(qx-px) + b*(qy-py) + c*(qz-pz); if (tDenom == 0) return null; var t = - ( a*px + b*py + c*pz + d ) / tDenom; return { x: (px+t*(qx-px)), y: (py+t*(qy-py)), z: (pz+t*(qz-pz)) }; } // Example (plane at y = 10 and perpendicular line from the origin) console.log(JSON.stringify(findLinePlaneIntersectionCoords(0,0,0,0,1,0,0,1,0,-10))); // Example (no intersection, plane and line are parallel) console.log(JSON.stringify(findLinePlaneIntersectionCoords(0,0,0,0,0,1,0,1,0,-10)));