Эффективный алгоритм для кратчайшего расстояния между двумя отрезками в 1D - PullRequest
Новая
       23

Эффективный алгоритм для кратчайшего расстояния между двумя отрезками в 1D

4 голосов
/ 15 декабря 2010

Я могу найти множество формул для определения расстояния между двумя перекосами.Я хочу вычислить расстояние между двумя отрезками в одном измерении .

Это легко сделать с помощью набора операторов IF.Но мне было интересно, является ли их более эффективная математическая формула.

Например, 1: 

----L1x1-------L2x1-------L1x2------L2x2----------------------------

L1 = линейный сегмент 1, L2 = линейный сегмент 2;расстояние здесь равно 0 из-за пересечения

Например 2: 

----L1x1-------L1x2-------L2x1------L2x2----------------------------

расстояние здесь L2x1 - L1x2

РЕДАКТИРОВАТЬ:

Единственное предположение состоит в том, что сегменты линии упорядочены, то есть x2 всегда> x1.

Сегмент 1 линии может быть слева, справа, равен и т. Д. Сегмента линии 2. Алгоритм имеетрешить для этого.

РЕДАКТИРОВАТЬ 2:

Я должен реализовать это в T-SQL (SQL Server 2008).Мне просто нужна логика ... Я могу написать T-SQL.

РЕДАКТИРОВАТЬ 3:

Если отрезок является отрезком другой линии,расстояние равно 0. 

----L1x1-------L2x1-------L2x2------L1x2----------------------------

Сегмент 2 - это сегмент отрезка 1, составляющий расстояние 0.

Если они пересекаются или касаются, расстояние равно 0.

Ответы [ 5 ]

3 голосов
/ 15 декабря 2010

Этот вопрос аналогичен вопросу "Пересекаются ли два диапазона, и если нет, то какое расстояние между ними?"Ответ немного зависит от того, знаете ли вы, какой диапазон уже наименьший, и правильно ли упорядочены точки в диапазонах (то есть, имеют ли линии одинаковое направление). 

if (a.start < b.start) {
  first = a;
  second = b;
} else {
  first = b;
  second = a;
}

Тогда: 

distance = max(0, second.start - first.end);

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

2 голосов
/ 15 декабря 2010

Это работает во всех случаях: 

d = (s1 max s2 - e1 min e2) max 0

В качестве бонуса удаление max 0 означает, что отрицательный результат точно указывает, сколько из двух сегментов перекрывается.

Доказательство

Обратите внимание, что алгоритм является симметричным, поэтому асимметричные случаи нужно охватить только один раз. Итак, я собираюсь утверждать s2> = s1 w.l.o.g. Также обратите внимание на то, что e1> = s1 и e2> = s2.

Случаи:

  • L2 начинается после окончания L1 (s2> = e1): s1 max s2 = s2, e1 min e2 = e1. Результатом является s2 - e1, который является неотрицательным и ясно, какое значение мы хотим (расстояние).
  • L2 внутри L1 (s2 <= e1, e2 <= e1): s1 max s2 = s2, e1 min e2 = e2. s2 - e2 не является положительным по s2 <= e2, поэтому результат равен 0, как и ожидалось при перекрытии. </li>
  • L2 начинается в пределах L1, но заканчивается после (s2 <= e1, e2> = e1): s1 max s2 = s2, e1 min e2 = e1. s2 - e1 не является положительным по s2 <= e1, поэтому результат равен 0, как и ожидалось при перекрытии. </li>
0 голосов
/ 15 декабря 2010

Эта формула работает во всех случаях, кроме той, в которой одна строка полностью лежит на другой. 

return -min(a2-b1,b2-a1)
0 голосов
/ 15 декабря 2010

Я думаю, так как все линейные сегменты в 1D имеют форму (X, 0) или (0, Y)

, поэтому сохраняйте все эти значения x в массиве и сортируйте массив, и минимальное расстояние будет разницей между 1-м и 2-м элементами массива.

Здесь вы должны быть осторожны при хранении элемента в массиве, чтобы дублирующийся элемент не сохранялся

0 голосов
/ 15 декабря 2010

Я не думаю, что есть способ обойти условия. Но это кратко: 

var diff1 = L2x1 - L1x2;
var diff2 = L2x2 - L1x1;

return diff1 > 0 ? max(0, diff1) : -min(0,diff2);

Это предполагает, что LNx1

...