Как узнать пересечение двух копланарных линий в C

У меня есть две 3D-линии, которые лежат в одной плоскости. line1 определяется точкой (x1, y1, z1) и ее вектором направления (a1, b1, c1), а line2 определяется точкой (x2, y2, z2) и ее вектором направления (a2, b2, c2). Тогда параметрические уравнения для обеих линий имеют вид

x = x1 + a1*t;         x = x2 + a2*s;
y = y1 + b1*t;         y = y2 + b2*s;
z = z1 + c1*t;         z = z2 + c2*s;

Если оба вектора направления отличны от нуля, мы можем легко определить местоположение узла пересечения, приравняв правую часть приведенных выше уравнений и решив t и s из любых двух из трех. Однако возможно, что не все a1 b1 c1 a2 b2 c2 отличны от нуля, поэтому я не могу решить эти уравнения одним и тем же способом. Моя текущая мысль состоит в том, чтобы решать эту проблему в каждом конкретном случае, например

case1: a1 = 0, others are nonzero
case2: a2 = 0, others are nonzero
case3: b1 = 0, others are nonzero
...

Однако в целом случаев так много, что реализация станет беспорядочной. Есть ли хорошие способы решить эту проблему? Любая ссылка? Большое спасибо!


c line-intersection
person Jin Yan    schedule 20.03.2014    source источник
comment
почему вы не представляете линии их проекцией на плоскость? В противном случае похоже, что вы пытаетесь решить пересечение линий в трехмерном пространстве. (обратите внимание, что перекрестное произведение между двумя векторами должно дать вам вектор нормали для плоскости, используйте его для проекции)   -  person Steve Cox    schedule 21.03.2014
comment
Похоже дело в матрицах...   -  person EOF    schedule 21.03.2014
comment
Секундочку, какая информация дана для нахождения координат точки пересечения? Я имею в виду, из x1, y1, ..., c2 и так далее   -  person Utkan Gezer    schedule 21.03.2014
comment
@SteveCox Что вы имеете в виду, проецируя линии на самолет? Какой самолет вы имеете в виду? Я знаю нормальный вектор плоскости, на которой находятся две линии.   -  person Jin Yan    schedule 21.03.2014
comment
@ThoAppelsin Это то, что у меня есть только...   -  person Jin Yan    schedule 21.03.2014

Ответы (3)


arrow_upward
2
arrow_downward

Вы можете решить это как линейную систему:

| 1 0 0 -a1   0 | | x |   | x1 |
| 0 1 0 -b1   0 | | y |   | y1 |
| 0 0 1 -c1   0 | | z | = | z1 |
| 1 0 0   0 -a2 | | s |   | x2 |
| 0 1 0   0 -b2 | | t |   | y2 |
| 0 0 1   0 -c2 |         | z2 |

x y z — точка пересечения, а s t — коэффициенты векторов. Это решает то же самое уравнение, которое написал @francis, с тем преимуществом, что оно также получает решение, которое минимизирует ошибку, если ваши данные не идеальны.

Это уравнение обычно записывается как Ax=b, и его можно решить, выполнив x = A^(-1) * b, где A^(-1) — псевдообратное A. Все библиотеки линейной алгебры реализуют некоторые функции для решения подобных систем, так что не беспокойтесь.

person ChronoTrigger    schedule 20.03.2014
comment
Отличный ответ! Очень просто и определенно решило мою проблему. Теперь я уверен, что две линии пересекаются друг с другом, а если они параллельны? Нужно проверить, является ли матрица A здесь дефектной или нет? - person Jin Yan; 21.03.2014
comment
Если прямые параллельны (оба вектора (abc)_1 и (abc)_2 одинаковы в масштабе), матрица A будет неполноценной (она будет иметь ранг 4 вместо 5). Опять же, если ваши данные зашумлены и векторы не совсем совпадают, A будет иметь ранг 5, но ваше решение не будет надежным. Чтобы предотвратить такие случаи, проверьте номер условия A: получите его сингулярные значения и разделите наибольшее на наименьшее. Чем выше, тем хуже. Если линии идеально параллельны, наименьшее сингулярное значение будет равно 0. - person ChronoTrigger; 21.03.2014
comment
Конечно, вы также можете проверить угол между векторами с помощью скалярного произведения, что может быть даже проще. - person ChronoTrigger; 21.03.2014
comment
Понимаю. Точечный продукт кажется проще. Поэтому, прежде чем формировать эту линейную систему, я должен сначала проверить, параллельны ли две линии друг другу, чтобы гарантировать стабильность алгоритма. - person Jin Yan; 21.03.2014

arrow_upward
4
arrow_downward

Гораздо практичнее рассматривать это как векторное уравнение. Точка . — это скалярное произведение, а A,n,B,m — векторы, описывающие линии. Точка A находится на первой линии направления n. Направления нормализованы: n.n=1 и m.m=1. Точка пересечения C такова, что:

 C=A+nt=B+ms

где t и s — вычисляемые скалярные параметры.

Поэтому (.n):

A.n+ t=B.n+m.n s
t= (B-A).n+m.n s

И м):

 A.m+n.m t=B.m+ s
 A.m+n.m (B-A).n+(m.n)^2 s=B.m+ s
 n.m(B-A).n+(A-B).m=(1-(m.n)^2).s

Поскольку n.n=m.m=1, а n и m не выровнены, (m.n)^2‹1 :

 s=[n.m(B-A).n+(A-B).m]/[1-(m.n)^2]
 t= (B-A).n+m.n s
person francis    schedule 20.03.2014

arrow_upward
2
arrow_downward

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

Поэтому давайте решим более общую задачу — найдем значения t и s, при которых расстояние между соответствующими точками в линиях минимально. Очевидно, что это задача для исчисления, и она проста (потому что линейные функции — самые простые в исчислении).

Итак, точки

[xyz1]+[abc1]*t
and
[xyz2]+[abc2]*s

(здесь [xyz1] — 3-вектор [x1, y1, z1] и так далее)

(Квадрат) расстояния между ними:

([abc1]*t - [abc2]*s + [xyz1]-[xyz2])^2

(здесь ^2 — скалярное произведение 3-вектора на самого себя)

Найдем производную от этого по t:

[abc1] * ([abc1]*t - [abc2]*s + [xyz1]-[xyz2])    (multiplied by 2, but this doesn't matter)

(здесь первые * — скалярное произведение, а остальные * — обычные умножения между вектором и числом)

Производная должна быть равна нулю в точке минимума:

[abc1] * ([abc1]*t - [abc2]*s + [xyz1]-[xyz2]) = 0

Давайте также воспользуемся производной по s — мы тоже хотим, чтобы она была равна нулю.

 [abc1]*[abc1]*t - [abc1]*[abc2]*s = -[abc1]*([xyz1]-[xyz2])
-[abc2]*[abc1]*t + [abc2]*[abc2]*s =  [abc2]*([xyz1]-[xyz2])

Отсюда найдем t и s.

Затем найдем две точки, соответствующие этим t и s. Если бы все расчеты были идеальными, эти точки совпадали бы. Однако в этой точке вы практически гарантированно получите небольшие отклонения, поэтому возьмите и эти точки за результат (пересечение двух линий).

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

person anatolyg    schedule 20.03.2014