Вычислите среднее расстояние от точки до линейного сегмента и линейного сегмента к линейному сегменту
Я ищу алгоритм для вычисления среднего расстояния между точкой и линейным сегментом в 3D. Так, учитывая две точки (x1, y1, z1) и B (x2, y2, z2), которые представляют линейный сегмент AB и третья точка C (x3, y3, z3), каково среднее расстояние между каждой точкой на AB для указания на C?
Я также интересуюсь средним расстоянием между двумя линейными сегментами. Так данный сегмент AB и CD, каково среднее расстояние от каждой точки на AB к самой близкой точке на CD?
У меня не было удачи с веб-поисками, которые я попробовал, таким образом, любые предложения ценились бы.
Спасибо.
3 ответа
Если вы имеете в виду то, что, как я думаю, вы подразумеваете под «средним» (и «расстояние», т. Е. Норму L2, упомянутую древами), то вот процедура что я думаю должен работать для определения среднего расстояния между точкой и отрезком линии. Вам понадобится функция dot (A, B) , которая принимает скалярное произведение двух векторов.
// given vectors (points) A, B, C
K1 = dot(A-C,A-C)
K2 = 2*dot(B-A,A-C)
K3 = dot(B-A,B-A)
L1 = sqrt(K3*(K1+K2+K3))
L2 = sqrt(K3*K1)
N = 4*K3*L1 + 2*K2*(L1-L2) + (K2*K2-4*K1*K3)*log((K2+2*L2)/(2*K3+K2+2*L1))
D = N / (8*K3^1.5)
Если предположить, что я все записал правильно, то D будет средним расстоянием.
По сути, это просто псевдокод для оценки результата интеграла, который я сделал в Mathematica. Для этого может быть какой-нибудь изящный вычислительный ярлык, но если он есть, я этого не знаю. (И если его нет, я бы спросил, сколько вам действительно нужно для этого вычисления)
Если вы хотите найти среднее расстояние от ближайшей точки на линейном сегменте CD до всех точек на AB, в большинстве случаев ближайшая точка будет либо C, либо D, поэтому вы можете просто проверить оба из них, чтобы увидеть, какая из них ближе (возможно, используя некоторый расчет минимального расстояния, как указано в других ответах).Единственное исключение - когда CD и AB параллельны, и вы можете провести перпендикуляр от одного к другому, и в этом случае вам придется более точно определить свои требования.
Если бы вы хотели найти среднее расстояние между всеми точками на CD и всеми точками на AB ... это можно было бы сделать с помощью двойного интеграла, хотя я с содроганием представляю, насколько сложной будет полученная формула.
Во-первых, расстояние между двумя точками - это квадратный корень из суммы квадратов попарных разностей координат. (Например, расстояние от (0,0,0) до (1) , 1,1) равно sqrt (3), но это работает для произвольных точек в любом количестве измерений.) Это расстояние известно как l2-норма (L в нижнем регистре) или Евклидова норма. Запишите норму (A, B) для расстояния между точками A и B.
Переходя к интересной задаче о средних расстояниях ... (Обратите внимание, что нахождение минимальное расстояние от точки до линии или между линейными сегментами является гораздо более распространенной проблемой. Здесь был ответ с хорошими указателями на эту проблему, но, похоже, он был удален за это время.)
Чтобы найти среднее расстояние от точки C до отрезка AB, рассмотрим расстояние до произвольной точки между A и B, а именно (1-k) A + kB, где k изменяется от 0 до 1. Это норма ( C, (1-k) A + kB). Таким образом, среднее расстояние - это интеграл от k = 0 до 1 нормы (C, (1-k) A + kB).
Mathematica может сделать этот интеграл для любых конкретных A, B и C.
Вот реализация Mathematica:
avgd[A_,B_,C_] := Integrate[Sqrt@Dot[(1-k)*A+k*B-C, (1-k)*A+k*B-C], {k, 0, 1}]
Подынтегральное выражение также можно записать Norm [(1-k) * A + k * BC] . В любом случае, Mathematica может сделать это для определенных точек, но не может интегрировать это символически, хотя, очевидно, Дэвид каким-то образом сумел это сделать.
Вот пример Дэвида из комментариев:
> avgd[{0, 0, 0}, {4, 0, 0}, {4, 3, 0}] // N
3.73594
Для проблемы среднего расстояния между двумя отрезками, теоретически я думаю, что это должно сработать:
avgd[A_,B_,C_,D_] := Integrate[Norm[(1-k)A+k*B - (1-j)C - j*D], {k,0,1}, {j,0,1}]
Но Mathematica, кажется, задыхается от этого даже для определенных точек, не говоря уже о символах.
Что ж, если анализ не удастся, возьмите компьютер и проделайте глупые вычисления, пока не почувствуете числа ...
I тоже есть копия Mathematica. Для простоты, поскольку треугольник должен лежать в плоскости, я проработал следующее в 2D-пространстве. Чтобы упростить задачу, я указываю точку в {0,0} и отрезок от {1,0} до {0,1} . Среднее расстояние от точки до линии должно быть, если это имеет смысл, средней длиной всех линий, которые могут быть проведены от {0,0} до любой точки сегмента линии. Конечно, таких строк очень много, поэтому давайте начнем, скажем, с 10. В системе Mathematica это может быть вычислено как
Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 10.0^-1}]]]
, что дает 0,830255 . Следующий шаг очевиден - увеличьте количество измеряемых линий. Фактически, давайте составим таблицу средних значений, когда показатель степени 10,0 станет меньше (они отрицательны!).В Mathematica:
Table[Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1,
10.0^-i}]], {i, 0, 6}]
, что дает:
{1, 0.830255, 0.813494, 0.811801, 0.811631, 0.811615, 0.811613}
Следуя этому подходу, я переработал пример @Dave (забудьте о третьем измерении):
Table[Mean[Table[EuclideanDistance[{0, 0}, {4, 0 + 3 k}], {k, 0, 1,
10.0^-i}]], {i, 0, 6}]
, который дает:
{9/2, 4.36354, 4.34991, 4.34854, 4.34841, 4.34839, 4.34839}
Это не согласуется с тем, что @dreeves говорит об алгоритме @Dave. вычисляет.
РЕДАКТИРОВАТЬ: Хорошо, поэтому я потратил на это еще немного времени. Для простого примера, который я использовал в первую очередь, то есть с точкой в {0,0} и отрезком линии, простирающимся от {0,1} до { 1,0} Я определяю функцию в системе Mathematica (как всегда), например так:
fun2[k_] := EuclideanDistance[{0, 0}, {0 + k, 1 - k}]
Теперь она интегрируема. Mathematica дает:
In[13]:= Integrate[fun2[k], {k, 0, 1}]
Out[13]= 1/4 (2 + Sqrt[2] ArcSinh[1])
Или, если вы предпочитаете числа, это:
In[14]:= NIntegrate[fun2[k], {k, 0, 1}]
Out[14]= 0.811613
, что дает чисто численный подход, который я использовал ранее.
Теперь я собираюсь вернуться к работе и предоставить вам возможность обобщить это на произвольный треугольник, определяемый точкой и конечными точками отрезка линии.