Пересечение 3D-плоскости

Question

Если задана линия (представленная либо вектором, либо двумя точками на линии), как мне найти точку, в которой линия пересекает плоскость? Я нашел множество ресурсов по этому вопросу, но я не могу понять уравнения там (они не кажутся стандартными алгебраическими). Мне бы хотелось уравнение (независимо от того, как долго), которое можно интерпретировать с помощью стандартного языка программирования (я использую Java).

Answer 1

Вот пример Python, который находит пересечение прямой и плоскости.

Где плоскость может быть либо точкой и нормалью, либо вектором 4d (нормальная форма), в примерах ниже (предоставляется код для обоих) .

Также обратите внимание, что эта функция вычисляет значение, представляющее, где находится точка на линии (называемое fac в приведенном ниже коде).Возможно, вы захотите и это вернуть, потому что значения от 0 до 1 пересекают отрезок линии - что может быть полезно для вызывающего абонента.

Другие детали, отмеченные в комментариях к коду.

---

Примечание. В этом примере используются чистые функции без каких-либо зависимостей - для упрощения перехода на другие языки.С Vector типом данных и перегрузкой оператора, это может быть более кратким (включено в пример ниже).

# 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,
        )

Если плоскость определена как 4-мерный вектор (нормальная форма) , нам нужно найти точку на плоскости, а затем вычислить пересечение, как и раньше (см. 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

Для дальнейшего использования это было взято из Blender и адаптировано для Python.isect_line_plane_v3() in math_geom.c

---

Для ясности, вот версии, использующие mathutils API (который может быть изменен для других математических библиотек)с перегрузкой оператора) .

# 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

Answer 2

Вам нужно будет рассмотреть три случая:

• Плоскость параллельна прямой, а линия не лежит в плоскости (нет пересечений)
• Плоскость не параллельна линии(одна точка пересечения)
• Плоскость содержит линию (линия пересекается в каждой точке на ней)

Вы можете выразить линию в параматизированной форме, как здесь:

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

Первые несколько страниц этой лекции делают то же самое для плоскости:

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

Если нормаль к плоскости перпендикулярна плоскостиНаправление вдоль линии, тогда у вас есть край ребра, и вам нужно увидеть, пересекается ли он вообще или лежит внутри плоскости.

В противном случае у вас есть одна точка пересечения, и вы можете ее решить.

Я знаю, что это не код, но чтобы получить надежное решение, вы, вероятно, захотите поместить это в контекст своего приложения.

РЕДАКТИРОВАТЬ: Вот пример длячто есть ровно одна точка пересечения.Допустим, вы начинаете с параметризованных уравнений в первой ссылке:

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

Параметр t может быть любым.(Бесконечный) набор всех (x, y, z), которые удовлетворяют этим уравнениям, составляют линию.Затем, если у вас есть уравнение для плоскости, скажем:

x + 2y + 2z = 5

(взято из здесь ), вы можете заменить уравнения на x, y и z выше в уравнение для плоскости, которая теперь находится только в параметре t.Решить за t.Это конкретное значение t для той линии, которая лежит на плоскости.Затем вы можете решить для x, y и z, вернувшись к уравнениям линий и подставив t обратно.

Answer 3

Вот метод в Java, который находит пересечение между прямой и плоскостью. Есть векторные методы, которые не включены, но их функции довольно понятны.

/**
 * Determines the point of intersection between a plane defined by a point and a normal vector and a line defined by a point and a direction vector.
 *
 * @param planePoint    A point on the plane.
 * @param planeNormal   The normal vector of the plane.
 * @param linePoint     A point on the line.
 * @param lineDirection The direction vector of the line.
 * @return The point of intersection between the line and the plane, null if the line is parallel to the plane.
 */
public static Vector lineIntersection(Vector planePoint, Vector planeNormal, Vector linePoint, Vector lineDirection) {
    if (planeNormal.dot(lineDirection.normalize()) == 0) {
        return null;
    }

    double t = (planeNormal.dot(planePoint) - planeNormal.dot(linePoint)) / planeNormal.dot(lineDirection.normalize());
    return linePoint.plus(lineDirection.normalize().scale(t));
}

Answer 4

Использование numpy и 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)

Answer 5

Если у вас есть две точки p и q, которые определяют линию, и плоскость в общей декартовой форме ax + by + cz + d = 0, вы можете использовать параметрический метод.

Если вам нужноэто для целей кодирования, вот фрагмент 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)));

Answer 6

На основе этого кода Matlab (минус проверки на пересечение) в 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

Результат

[-3.90909091  1.18181818 -0.27272727]

Я проверил это графически, похоже, работает,

Я считаю, что это более надежная реализация ссылки общего доступа до

Answer 7

Этот вопрос старый, но, поскольку есть гораздо более удобное решение, я подумал, что оно может кому-то помочь.

Пересечения плоскостей и линий довольно элегантны, когда выражаются в однородных координатах, но давайте предположим, что вам просто нужно решение:

Существует вектор 4x1 p, который описывает плоскость так, что p ^ T * x= 0 для любой однородной точки на плоскости.Затем вычислите координаты щипцов для линии L = ab ^ T - ba ^ T, где a = {point_1;1}, b = {point_2; 1}, оба 4x1 в строке

вычисляют: x = L * p = {x0, x1, x2, x3}

x_intersect = ({x0, x1, x2} / x3) где, если x3 равно нулю, пересечения в евклидовом смысле нет.

Answer 8

Просто для того, чтобы расширить ответ Згорлока , я сделал точечное произведение, плюс и множество 3D Векторов. Ссылки для этих расчетов: Точечный продукт , Добавить два трехмерных вектора и Масштабирование . Примечание: Vec3D - это просто пользовательский класс с точками: x, y и z.

/**
 * Determines the point of intersection between a plane defined by a point and a normal vector and a line defined by a point and a direction vector.
 *
 * @param planePoint    A point on the plane.
 * @param planeNormal   The normal vector of the plane.
 * @param linePoint     A point on the line.
 * @param lineDirection The direction vector of the line.
 * @return The point of intersection between the line and the plane, null if the line is parallel to the plane.
 */
public static Vec3D lineIntersection(Vec3D planePoint, Vec3D planeNormal, Vec3D linePoint, Vec3D lineDirection) {
    //ax × bx + ay × by
    int dot = (int) (planeNormal.x * lineDirection.x + planeNormal.y * lineDirection.y);
    if (dot == 0) {
        return null;
    }

    // Ref for dot product calculation: https://www.mathsisfun.com/algebra/vectors-dot-product.html
    int dot2 = (int) (planeNormal.x * planePoint.x + planeNormal.y * planePoint.y);
    int dot3 = (int) (planeNormal.x * linePoint.x + planeNormal.y * linePoint.y);
    int dot4 = (int) (planeNormal.x * lineDirection.x + planeNormal.y * lineDirection.y);

    double t = (dot2 - dot3) / dot4;

    float xs = (float) (lineDirection.x * t);
    float ys = (float) (lineDirection.y * t);
    float zs = (float) (lineDirection.z * t);
    Vec3D lineDirectionScale = new Vec3D( xs, ys, zs);

    float xa = (linePoint.x + lineDirectionScale.x);
    float ya = (linePoint.y + lineDirectionScale.y);
    float za = (linePoint.z + lineDirectionScale.z);

    return new Vec3D(xa, ya, za);
}