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

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

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

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

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

Есть какой нибудь приблизительный способ сортировки?
  • Вопрос задан
  • 6199 просмотров
Пригласить эксперта
Ответы на вопрос 5
Пример одного из вариантов на скриншоте (Python).
84648af2f5b44cf2beea86df1eec2629.png

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

Алгоритм набросал навскидку и в лоб. Указанные условия вроде все соблюдены. Принцип показал, детали доработаете сами (порядок сортировки и т.д.).
Ответ написан
Комментировать
SHVV
@SHVV
Мне кажется, или вы пытаетесь изобрести триангуляцию Делоне?
Хотелось бы больше знать об исходных данных и целевой задаче.
Ответ написан
vipuhoff
@vipuhoff
теоретически не вижу ничего сложного, можно попробовать так, ищем центр масс точек, далее меняем координаты от декартовых к полярным, где нового пространства находится в центре масс, определяем координаты всех точек в полярных координатах, сортируем по углу, берем все точки по порядку и получаем то что нужно.
Ответ написан
Комментировать
Mrrl
@Mrrl
Заводчик кардиганов
Результат сортировки будет красивее, если делать так.
Рекурсия:
- делим более длинную сторону матрицы на две равные (или различающиеся на 1) части.
- если длинная сторона была вертикальной, то сортируем элементы матрицы по y, чтобы элементы с меньшим y оказались в нижней половине, а если горизонтальной - то сортируем по x, чтобы элементы с меньшим x оказались в левой половине. Сортируем не строки-столбцы, а матрицу в целом (как одномерный массив).
- повторяем процедуру для каждой из полученных половинок.
Ответ написан
Комментировать
akhmelev
@akhmelev
программист
Медленно, но без потерь памяти - перестановками. Т.е. если не очень важна скорость используйте сортировку хотя бы тем же пузырьком, но двухмерную. Перебираем все элементы матрицы двигаясь по побочным диагоналям 11 12 21 13 22 31.... Каждый элемент нужно сравнить с 8 элементами вокруг него (хотя, на самом деле хватит и трех, правее, ниже, правее-ниже) и найти наилучшего кандидата на обмен местами. Сравнение вести по сумме x+y или лучше по квадрату длины вектора (x^2+y^2). Повторять перебор матрицы пока есть обмены. Т.к. самый тяжёлый элемент упадёт в конец матрицы, можно каждый новый проход делать не единицу короче.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы