Как сделать сортировку матрицы?

Question

[Всеволод Калошин]

Есть матрица координат, так что элемент матрицы содержит одновременно и х и y.

Все "просто" отсортировать матрицу по x по возрастанию, чтобы элементы строк справа налево шли по возрастанию и по y по возрастанию, чтобы элементы столбцов снизу вверх шли по возрастанию.

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

Нужно для поверхности Безье, для составления по точкам многогранника.

Есть какой нибудь приблизительный способ сортировки?

Comments

[DancingOnWater]

Скажите зачем вам сортировка точек для кривой безье?

[Всеволод Калошин]

@DancingOnWater: для поверхности Безье.

[DancingOnWater]

Сори, поверхности. Но смысл не меняется. Для вычисления полиномов сортировка опорных точек необязательна.

Answer 1

[Владлен Грачев]

Пример одного из вариантов на скриншоте (Python).


Если на словах, то примерно так:
1. Разворачиваем исходный массив в одномерный.
2. Сортируем по обеим координатам (с приоритетом по X).
3. Из полученного одномерного массива делаем двумерный, сортируем элементы каждой строки по Y.
4. Транспонируем.

Алгоритм набросал навскидку и в лоб. Указанные условия вроде все соблюдены. Принцип показал, детали доработаете сами (порядок сортировки и т.д.).

Answer 2

[SHVV]

Мне кажется, или вы пытаетесь изобрести триангуляцию Делоне?
Хотелось бы больше знать об исходных данных и целевой задаче.

Comments

[Всеволод Калошин]

Триангуляцию я не изучал, поэтому немного не понимаю при чем она тут.
Задается многогранник NxM с координатами x,y,z. Если взять самые крайние точки многогранника и их соединить, то должен получится выпуклый многоугольник по координатам x,y.
Координаты задаются беспорядочным способом = > его надо отсортировать, так чтобы он стал выпуклым. (ну это я так считаю)
Все это нужно для поверхности Безье.
Может не в верном направлении думаю.

[ppxy]

@Sevchik403: алгоритмы построения выпуклой оболочки посмотрите. Что то по типу вот этого получится. codepen.io/vizauz/pen/gAfaH?editors=001

[SHVV]

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

Answer 3

[Виталий]

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

Answer 4

[Mrrl]

Результат сортировки будет красивее, если делать так.
Рекурсия:
- делим более длинную сторону матрицы на две равные (или различающиеся на 1) части.
- если длинная сторона была вертикальной, то сортируем элементы матрицы по y, чтобы элементы с меньшим y оказались в нижней половине, а если горизонтальной - то сортируем по x, чтобы элементы с меньшим x оказались в левой половине. Сортируем не строки-столбцы, а матрицу в целом (как одномерный массив).
- повторяем процедуру для каждой из полученных половинок.

Answer 5

[Александр Хмелев]

Медленно, но без потерь памяти - перестановками. Т.е. если не очень важна скорость используйте сортировку хотя бы тем же пузырьком, но двухмерную. Перебираем все элементы матрицы двигаясь по побочным диагоналям 11 12 21 13 22 31.... Каждый элемент нужно сравнить с 8 элементами вокруг него (хотя, на самом деле хватит и трех, правее, ниже, правее-ниже) и найти наилучшего кандидата на обмен местами. Сравнение вести по сумме x+y или лучше по квадрату длины вектора (x^2+y^2). Повторять перебор матрицы пока есть обмены. Т.к. самый тяжёлый элемент упадёт в конец матрицы, можно каждый новый проход делать не единицу короче.

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

Все умозрительно. Надо проверять.