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

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

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

E.g. 1:

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

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

E.g. 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.


sql-server distance algorithm geometry intersection
person IamIC    schedule 15.12.2010    source источник
comment
Чтобы прояснить вопрос, я предлагаю вам использовать строку - сегмент. Все линии в одном измерении одинаковы. Не могли бы вы также прояснить предположения, например для каждого сегмента x2 >= x1 (не уверен, так ли это)?   -  person Ani    schedule 15.12.2010

Ответы (5)


arrow_upward
3
arrow_downward

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

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

Потом:

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

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

person Andrew Aylett    schedule 15.12.2010
comment
Блестяще! Потребовалось ‹1 мин, чтобы доказать, что это работает в Excel. Спасибо! - person IamIC; 15.12.2010

arrow_upward
2
arrow_downward

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

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, как и ожидалось во время перекрытия.
  • L2 начинается в L1, но заканчивается после (s2 ‹= e1, e2> = e1): s1 max s2 = s2, e1 min e2 = e1. s2 - e1 неположительно на s2 ‹= e1, поэтому результат равен 0, как и ожидалось во время перекрытия.
person Craig Gidney    schedule 15.12.2010
comment
+1. Или больше в синтаксисе плакатов d = max (0, max (L1x1, L2x1) -min (L1x2, L2x2)) - person phkahler; 15.12.2010
comment
Вот что я написал: MAX (0, IF (L1x1 ‹L2x1, L2x1-L1x2, L1x1-l2x2)) - person IamIC; 15.12.2010
comment
@IanC Это тоже будет работать нормально, хотя я считаю его более сложным и теряет красивое свойство без-max-0. - person Craig Gidney; 15.12.2010
comment
в конечном итоге я пишу это на T-SQL. Там совсем не красиво :) - person IamIC; 15.12.2010

arrow_upward
0
arrow_downward

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

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

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

Предполагается, что LNx1 ‹LNx2.

person Aliostad    schedule 15.12.2010
comment
Линии могут перекрываться и могут находиться в любом соотношении друг к другу (слева, справа, внутрь, пересекаются и т. Д.). - person IamIC; 15.12.2010

arrow_upward
0
arrow_downward

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

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

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

person TalentTuner    schedule 15.12.2010
comment
Это не вернет 0, если строка 1 является сегментом строки 2. - person IamIC; 15.12.2010

arrow_upward
0
arrow_downward

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

return -min(a2-b1,b2-a1)
person bezmax    schedule 15.12.2010
comment
Я пробовал это. Если строка 1 является сегментом строки 2, результат должен быть 0. - person IamIC; 15.12.2010