Алгоритм вычисления среднего направления неориентированных сегментов

Question

У меня есть набор 2D неориентированных сегментов, состоящий из двух конечных точек. Статистически большинство из них лежат в более или менее одинаковом направлении.

То, что я хотел бы вычислить, - это среднее значение направления набора сегментов (например, если множество глобально N/S, оно вернет что-то ~ 0 ° и т. Д.). Обратите внимание, что мне все равно, какое фактическое направление возвращается (0 ° или 180 ° в равной степени).

Зажимное направление каждого сегмента в диапазоне [0..180 ° [и усреднение не работает (например, два сегмента, один 1 ° и другой -1 °: второй будет зажиматься до 179 ° и среднее значение неверно, здесь 90 °, должно быть 0 °).

Я также думал о кластеризации «нормализованных сегментов» конечных точек в двух группах и вычислении направления сегмента, состоящего из двух кластеров средних точек, но это кажется немного сложным для задачи. Под «нормализованным сегментом» я подразумеваю, что сегмент имеет как конечные точки на единичном круге, так и среднюю точку в начале координат.

Есть ли известный алгоритм/формула для этого?

Answer 1

Как я понимаю, расположение сегментов не имеет значения, только их направление.

Таким образом, мы можем изменить неполадку немного: у нас есть множество векторов, и мы хотим, чтобы соответствовать линии на них.

Для этого мы можем принять различные критерии. Обычно используемым является наименьший квадрат.

Для этого критерия решение:

double dvx=0,dvy=0; 
for(const auto &direction:directions) 
{ 
    dvx+=2*direction.dx*direction.dy; 
    dvy+=squared(directions.dx)-squared(directions.dy); 
} 
return std::atan2(dvx,dvy)/2;//or may be +pi/2 

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

Этот метод иногда используется для определения направления линий распознавания отпечатков пальцев: http://jmit.us.edu.pl/cms/jmitjrn/22/28_Wieclaw_4.pdf

Есть несколько способов, чтобы понять этот метод. Одним из них является геометрическим:

У нас есть множество векторов с углом alpha[i] от оси X. Мы не усредняем эти векторы. Вместо этого мы строим векторы с углом 2*alpha[i], усредняем их и берем половину результирующего угла.Фокус в том, что если противоположные направления отличаются на pi, и после удвоения они будут отличаться на 2*pi, что не имеет никакого значения.

Answer 2

Там is method найти среднее из углов (в полном круговом диапазоне)

MeanAngle = ArcTan2(Sum{i=1..n}(Sin(Alpha[i])), Sum{i}(Cos(Alpha[i]))) 

кажется, что для вас случае вы можете рассчитать среднее косинусов векторов направления (потому что Cos (-альф) = cos (альфа)), и получить ArcCos (в диапазоне 0..Pi)

MeanAngleWithoutDir = ArcCos(1/n * Sum{i=1..n}(Cos(Alpha[i]))) 

Вероятно, углы должны быть прижата к (0..Pi) или (-Pi/2..Pi/2) в диапазоне, чтобы избежать неоднозначности.

Answer 3

Мета примечание: этот ответ вычисляет медианную “ ” данных строк. other answer от MBo вычисляет “ среднее значение ” данных строк.

---

Оформить проблему следующим образом. Нам дается коллекция строк, и мы хотим найти строку p так, чтобы сумма углов между p и всеми указанными линиями была минимально возможной. Здесь угол между двумя линиями является минимальным из углов в их точке пересечения, или 0, если они параллельны или совпадают. Таким образом, угол между двумя линиями всегда составляет от 0 до 90 градусов.

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

---

Для решения этой задачи изучим производную от указанной суммы. Предположим, у нас есть линия ответа p. Пусть х линии, которые 0-90 градусов по часовой стрелке от р и у линии, которые 0-90 градусов против часовой стрелки от р (х + у = п, общее количество из приведенных строк).

Теперь поверните р небольшим углом α по часовой стрелке. Ответ будет уменьшен на x * α и увеличится на y * α. Итак, если x> y, ответ будет уменьшаться, и если x < y, он будет увеличиваться.

Есть два случая, когда величины x и y изменение.

1. Линия р совпадает с одной из указанных линий.

2. Линия q ортогональна одной из заданных линий.

Между любыми двумя такими последовательными точками на окружности, производная от нашей суммы будет постоянная х - у. Итак, минимум будет на одном из интересующих уголков “ ”: либо параллельный, либо ортогональный к некоторым из заданных линий. Это приводит к O (N^2) алгоритм: для каждого из O (N) углов, представляющих интерес, просто вычислить сумму в O (N) и выбрать угол, который дает минимальную сумму.

---

Это может быть ускорено далее O (N журнал N).

1. Генерировать углы, представляющие интерес 2 н в O (N).

2. Отсортировать их по: O (n log n).

3. Вычислительный ответ, а также х и у, для первого такого угла в O (N).

4. Перемещение по кругу, сохраняя текущий ответ и значения х и у. В каждом из шагов O (n) расчеты могут быть выполнены в O (1).

Answer 4

Ниже приведено решение O(n), которое также может содержать дополнительный вес для каждого сегмента.

Мы моделируем каждый сегмент своим углом с осью X (a) с весом (w). На этом этапе направление сегмента не важно, любое значение по модулю 180 ° будет делать. Идея состоит в том, чтобы петля для каждого сегмента и отслеживать среднее направление, вычисленное до сих пор; и отрегулируйте это среднее с направлением по модулю 180, которое ближе к самому среднему.

Псевдо-код (все углы в градусах):

aa = 0 
ww = 0 
for a, w in segments: 
    // Compute delta between angles in range [-180°..+180°[ 
    da = a - aa 
    if da < -180: 
     da += 360 
    if da >= 180: 
     da -= 360 
    // Optional direction swap, delta in [-90°..+90°[ 
    if da < -90: 
     da += 180 
    if da >= 90: 
     da -= 180 
    // The following formula also make sure aa = a mod 180 
    // when ww = 0 (first iteration). 
    aa += da * w/(w + ww) 
    ww += w 
    // Clamp result to [0°..+360°[ 
    if aa >= 360: 
     aa -= 360 
    if aa < 0: 
     aa += 360 
// Clamp final result aa to [0..+180°[ (optional step) 
if aa > 180: 
    aa -= 180 

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

---

На зависимость этого алгоритма против ввода итерации порядка

Для хорошо себя входных данных, алгоритм является очень стабильным, независимо от того, итерации.

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

Численное моделирование показывает, что для случайных направлений со стандартным отклонением менее 20 ° (вокруг медианы) алгоритм всегда стабилен. При стандартном отклонении более 20 ° начинают появляться числовые неустойчивости, и результат сильно зависит от порядка итерации (между 20 и 30 ° различие, вероятно, достаточно мало, чтобы игнорировать, более 30 ° появляется большая разница).

Я точно не вычислил точное хаотическое/стабильное стандартное отклонение, поэтому возьмите это значение 20 ° как исходное предположение. Точное математическое решение остается как упражнение для читателя.

Ниже приведено численное моделирование (для каждого стандартного отклонения от 0 до 45 ° запускается в 1000 раз алгоритм на различные случайные данные данного стандартного отклонения и измеряется средняя дельта между 10 прогонами).

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

Answer 5

Статистически большинство из них лежат в более или менее одинаковом направлении.

Этот ключевой бит информации будет иметь решающее значение при разработке вашего алгоритма.Если вы знаете, что все векторы лежат в пределах 90 градусов конуса можно использовать очень простой метод:

• взять скалярное произведение первого нормированного вектора направления со всеми остальными
• Флип любых векторов, возвращать отрицательное скалярное произведение
• усреднить полученные векторы как обычный

Если вам необходимо обрабатывать более широкое распространение вы можете изменить это немного:

• суммы ваше нормализованное направление векторов по одному
• перед добавлением вектора, вычислить его скалярное произведение с текущей суммой
• если скалярное произведение отрицательно оборотная вектор перед добавлением к сумме
• нормализовать сумму

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

• для каждого нормированного вектора пары в дереве восстановления
  • взять скалярное произведение пары
  • если он отрицательный флип один из двух векторов и просуммировать их
  • передать сумму к следующему этапу редукции
• нормализует окончательную сумму

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