C ++ найти, где набор точек лежит между двумя другими - PullRequest
Новая
       9

C ++ найти, где набор точек лежит между двумя другими

0 голосов
/ 02 мая 2018

У меня есть три набора 2d очков. Что мне нужно сделать, это выяснить, где находится один по отношению к двум другим. Каждый сет имеет одинаковые точки в одинаковом порядке. Один «нейтрален», один «макс», а третий неизвестен. Что мне нужно, это вернуть одно значение, от 0 до 1, которое иллюстрирует количество, которое неизвестный набор находится между двумя другими.

Например, на изображении:

points

Я бы каким-то образом вычислил «расстояние» или «вес» между множеством А и множеством В, а затем выяснил, где между ними находится множество С. В этом примере я ожидал бы значение около 75% или 0,75.

Я смотрел на использование алгоритмов регистрации набора точек, которые возвращают масштабное значение, чтобы сопоставить Набор C с Набором B, но я не уверен, что это лучший способ. Какой подход подойдет для этой проблемы? Какие алгоритмы мне нужно искать?

1 Ответ

0 голосов
/ 03 мая 2018

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

Давайте сосредоточимся на одной точке p. Мы знаем его координаты во всех наборах p_A, p_B и p_C. Затем мы указываем, что p_C является более или менее линейной интерполяцией между p_A и p_B с параметром t (где t=0 представляет набор A, а t=1 представляет набор B): 

      p_C = (1 - t) * p_A + t * p_B
          = p_A - t * p_A + t * p_B
          = p_A + t * (p_B - p_A)
p_C - p_A = t * (p_B - p_A)

Теперь вопрос заключается в том, чтобы найти t, который приблизительно соответствует всем вашим точкам.

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

arg min_t Σ_i (pi_C.x - pi_A.x - t * (pi_B.x - pi_A.x))^2
               + (pi_C.y - pi_A.y - t * (pi_B.y - pi_A.y))^2

Оптимальный t равен: 

numX = Σ_i (pi_A.x^2 - pi_A.x * pi_B.x - pi_A.x * pi_C.x + pi_B.x * pi_C.x)
numY = Σ_i (pi_A.y^2 - pi_A.y * pi_B.y - pi_A.y * pi_C.y + pi_B.y * pi_C.y)
denX = Σ_i (pi_A.x^2 - 2 * pi_A.x * pi_B.x + pi_B.x^2)
denY = Σ_i (pi_A.y^2 - 2 * pi_A.y * pi_B.y + pi_B.y^2)
t = (numX + numY) / (denX + denY)

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

...