Как упростить / оптимизировать 3D-путь?

Question

У меня есть куча точек в 3d (массив, содержащий объекты со свойствами x, y, z).

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

_{(источник: lifesine.eu )}

Как я могу очистить этот путь?

На данный момент первое, что приходит на ум, это

• создать массив для оптимизированных путь
• цикл, хотя все точки начинаются с индексом 1 вместо 0 и получить «направление» для пути. Если изменения направления, добавьте последний из две точки (текущий, а не предыдущий) в оптимизированный массив.

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

Примечание. Я использую actionscript 3, но могу понять синтаксис на других языках или псевдокод.

Спасибо!

Answer 1

Проверить Алгоритм Рамера-Дугласа-Пекера

Answer 2

Зациклите все точки, начиная с индекса 1 вместо 0, и получите «направление» для пути. Если направление изменяется, добавьте последнюю из двух точек (текущую, а не предыдущую) к оптимизированному массиву.

Если вы думаете, что это поможет, вы должны либо думать, что Земля плоская; -)

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

Answer 3

Я думаю, ваша первоначальная идея великолепна. Я бы добавил / изменил две вещи:

1) Я бы добавил порог расстояния в ваш алгоритм: только когда вы проверяете текущую точку на некотором минимальном расстоянии от вашей последней «хорошей» точки, вы должны даже протестировать ее. В зависимости от источника данных вашего пути (возможно, от магнитного трекера?), Стационарность может плохо отражаться в ваших исходных данных из-за шума измерений. Это может привести к относительно большим изменениям направления в очень маленькой области, которые по сути бессмысленны.

2) Когда вы обнаружите достаточно большое изменение, не добавляйте текущую проверенную точку (как вы предложили), а предыдущую. В противном случае вы можете искажать путь. Пример (в 2D): путь, состоящий из (0,0) -> (1,0) -> (2,0) -> (3,0) -> (4,0) -> (5,5 ) будет в конечном итоге как (0,0) -> (5,5), используя ваши методы, что я не считаю хорошим представлением пути. Лучше было бы (0, 0) -> (4,0) -> (5,5).

Answer 4

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

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