Упорядочение набора неорганизованных точек вдоль кривой

9

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

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

Есть ли какой-либо известный подход для такого рода проблем?

Некоторая дополнительная информация:

  • Кривые в целом являются параметрическими (сплайны / Безье, круговые срезы ..).
  • Точки даны как координаты с плавающей точкой.
  • Точки упакованы очень плотно (но они могут быть настолько плотными, насколько я хочу). Чтобы дать вам представление, для кривой, которая занимает 19 единиц в x, 10 единиц в x и 5 единиц в z, я процитирую последовательность точек в сегменте кривой: (20.7622, ​​25.8676, 0) (20.6573, 25.856, 0) (20,5529, 25,8444, 0) (20,4489, 25,8329, 0) (20,3454, 25,8213, 0)
andrea.al
источник
Даже если мы знаем порядок, существует бесконечное количество кривых, подходящих к точкам. Даже если мы добавим дополнительные ограничения, то открытые концы проблематичны, так как их касательная ориентация может быть произвольной. Картина здесь
joojaa
@joojaa Да, ты прав. Но так как упаковка очков очень плотная, я не ожидаю, что она будет точной. Если я получу правильный порядок, я планировал соединить последовательность точек в виде ломаной линии.
andrea.al
В коде, который должен упорядочить точки, вы даже знаете о параметрической форме кривой? (Если нет, я удалю свой первый ответ, потому что он требует, чтобы вы знали параметрическую форму.)
Мартин Эндер
@ MartinBüttner Да, у меня есть доступ к параметрической форме кривой, если это необходимо.
andrea.al
1
Пожалуйста, покажите типичный набор очков!
Ив Дауст

Ответы:

6

У вас есть пример проблемы, которая называется реконструкция кривой из неорганизованных точек . Теперь, когда вы знаете, что искать, вы найдете несколько методов, таких как crust, NN-crust и т. Д. Вот несколько ссылок:

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

LHF
источник
4

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

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

  • О(NжурналN)
  • Вы должны будете сделать специальную обработку для конечных точек. Их два ближайших соседа будут следующими двумя точками вдоль кривой вместо одной с каждой стороны. Вы можете обнаружить их эвристически, если отношение расстояний до двух соседей отличается более чем на некоторый порог (скажем, 1,5, зависит от гладкости вашей кривой и от того, насколько плотно упакованы точки). Или вы можете рассматривать данные о ближайших соседях как график, в котором вы обнаружите, что два соседа конечных точек указывают друг на друга (что не должно происходить где-либо еще на графике).
  • Теперь вы можете просто выбрать одну конечную точку и пройтись по ближайшим соседям (всегда выбирая ту, из которой вы не прибыли), чтобы пересечь точки вдоль кривой.

θ

Мартин Эндер
источник
3

(Икс,Y,Z)(Икс(T),Y(T),Z(T))

(Икс-Икс(T))2+(Y-Y(T))2+(Z-Z(T))2

T

TTT

Мартин Эндер
источник