Сортировка двумерного массива. Хитрая...
Задача. Есть массив координат точек (X, Y) который не упорядочен. Нужно пересортировать массив так, чтобы координаты стояли в таком порядке, что соответствующие им точки располагались бы на картинке последовательно, например, первый элемент массива - это верхняя левая точка, второй элемент - вторая сверху точка в первом столбце. и так далее.
Сложность в том что точки располагаются на картинке не "квадратно-гнездовым" способом, а с небольшими отклонениями (как показано на прикрепленной картинке). Идеи по реализации алгоритма?
Вот пример неупорядоченного массива координат точек (примерно соответствует тому что на изображении):
128 24
15 20
66 26
69 81
22 73
191 180
134 72
145 127
182 90
18 127
81 128
150 168
185 129
22 173
182 15
83 177
Сложность в том что точки располагаются на картинке не "квадратно-гнездовым" способом, а с небольшими отклонениями (как показано на прикрепленной картинке). Идеи по реализации алгоритма?
Вот пример неупорядоченного массива координат точек (примерно соответствует тому что на изображении):
128 24
15 20
66 26
69 81
22 73
191 180
134 72
145 127
182 90
18 127
81 128
150 168
185 129
22 173
182 15
83 177
[QUOTE=Andreww]Хе, хе, в том то и дело, что если б можно было наложить сетку то эта софтинка была б уже давно написана, а так реальность такова что пятна на картинке иногда получаются сильно сильно разбросанными, поэтому мне пришлось находить их хитрыми способами -- отсюда и "кривые" массивы которые требуют хитрой сортировки....[/QUOTE]В каком смысле не можно наложить сетку? На те 16 точек я вчера "сетку наложил". Прога из 80 команд определила, что можно наложить сетку 4*4 и 8*2. Если добавить определение средней длины столбцов и высоты строк, тогда ответом будет 4*4. Нужно только, чтоб в этих наборах отдельные столбцы можно было отделить вертикальными прямыми, а строки горизонтальными. Т.е. чтоб ни одна точка не лезла напр. в чужой столбец. Но даже эту аномалию можно решить, но тогда прога будет довольно сложна.
В том то и дело, что на ту картинку из 4х4 сетку наложить можно, но иногда получаются картинки, в которых точки могут залазить в соседние столбцы или строки. Так что лучше пока заставлю пользователя самому вводить кол-во строк и столбцов, а дальше посмотрим...
[QUOTE=Andreww]В том то и дело, что на ту картинку из 4х4 сетку наложить можно, но иногда получаются картинки, в которых точки могут залазить в соседние столбцы или строки. Так что лучше пока заставлю пользователя самому вводить кол-во строк и столбцов, а дальше посмотрим...[/QUOTE]Главное чтоб твоя программа соответствовала Стандарту С++, а все остальное, напр. использование компьютером пользователя в качестве счетной машинки, это мелочи жизни.
[QUOTE=Merlin]Если для одной точки первого файла найдется 3 равноудаленных точек второго файла, тогда которую из этих трех выбрать?[/QUOTE]
Тогда всё равно, какую выбирать. Но и это, и "залазиние" точек в другие столбцы и строки - отклонение от первоначального условия.
[QUOTE=Andreww]иногда получаются картинки, в которых точки могут залазить в соседние столбцы или строки. [/QUOTE]
Если точки могут залазить в соседние столбцы или строки, то о каком решении вообще может идти речь? Ты же сам вначале написал, что точки укладываются в правильную сетку. А так получается, что мы всё-таки имеем беспорядочный набор точек. По моему, в этом случае и пользователь не сможет выделить столбцы и строки. Разве что такие отклонения будут очень редкими, как бы исключением из общего правила. Если не секрет, зачем всё это нужно? Нельзя ли достичь конечной цели программы другим путём?
Тогда всё равно, какую выбирать. Но и это, и "залазиние" точек в другие столбцы и строки - отклонение от первоначального условия.
[QUOTE=Andreww]иногда получаются картинки, в которых точки могут залазить в соседние столбцы или строки. [/QUOTE]
Если точки могут залазить в соседние столбцы или строки, то о каком решении вообще может идти речь? Ты же сам вначале написал, что точки укладываются в правильную сетку. А так получается, что мы всё-таки имеем беспорядочный набор точек. По моему, в этом случае и пользователь не сможет выделить столбцы и строки. Разве что такие отклонения будут очень редкими, как бы исключением из общего правила. Если не секрет, зачем всё это нужно? Нельзя ли достичь конечной цели программы другим путём?
[QUOTE=ShadyMan]Тогда всё равно, какую выбирать. Но и это, и "залазиние" точек в другие столбцы и строки - отклонение от первоначального условия.[/QUOTE]Не может быть все равно какую выбрать. На рисунке синие - старые точки, красные - новые точки. Если для 1 выбрать 4, тогда для 2 придется выбрать 3, но 3 это явно не новая точка 2-и.
Конечно при условии, что если например новая точка попадая в левый столбец, остается правее от левого соседа. Если это не так, т.е. соседние точки могут меняться столбцами, тогда мусор на входе, мусор на выходе(gigo).
Конечно при условии, что если например новая точка попадая в левый столбец, остается правее от левого соседа. Если это не так, т.е. соседние точки могут меняться столбцами, тогда мусор на входе, мусор на выходе(gigo).
Точки в сетку укладываются. Но в редких случаях они могут немножко залазить в чужие области. Сильное залазенье в чужие области и смена точек местами -- это понятное дело, очень тяжелый случай который в практике не наблюдается и поэтому мы его не рассматриваем. У нас все в меру.
Зачем это нужно.... Ну расскажу тогда матчасть.... Для анализа волновых фронтов в оптике используются матрицы Шека-Гартмана, представляющие из себя массив маленьких линзочек. Линзочек обычно бывает 13х18, диаметр одной линзочки порядка 0.4 мм.
Через эту матрицу линз пропускается световой поток, вначале с заведомо плоской волной (записываются те самые эквидистантно расположенные точки), а затем с искаженной волной -- в этом случае точки получаются уже не равноудаленными друг от друга, а слегка разбросанными. Забыл сказать -- точки это места где фокусируется свет от каждой линзочки.
Сравнивая картинку полученную для плоской световой волны с картинкой записанной для искаженной волны мы можем узнать форму искаженного волнового фронта.
Это все применяется в офтальмологии и астрономической оптике. Ну, вроде кратко обьяснил :-)
Зачем это нужно.... Ну расскажу тогда матчасть.... Для анализа волновых фронтов в оптике используются матрицы Шека-Гартмана, представляющие из себя массив маленьких линзочек. Линзочек обычно бывает 13х18, диаметр одной линзочки порядка 0.4 мм.
Через эту матрицу линз пропускается световой поток, вначале с заведомо плоской волной (записываются те самые эквидистантно расположенные точки), а затем с искаженной волной -- в этом случае точки получаются уже не равноудаленными друг от друга, а слегка разбросанными. Забыл сказать -- точки это места где фокусируется свет от каждой линзочки.
Сравнивая картинку полученную для плоской световой волны с картинкой записанной для искаженной волны мы можем узнать форму искаженного волнового фронта.
Это все применяется в офтальмологии и астрономической оптике. Ну, вроде кратко обьяснил :-)
[QUOTE=Andreww]Для анализа волновых фронтов в оптике используются матрицы Шека-Гартмана...[/QUOTE]
Бла-бла-бла-бла-бла... :p :p :p Это то, что я воспринимаю на своём интеллектуальном уровне. Сожалею, что подал неоправданные надежды на помощь, но я так далёк от физики и математики...
Бла-бла-бла-бла-бла... :p :p :p Это то, что я воспринимаю на своём интеллектуальном уровне. Сожалею, что подал неоправданные надежды на помощь, но я так далёк от физики и математики...