Вычислить среднее расстояние от точки до отрезка и отрезка до отрезка

Question

Я ищу алгоритм для расчета среднего расстояния между точкой и отрезком в 3D.Итак, учитывая две точки A (x1, y1, z1) и B (x2, y2, z2), которые представляют отрезок AB, и третью точку C (x3, y3, z3), каково среднее расстояние между каждой точкой на ABв точку C?

Меня также интересует среднее расстояние между двумя отрезками.Итак, учитывая отрезки AB и CD, каково среднее расстояние от каждой точки на AB до ближайшей точки на CD?

Мне не повезло с поиском в Интернете, который я пробовал, поэтому любые предложения будутбыть оцененным.

Спасибо.

Answer 1

Во-первых, расстояние между двумя точками - это квадратный корень из суммы квадратов парных разностей координат. (Например, расстояние от (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*B-C]. В любом случае, 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 задыхается от этого даже в определенных точках, не говоря уже о символическом значении.

Answer 2

Что ж, если анализ не удался, дотянись до компьютера и сделай глупые подсчеты, пока не почувствуешь цифры ...

У меня тоже есть копия 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}

Следуя этому подходу, я переделал пример @ Дейва (забудьте третье измерение):

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, алгоритм @ Дейва вычисляет.

РЕДАКТИРОВАТЬ: ОК, так что я потратил немного больше времени на это.Для простого примера, который я использовал в первую очередь, то есть с точкой на {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

, что дает чисто числовой подход, который я использовал ранее.

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

Answer 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 ... это можно сделать с помощью двойного интеграла, хотя мне страшно подумать, насколько сложной будет полученная формула.