Как я могу измерить прямолинейность нарисованной линии?

37

Я работаю над игрой, которая требует, чтобы игроки рисовали линию от точки A (x1, y1) до другой точки B (x2, y2) на экране устройства Android.

Я хочу выяснить, насколько хорошо этот рисунок подходит к прямой линии. Например, результат 90% будет означать, что рисунок почти идеально соответствует линии. Если игроки проводят изогнутую линию от А до В, она должна получить низкую оценку.

Конечные точки заранее неизвестны. Как я могу это сделать?

user3637362
источник
1
Вы знаете заранее, каковы ваши две конечные точки? Или определяется в тот момент, когда пользователь перестает касаться экрана?
Vaillancourt
Извините, если мое описание вам не понятно. Ну, начальная точка A (x, y) - это первое касание, а конечная точка B (x, y) - когда мы отпустили сенсорный экран, как вы сказали.
user3637362
У нас есть связанный вопрос на соответствие нарисованных игроком букв .
Анко
3
Пожалуйста, не размещайте изображения для исходного кода в будущем.
Джош
1
@ user3637362 Я понимаю, что вы начинаете, j=1так что вы можете сравнить touchList[j]с touchList[j-1], но когда touch.phase == TouchPhase.Beganили touch.phase == TouchPhase.Endedпозиции не добавляются touchListи впоследствии не включены в sumLength. Эта ошибка будет присутствовать во всех случаях, но будет более очевидной, когда линия имеет несколько сегментов.
Келли Томас,

Ответы:

52

Совершенно прямая линия также будет самой короткой из возможных линий общей длиной sqrt((x1-x2)² + (y1-y2)²). Более набросанная линия будет менее идеальной связью и, следовательно, будет неизбежно более длинной.

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

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

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

Счет или индекс извилистости 1 был бы идеальным, все, что выше, было бы менее совершенным, что-либо ниже 1 было бы ошибкой. Когда вы предпочитаете иметь счет в процентах, разделите 100% на это число.

Philipp
источник
34
Есть небольшая проблема с этим подходом в том, что полилинии одинаковой длины не являются одинаково «прямыми». Линия, которая колеблется с низким отклонением (но много раз) вокруг прямой линии, является «более прямой», чем линия равной длины, которая отклоняется в одну точку, а затем обратно.
Dancrumb
Я не могу +1 комментарий @Dancrumbs достаточно - это довольно серьезное ограничение для этого метода, так как если пользователь рисует прямую линию, он немного колеблется, так что это похоже на обычный случай использования.
Т. Кили
@ Dancrumb просто учитывает среднее расстояние от линии или «максимальное расстояние» любой точки от линии. Затем вы можете взвесить алгоритм в направлении более шатких линий с меньшими амплитудами отклонения и от линий, отклоняющихся от ожидаемого пути.
Superdoggy
2
@ Dancrumb для меня это звучит так, как будто это может закончиться выгодой для сценария использования ОП. Рисованные линии, конечно, будут иметь небольшие отклонения. Этот подход может фактически работать, чтобы ослабить эффект этих ожидаемых различий.
2
@ user3637362 у вас есть ошибка в вашем коде. Возможное объяснение состоит в том, что вы забыли учесть расстояние между начальной точкой и первой точкой или конечной точкой и последней точкой, но не глядя на ваш код, невозможно сказать, в чем может быть ваша ошибка.
Филипп
31

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

RMSD = sqrt(mean(deviation^2))

Заметка:

  • Сумма абсолютных отклонений (в виде интеграла) может быть лучше, поскольку она не усредняет положительные ошибки с отрицательными. (=sum(abs(deviation)) )
  • Возможно, вам придется искать кратчайшее расстояние до линейной линии, если есть способ, который создает более короткие расстояния, чем падение перпендикуляра.

рисунок

(Прошу прощения за низкое качество моего рисунка)

Как видите, вы должны

  1. найти ортогональный вектор к вашей линии ( скалярное произведение равно 0 ).
    Если ваша линия указывает на(1, 3) то, что вы хотите (3, -1)(через начало координат)
  2. Измерьте расстояния h от идеальной линии до пользовательской, параллельной этому вектору.
  3. Рассчитайте RMSD или сумму абсолютных разниц.
gr4nt3d
источник
Ответ Джоэля Босвелда указывает на интересный случай: почти идеально прямая линия с углами в начале и в конце. Если линия должна быть нарисована пользователем свободно, это действительно проблема. Тем не менее, я думаю, что этот метод может охватить этот сценарий. Фактически можно выполнить подбор с помощью RMSD или абсолютного интеграла в качестве минимально допустимого значения. Начальные значения могут быть начальной и конечной точками. Поскольку длина не имеет значения, также не имеет значения, будет ли оптимизация смещать точки так, чтобы идеальная линия протягивалась дальше или была короче (высота должна быть рассчитана до этого niveau).
gr4nt3d
1
Другой случай, который, кажется, не охватывается: скажем, каждая измеренная точка находится на оси x, но линия меняет направление несколько раз. Это вернет ошибку 0.
Дэйв Манкофф
23

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

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

Если мы примем положение в момент времени t (x (t), y (t)), то касательная будет (Dx (t), Dy (t)), где Dx (t) - производная от x в момент времени t (на этом сайте отсутствует поддержка TeX). Если кривая не параметризована длиной дуги, мы нормализуем ее делением на || (Dx (t), Dy (t)) ||. Таким образом, у нас есть единичный вектор (или угол) касательной к кривой в момент времени t. Таким образом, угол a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Затем нас интересует || Da (t) || ^ 2, интегрированное вдоль кривой.

Учитывая, что у нас, скорее всего, есть дискретные точки данных, а не кривая, мы должны использовать конечные разности для аппроксимации производных. Итак, Да (т) становится (a(t+h)-a(t))/h. И, (т) становится ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Затем мы получаем S путем суммирования h||Da(t)||^2для всех точек данных и, возможно, нормализации по длине кривой. Скорее всего, мы используем h=1, но это действительно просто произвольный масштабный коэффициент.

Повторим, S будет нулем для линии и чем больше, тем больше она отклоняется от линии. Для преобразования в нужный формат используйте 1/(1+S). Учитывая, что масштаб является несколько произвольным, можно умножить S на некоторое положительное число (или преобразовать его другим способом, например, использовать bS ^ c вместо S), чтобы отрегулировать, насколько прямолинейны определенные кривые.

Джоэл Босвелд
источник
2
Это наиболее разумное определение прямолинейности.
отмечает Томас
1
Это, безусловно, самый разумный ответ, и я уверен, что другие станут очень разочаровывающими. К сожалению, форма, в которой представлено решение, немного более неясна, чем другие, но я бы порекомендовал, чтобы ФП сохранялась.
Дэн Шеппард
Вообще я тоже считаю этот ответ действительно лучшим. Хотя проблема беспокоит меня: что произойдет, если линия не будет «достаточно гладкой»? Например, если у вас есть два совершенно прямых отрезка с углом, скажем, 90 °. Я ошибаюсь или это приведет к довольно низкому результату по сравнению с действительно гладкой линейной линией? (Я думаю, что пользовательский случай Данкрамба с шаткой линией был похожей проблемой) ... Локально это, конечно, лучший способ.
gr4nt3d
3

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

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

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

Лучник
источник
3

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

  1. Используйте метод наименьших квадратов для всех точек (это предотвращает проблему конечного перегиба, упомянутую Джоэлем Босвелдом).
  2. Для всех точек кривой определите расстояние до линии. Это тоже стандартная проблема. (линейная алгебра, базовое преобразование.)
  3. Суммируйте все расстояния.
MSalters
источник
Не могли бы вы возражать, если бы я попросил у вас какое-нибудь текстовое кодирование (JS, C #) или псевдокод, поскольку большинство ответов выше описаны теоретически, я не знаю, как начать?
user3637362
1
@ user3637362: у StackOverflow есть практические ответы: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

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

Вот кое-что, с чего можно начать в псевдокоде:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

Что cumulativeDistanceможет дать вам представление о примерке. Расстояние 0 означало бы, что пользователь все время был на линии. Теперь вам нужно сделать несколько тестов, чтобы увидеть, как он ведет себя в вашем контексте. И вы можете усилить возвращаемое значение distanceOfPointToLine, возведя его в квадрат, чтобы наказать больше на больших расстояниях от линии.

Я не знаком с единством, но код updateздесь может идти вonDrag функции.

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

Vaillancourt
источник
5
Когда вы складываете расстояние между идеальной линией и точкой для каждой измеренной точки, вам необходимо учитывать количество принятых мер, в противном случае, когда пользователь рисует медленнее или использует устройство с более высокой скоростью сканирования, он регистрирует больше. очки, что означает, что они получат худшую оценку.
Филипп
@ Филипп Да, вы делаете! Я должен признать, что ваш способ сделать это кажется лучше, чем мой: P
Vaillancourt
Я думаю, что этот подход улучшен, если брать среднее расстояние, а не совокупное расстояние.
Dancrumb
@Dancrumb Действительно, это зависит от потребностей, но да, это был бы способ сделать это.
Vaillancourt
2

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

Редактировать:

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

Кик
источник
1

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

Чем толще должна быть линия, тем хуже пользователь рисовал ее.

Адам Дэвис
источник
0

Как-то со ссылкой на MSalters Answer, здесь есть более конкретная информация.

Используйте метод наименьших квадратов, чтобы подогнать линию под ваши точки. Вы в основном ищете функцию y = f (x), которая подходит лучше всего. Получив его, вы можете использовать действительные значения y, чтобы сложить квадрат разностей:

s = сумма за ((yf (x)) ^ 2)

Чем меньше сумма, тем прямее линия.

Как получить наилучшее приближение, объясняется здесь: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Просто прочитайте из "Установка прямой линии". Обратите внимание, что t используется вместо x и b вместо y. C и D должны быть определены как приближение, тогда у вас есть f (x) = C + Dx

Дополнительное примечание: Очевидно, что вы также должны принять во внимание длину линии. Каждая линия, состоящая из 2 очков, будет идеальной. Я не знаю точного контекста, но, думаю, я бы использовал сумму квадратов, деленную на количество очков, в качестве рейтинга. Также я бы добавил требование минимальной длины, минимального количества баллов. (Может быть, около 75% от максимальной длины)

Philipp
источник