Разработка алгоритма: отслеживание движущихся точек в трехмерном пространстве - PullRequest
Новая
       6

Разработка алгоритма: отслеживание движущихся точек в трехмерном пространстве

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

Это независимый от языка вопрос, более ориентированный на разработку алгоритмов.

Представьте, что у нас есть два массива точек в трехмерном пространстве (каждый выглядит как [(1, 0, 2), (2, 4, 32), ...])

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

Проблема: Учитывая эти два массива, как можно сопоставить (с разумной степенью точности) каждую сдвинутую точку с ее исходной точкой, а также определить, какие точки являются новыми и не существовали в первом состояние

Идеи: Я думал, что можно применить некую кластеризацию k-средних, но я не уверен, как она справится с тем фактом, что некоторые точки могли быть удалены / добавлены между состояниями. - поэтому я не думаю, что такой подход будет работать хорошо.

Edit:

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

Ответы [ 3 ]

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

Это основано на одном допущении: расстояние сдвига очень мало (по существу, нечеткое измерение) по сравнению с расстоянием между уникальными точками между первым и вторым множеством.

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

Возьмите мин / макс для каждого измерения (x, y, z и т. Д.). Переведите и измените масштаб двух наборов. Точное масштабирование не имеет значения, но вы можете использовать его таким образом, чтобы все точки были положительными и составляли от 0 до 100 в каждом измерении. Это позволяет сравнивать точки более последовательно. Хотя это может не быть строго необходимо и может быть пропущено

Затем вы должны создать двунаправленное отображение (двунаправленный граф) между множеством точек A и множеством точек B, которое будет O (| A | + | B |), где | A | и | B | размеры наборов. Пример двунаправленного отображения: a_to_b[(1.001,2.001)] = [(1.005,1.995)] b_to_a[(1.005,1.995)] = [(1.001,2.001)]

Если a_to_b и b_to_a отображаются друг на друга, то это одна и та же точка с относительно высокой вероятностью.

Если нет, то вы, скорее всего, увидите что-то вроде этого: a_to_b[(1.001,2.007)] = [(1.005,1.995)] b_to_a[(1.005,1.995)] = [(1.500, 2.004)]

a_to_b[(1.500, 2.004)] = [(1.495, 2.009)] b_to_a[(1.495, 2.009)] = [(1.500, 2.004)]

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

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

Возможно, вы захотите получить триангуляцию Делоне для обоих наборов точек, чтобы позволить искать ближайший сосед всех точек намного быстрее из-за знания того, какие точки пространственно соседствуют с данной точкой. Число ребер в графе Делоне, если я правильно помню, равно O (V), поэтому среднее ребро по вершинам равно O (1). Как только вы нашли ближайшую точку. Тем не менее, вам может потребоваться внести некоторые изменения в делавнарные графики, чтобы учесть добавленные / удаленные ребра.

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

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

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

Считайте несопоставленные точки удаленными или добавленными.

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

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

При допущениях, что:

  1. Точки могут сдвигаться под произвольным углом и длиной,
  2. Очки могут случайно исчезнуть,
  3. Очки могут быть добавлены случайным образом и в случайных местах,
  4. Точки (в каждом массиве) определяются исключительно своими координатами без идентификатора любого типа.

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

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

EDIT

После обсуждения с Тедом Хоппом я включаю альтернативный подход, основанный на двух ВСТАВЛЕННЫХ КРИТИЧЕСКИХ предположениях :

  1. Очки перемещаются один и только один раз,
  2. Можно утверждать, что минимальное начальное расстояние между любыми двумя точками известно, назовем его Lmin, а максимальное расстояние любого движения - << <code>LMin, и мы назовем его Mmax.

С этими двумя дополнительными допущениями вы можете думать о механизме следующим образом (JavaScript-подобный код - не проверено!): 

for (i = 0 ; i < Points.Count ; i++) {
    for (j = i + 1 ; j < Points.Count ; j++) {

        if ((ABS(Array1[i].x - Array2[j].x) > Mmax ) ||
            (ABS(Array1[i].y - Array2[j].y) > Mmax ) ||
            (ABS(Array1[i].z - Array2[j].z) > Mmax )    ) {
           // Distance between two points is for sure equal or bigger than max.
           continue ; // Meaning, go to check next point.
        }

        // The check of the distance is split into two stages
        // because, if the first if is true, the actual distance
        // calculation is not needed (and hence time is saved).

        if (Distance_Between_Points(Array1[i],Array2[j]) > Mmax) {
           // Distance between two points is for sure bigger than max.
           continue ; // Meaning, go to check next point.
        }

        // Points appear to be related!!!!!!
        ..........
    }
}
...