3

Есть массив точек X{x,y}, образующих замкнутый гладкий контур (аэродинамический профиль). Точки изначально расположены в массиве хаотично и неравномерно. Подскажите алгоритм сортировки, позволяющий расположить точки по логическому порядку.

UPD. Лимит коментариев((. Точки на профиле расположены примерно так (в большинстве случаев)

alt text

т.е. в местах с большим радиусом кривизны пореже и наоборот. Шаг точеки может быть как маленьким, так и относительно большим. (@alexz)

4 ответа 4

2

Или я неправильно понял условие или однозначного решения нет. Например на приведеной ниже картинке точки можно расположить как минимум в 2-х разных порядках: Пример

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

4
  • Немного я не полно описал. Не помню как это правильно назвать (такой вид контура), но такой ситуации в моем случае не может быть вроде. Контуры представляют собой [аэродинамический профиль][1]. [1]: ru.wikipedia.org/wiki/… 11 окт 2011 в 12:25
  • 1
    Все эти профили, кроме Жуковского, выпуклые. Вы это имели ввиду?
    – dzhioev
    11 окт 2011 в 12:47
  • Да-да. Именно так 12 окт 2011 в 4:21
  • Идея с оболочкой интересна. Но как быть с профилями типа того самого Жуковского? Или хотябы как отличить такие профили? 12 окт 2011 в 4:28
2
  1. Берем произвольную точку.
  2. Вычеркиваем из общего списка неразобранных точек, помещаем в выходной список.
  3. Находим точку, которая ближе всего к исходной. Используем обычную декартовскую меру расстояния.
  4. Вычеркиваем ее из списка неразобранных, помещаем в выходной список.
  5. Если есть еще неразобранные точки - идем к п.3.

По замечаниям и обсуждениям усисливаем позицию :-) :

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

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

3
  • Идея хорошая. Но (опять же моя ошибка в вопросе), точки могут быть расположены очень не равномерно. И необходимая следующая точка может быть по расстоянию дальше какой-нибудь "ненужной". 11 окт 2011 в 12:31
  • По-моему, если это гладкий контур, то вряд ли :-) Разумеется, эффективность метода во многом зависит от частоты дискретизации. Если мы говорим о фигуре профиля, то нужно позаботиться о том, чтобы на участках с малой толщиной отсчеты брались чаще - хотя бы в полтора раза чаще чем толщина профиля. 11 окт 2011 в 17:53
  • Это факт. Некоторые участки могут быть близкими к прямой - в этих местах точки расположены редко. 12 окт 2011 в 4:23
1

По мне - для начала достаточно отсортировать по возрастанию координат. Например, по x. Если будут точки с одинаковой координатой x - отсортировать их по y. Теперь если их соединить получается ломаная. Зигзагообразная. А теперь нужно придумать как разбить точки на два класса - на одну кривую аэродинамического профиля и на другую. Пока идеи нет как это сделать.

Если фигура стабильно выпуклая - можно заюзать алгоритмы триангуляции. Они как раз делают массив "ребер" на выходе, а затем уже можно выбрать среди них нужные.

2
  • С триангуляцией немного непонятно как потом ребра выбирать. После триангуляции, как мне кажется, задача не сильно упростится. А вот с отбором по координатам конечно можно придумать что-нибудь. С плоско-выпуклыми и выпуклыми все понятно. Первая половина массива отсортирована по x && y выше "базовой линии", вторая половина - y ниже линии или на ней. А как быть с выпукло-вогнутыми (тот же Жуковский)? Какие предложения? 12 окт 2011 в 4:42
  • Сложный вопрос. Можно попробовать выстроить контур, взяв произвольную точку, найти ближайшую. Затем найти ближайшую к любой из двух, и поместить в голову списка или в хвост в зависимости от расстояния до головы/хвоста. Затем повторить для оставшихся (найти ближайшую к крайним из найденых). И т.д. Сильно зависит от исходных данных (например как выбираются точки, какой профиль, etc.)
    – alexlz
    12 окт 2011 в 5:21
1
  1. Находим центр. Точка с коорд x0 = средняя X всех точек, y0 аналогично. Вариант: (xmin+xmax)/2, и y так же
  2. Вычисляете угол между центром и точкой (центр в полярной системе координат) в диапазоне от 0 до 2pi (или -pi до pi)
  3. Сортируете в нужном Вам порядке обхода

Но это только для выпуклых фигур.

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

alt text

Вот тут одна из проблем автоматического построения

alt text

7
  • Мне кажется это ближе всего к истине. Подойдет и для выпукло-вогнутых профилей если правильно определить центр. Если центр будет находиться внутри профиля (даже выпукло-вогнутого) то угол от "нужной" точки к точке будет постоянно возрастать (или убывать). С абсциссой все просто. А как правильно найти ординату центра так, чтобы она была внутри профиля? 12 окт 2011 в 5:23
  • 1
    Вряд ли это хорошая идея. Потому что при центре внутри профиля некоторые точки нижней вогнутой части будут идти в неправильном порядке.
    – alexlz
    12 окт 2011 в 5:44
  • А что есть неправильный порядок? И почему некоторые точки? Какие некоторые? Если точки будут идти в порядке "по часовой или против" начиная с точки с Xmax, то это идеальный вариант. Так как потом это все еще нарисовать надо (иногда сплайном). 12 окт 2011 в 5:53
  • Блииин. Да. Мои извинения! Все больше склоняюсь к тому, что сначала нужно выделить нижнюю и верхнюю дуги, а выполнять сортировку отдельно для каждой, а потом каким-то способом лепить общий массив. Есть идеи? 12 окт 2011 в 7:46
  • Проблема глобальная или нужно решение конкретной задачи? Возможно надо "что-то в консерватории подправить". Т.е. каким образом Вы получаете координаты точек? Может быть что-то там? Допустим, точки скалываются с чертежа на регулярной основе (ну кроме вставки ранее пропущенных при съёме).
    – alexlz
    12 окт 2011 в 8:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.