Измерение прямолинейности сегмента кривой (представленного в виде ломаной линии)

11

Я работаю над автоматическим алгоритмом маркировки контура возвышения, и один из факторов, который я хочу принять во внимание при определении положения меток, - насколько «прямолинейен» конкретный сегмент контура. Чем оно прямее, тем больше вероятность, что оно будет использовано для размещения метки на этом сегменте.

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

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

Игорь Брейц
источник

Ответы:

9

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

Например, предположим , что вы собираетесь проводить систематический поискчерез всю связную компоненту контура, представленную как последовательность точек P (0), P (1), ..., P (n). Это было бы сделано путем инициализации одного указателя (индекса в последовательности) s = 0 («s» для «начала») и другого указателя f (для «конца»), чтобы быть наименьшим индексом, для которого расстояние (P (f), P (s))> = 100, а затем продвижение s на расстояние, равное расстоянию (P (f), P (s + 1))> = 100. В результате получается кандидатная ломаная (P (s), P (s +) 1) ..., P (f-1), P (f)) для оценки. Оценив его «пригодность» для поддержки метки, вы затем увеличиваете s на 1 (s = s + 1) и переходите к увеличению f до (скажем) f 'и s до s' до тех пор, пока еще раз кандидатная ломаная линия не превысит минимальное значение. образуется диапазон 100, представленный как (P (s '), ... P (f), P (f + 1), ..., P (f')). При этом вершины P (s) ... P (s ') Очень желательно, чтобы пригодность могла быть быстро обновлена ​​на основе знания только удаленных и добавленных вершин. (Эта процедура сканирования будет продолжаться до тех пор, пока s = n; как обычно, f должно быть разрешено «оборачиваться» от n до 0 в процессе.)

Это соображение исключает множество возможных мер пригодности ( извилистость , извилистость и т. Д.), Которые в противном случае могли бы быть привлекательными. Это побуждает нас отдавать предпочтение мерам на основе L2 , потому что они, как правило, могут быстро обновляться, когда базовые данные изменяются незначительно. Принимая аналогию с анализом главными компонент предполагает , мы принимаем следующие меры (где маленьким лучше, по запросу): используйте меньшее из двух собственных в ковариационной матрицекоординат точки. Геометрически это является одной мерой «типичного» бокового отклонения вершин в пределах потенциального участка ломаной линии. (Одна интерпретация состоит в том, что его квадратный корень является меньшей полуосью эллипса, представляющего вторые моменты инерции вершин полилинии.) Он будет равен нулю только для наборов коллинеарных вершин; в противном случае он превышает ноль. Он измеряет среднее боковое отклонение относительно базовой линии в 100 пикселей, созданной началом и концом полилинии, и, таким образом, имеет простую интерпретацию.

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

Вот пример результата этого алгоритма. Черные точки - вершины контура. Сплошная красная линия является лучшим кандидатом в полилинии, длина конца в конец больше 100 в пределах этого контура. (Визуально очевидный кандидат в правом верхнем углу не достаточно длинный.)

фигура

Whuber
источник
Ух ты, ты меня там потерял :). Вы правы в систематическом поиске, я уже должен это сделать, чтобы получить тангенс каждой вершины полилинии / многоугольника (горизонтальные метки предпочтительнее вертикальных), поэтому в теории я мог бы расширить этот поиск, чтобы охватить другие измерения. Кстати: вы подготовили образец графика, используя реальный алгоритм или вручную?
Игорь Брейц
1
Иллюстрация реальна, но используемая мною реализация не использует процедуру обновления ковариации и поэтому не является оптимальной в вычислительном отношении.
whuber
2
График в конце делает этот ответ еще более удивительным
Раги Язер Бурхум
2
Игорь, я должен отметить, что направление метки приходит бесплатно: оно задается направлением большой оси эллипса (собственный вектор, связанный с большим собственным значением). Поэтому вы можете одновременно искать эффективный способ поиска наилучшего сочетания ориентации этикетки и линейности сечения контура.
whuber
3

В сообществе компьютерной графики часто бывает необходимо найти ограничивающую рамку вокруг объекта. Следовательно, это хорошо изученная проблема с быстрыми алгоритмами. Например, см. Статью « Минимальные ограничивающие рамки» в Википедии . Вы можете найти прямоугольник минимальной площади, окружающий вашу полилинию, а затем использовать соотношение сторон прямоугольника, высоту / длину. Чтобы получить более точную меру, вы можете посмотреть на отклонение полилинии от центральной линии этого ограничивающего прямоугольника.

Джозеф О'Рурк
источник
1
Я думал об использовании мин. ограничивающие прямоугольники, но я вижу две проблемы: а) вычислительная сложность вычисления прямоугольника, который действительно будет минимальным (и, следовательно, повернутым), б) два сегмента кривой с одинаковым соотношением сторон могут иметь очень разную кривизну (представьте себе синусоидальную) кривая с одинаковой амплитудой, но разными периодами волны).
Игорь Брейц
1
Приятно видеть вас здесь на страницах ГИС, Джозеф!
whuber
1
Да, у меня сейчас в руках твоя книга «Вычислительная геометрия в Си» :)
Игорь Брейк,
1
Спасибо всем за приветствие! :-) Я понимаю, что мое предложение не является идеальной мерой, но кодирование готово (если у вас есть правильная полка). Этот тип проблемы был довольно мало изучен в производственных условиях, где они должны измерять качество обрабатываемой детали.
Джозеф О'Рурк
3

Я не знаю, помогает ли это, или даже если это считается ответом, но когда я сидел здесь и размышлял над вопросом, который только что написал, у меня возникла мысль:

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

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

Я уверен, что это не очень помогает, и то, что я говорю по-английски, намного сложнее на любом языке программирования, который вы используете, но это может быть началом?

Рекс-Н
источник
Интересная идея. Чтобы упростить задачу, вы можете рассчитать соотношение между длиной сегмента на одной стороне и расстоянием между начальной и конечной точками. Это не так точно, но это быстро рассчитать. А ваша идея использования круга позволила бы более точно рассчитать прямолинейность.
Игорь Брейц
3

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

Это должно быть действительно простым в реализации решением.


Обновление: Как правильно заметил Майк, это будет равно Sinuosity .

введите описание изображения здесь

Подземье
источник
Именно то, что пришло мне в голову после прочтения ответа Рекса :)
Игорь Брейц
4
в основном взаимность извилистости
Майк Т
точно :) ....
Подземье
2
Вы правы в том, что это легко реализовать, потому что обновление длины при поиске соответствующих сегментов для метки так же просто, как сложение и вычитание длин между последовательными вершинами. Тем не менее, извилистость не совсем отражает смысл, в котором кривая может отклоняться от линейности. Например, сравните полукруг диаметра 100 с линейной последовательностью полукругов диаметра 1 : обе кривые имеют одинаковую извилистость, но отклонение из стороны в сторону от первой в 100 раз больше, чем у второй (что было бы хорошей основой для этикетки).
whuber
Примите во внимание, что если ваша ломаная линия нарисует круг, этот метод даст вам бесконечную извилистость, которая, возможно, не является желаемым результатом.
obchardon
1

Поиск "кривизна" и "полилиния", я получил эту информацию Как я могу найти кривизну полилинии? , Там он предложил использовать возврат к определению кривизны - K= DF/Ds. Здесь Fон имеет в виду phi, или Tв примечаниях Википедии здесь ( http://en.wikipedia.org/wiki/Curvature ).

Скажем, у вас есть последовательность трех точек, p0, p1 и p2. вычислите расстояние sмежду p0 и p1, которое является дельтой s ( Ds), предполагая, что точки находятся близко друг к другу. Тогда вам нужна дельта T ( DT), которая представляет собой изменение единичного тангенциального вектора между p0 и p1. это может быть сложный способ, но грубый метод, который я могу придумать, состоит в том, чтобы взять два вектора p0-> p1, p1-> p2, нормализовать каждый, чтобы иметь длину один, затем взять векторное вычитание этих двух, а затем определить величину. То есть DT. Деление дает кривизну K0_1. возьмите p1, p2 и p3 для вычисления K1_2и так далее.

Мне интересно, если вы получите контур как ломаную линию, а не как визуализированные пиксели. Вы сказали 100px, так что я немного волнуюсь.

yosukesabai
источник
Спасибо за ссылку, мне придется изучить математику за ней. Я упомянул 100px просто потому, что отображаемый текст метки имеет определенную ширину (в пикселях), 100px был просто примером.
Игорь Брейц
Думать о кривизне это хорошая идея. Кривизна на сильно сглаженных участках контура достаточной длины может быть целесообразной, но сама кривизна - нет: например, один маленький зигзаг будет иметь чрезвычайно высокую кривизну, но в целом будет несущественным. Таким образом, по сути, вы будете использовать некоторую статистическую сводку отклонения от линейности по участкам полилинии. Среди вероятных кандидатов, кривизна будет одним из наиболее сложных вычислений для выполнения.
whuber