Сортировка точек

Реквестирую поддержку теха в lorcode.

Это просто два частных случая (и чем они отличаются?)

Вот точки, принадлежащие контуру буквы П:

               ******************
               *                *
               *    ********    *
               *    *      *    *
               *    *      *    *
               *    *      *    *
               *    *      *    *
               *    *      *    *
               ******      ******

Проблемная область - распознавание изображений. Приведу пример. Есть исходная картинка. Программа разбивает ее на отдельные плоскости по цветовым переходам. Вот пример обработанного изображения. Для наглядности каждая плоскость окрашена отдельным цветом. Каждая плоскость имеет контур. Вот изображение с контурами. На самом деле контур будет толщиной в один пиксель. Из-за особенностей нахождения плоскостей и их слияния, точки контуров в массивах неотсортированы. А их упорядоченность — необходимое условие для дальнейшей обработки. Количество точек в массиве зависит от величины плоскости, может достигать тысяч. Скорость пока не важна, лишь бы работало.

Всё сработает, осиль метод без срезания углов или приведи пруф, нарисуй и выложи пример, где он не сработает с кратким описанием.

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

Ну это даже не многогранник, линия окантовки может быть плавной. Чуть выше я прицепил картинку.

А в чем проблема сортировать и по углу, и по радиусу?

Похоже, такой способ может сработать, спасибо.

Относительно какой точки ты начнёшь вычисление полярных углов и радиусов?

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

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

Спасибо всем.

распознавание изображений

Тогда вычисление расстояний между пикселями это явно что-то не то.
Да тут ближайший сосед с анализом по пиксельной маске 5×5 подойдёт, например.
От шумов и выпавших точек потом легко простой масочкой избавишься (по 4- или 8-связности).

Относительно центра тяжести, ясен пень.

Но я не понял приведенной выше формулы, так что пока отложу этот вариант.

В википедии посмотри, если латех не понимаешь. Просто по-другому формулу и не запишешь. А лоркод, к сожалению, латех не понимает

Чует мое сердце, что ты что-то не то хочешь.

Например, относительно верхней левой.

Допустим. Какие теперь должны быть правила выбора очередной точки в контур, чтобы 1-2-3-4-5 попали в контур в правильной последовательности (ну или 5-4-3-2-1, если угол считать в обратную сторону), с учётом того, что углы и радиусы по возрастанию выстроились в таком порядке:

φ: 2, 3, 1=4, 5 (точки 1 и 4 лежат на одном луче, выходящем из O (насколько это возможно в компьютере))

ρ: 1, 5, 4, 2, 3

                            
               O****************5
               *                *
               *    *******1    *
               *    *      *    4
               *    *      *    *
               *    *      *    *
               *    *      *    *
               *    *      *    *
               ******      2****3

?

                            
               1******************
               *                 *
               2                 *
               *     *******     *
               *     5     *     *
               *     *  O  *     *
               *     *     *     *
               *     *     *     *
               *     *     *     *
               *     *     *     *
               *     *     *     *
               3*****4     *******

Точки по возрастанию углов и радиусов:

φ: 1, 2=5, 3, 4

ρ: 5, 2, 1, 4, 3

И что дальше?

У меня уже пятничное настроение. Кроме того, меня сейчас больше STM32 беспокоит.

Выше я уже намекнул, что надо делать: после перехода с точки 1.5 (которая между 1 и 2) на 2==5, мы видим, что у 5 r > tolerance. Следовательно, про пятую точку «забываем» до поры, до времени и переходим на 2.

Тут вариантов несколько: либо параллельно создавать все кусочки (т.е. когда мы найдем 5, начнем создавать подсписок — внутренний столбец левой колонки), но это геморройно в реализации. Другой вариант — ходить «туда-сюда»: мы идем по угловой координате до тех пор, пока не выйдем на точку 4, где следующей точкой будет далеко отстоящая точка в правом столбце. В этом случае начинаем идти по углу обратно. Уже «собранных» точек в списке нет, поэтому мы благополучно доберемся до точки 5 и пойдем дальше, не обращая внимания на точки внешней границы. После того, как доберемся до точки справа от 4, точки «кончатся» и мы пойдем по углу обратно, завершая контур. В принципе, для любых контуров такое «шукание» сгодится.

Можно сортировать точки объекта, а не контура, по значению координат, сравнивая сначала y, потом x, что-то типа int comp (pt l, pr r) { if (l.y< r.y) return 1; return l.x < r.x; }. Это позволит создать RLE-модель для каждой связной области. Для такого представления известен алгоритм Павлидиса для нахождения контура, как раз то что нужно вам. Кстати, контур объекта это не только внешний, но и контур дыр.

Также для создания подобного представления можно упростить сортировку, использовав более удобный алгоритм заливки для нахождения областей: http://leptonica.com/filling.html

Статья с алгоритмом Павлидиса: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4309833. Есть этот алгоритм и в его книге, изданной и на русском языке: Павлидис Т. Алгоритмы машинной графики и обработки изображений.

Вот в

r > tolerance

и

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

в итоге содержится та же логика, что в ближайшем соседе.

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

Но, выше ТС сказал сакраментальную фразу:

Есть исходная картинка

и дальше по тексту.

В общем, подозреваю, что Гонсалеса и Вудса он не читал. И хочет изобрести велосипед.

Чует мое сердце, что ты что-то не то хочешь.

Почему? :-) Что дает повод так думать?

Можно для определенности четко высказать ТЗ?

Да, набор точек объекта тоже есть, его можно использовать, но я не придумал как. Спасибо за информацию. Я решил упростить: контур дыры — внешний контур другого объекта. Потом все контуры увяжутся вместе отношениями.

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

В общем, подозреваю, что Гонсалеса и Вудса он не читал. И хочет изобрести велосипед.

Не читал, велосипед хочу :-) Вообще, просто пришла в голову идея, описать контуры кривыми Безье, а полученные точки увязать между собой векторами по всем плоскостям. Решил проверить, что получится. Вот пришлось изобретать, как достать из изображения контуры.

ТЗ никакого нет, я сам еще не понимаю, что делаю. Иду шаг за шагом, появилась проблема, я ее решаю. Есть только конечная цель, до которой конкретно далеко.

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

// кстати, на сях реализация есть

Валидных решений может быть множество. Разве что ты ищешь фигуру с максимальной площадью.

Вот тут я эту задачу в L2Fortress решал: http://www.balancer.ru/tech/forum/2007/04/t55143--ischetsya-algoritm-postroen...

Чем кончилось — не помню, давно было :) Какая-то сортировка работала, но насколько я до ума её довёл — не помню.

Границы найдены, разрывов нет. Есть массив точек объекта, по нему я делал раскраску объктов на картинке. Но он тоже несортирован.

Ок, посмотрю.

Спасибо, почитаю.

Оно и есть. Только, учитывая специфику, интерполяции проводить не придется. Только шагающие квадраты.

Словосочетание «аналитическая геометрия» тебе о чем-нибудь говорят?

Ну не стыдно замечательного русского учёного Делоне обзывать всякими французскими именами.

Я дичайше извиняюсь, но грани и ребра есть только у объемных фигур :))) У плоских фигур есть только вершины и отрезки, так что описание темы сразу ввело меня в ступор)
Вершины можно обрабатывать с помощью http://www.qhull.org (я так строил ландшафт как-то). Но вообще задача странновата. Для объединения точек в контур есть множество путей, тебе это зачем? Последовательность точек и есть описание контура фигуры.

Звиняй: уж больно фамилия французская.

Из Numerical Recipes:

Boris Nikolaevich Delone (1890–1980), a Russian mathematician also celebrated as a rock climber, first published the ideas behind Delaunay triangulation in 1934. Since his paper was written in French, his name was transliterated so as to be pronounced (approximately) correctly by French speakers. A better English pronunciation might be “dyeh-LOAN-yeh.”

Все правильно, я терминологию из уроков геометрии успел подзабыть. Вот я описывал для чего это нужно. Подумав, я понял, как облегчить себе задачу. Если немного доработать программу, то в массиве уже будут не все точки вразброс, а целые куски (сегменты) внешнего контура. Но они будут идти не в нужной последовательности. Отдельные сегменты сортировать легче, и будет их не много. Методами, которые советовали выше, я нахожу дырки контуре за первый проход по массиву. За второй — определяю потерянные сегменты и нахожу для каждого его место.

На выходе у тебя именно перемешанный контур (@_@), или область точек тоже есть?

Может быть кто подскажет, как их отсортировать?

Ласло М. Вычислительная геометрия и компьютерная графика на C++
5.2.2. Стр.135. Построение звёздчатого полигона - starPoligon. На выходе - отсортированный массив точек полигона.

Погоди.. элементарная же задача. Берешь произвольную точку (они у тебя все контурные остались). ищешь точку слева/справа/сверху/снизу нее, как найдешь, она - следующая, ищешь точку слева/справа/сверху/снизу нее ... когда контур замкнется, переходишь к следующей необработанной произвольной точке. Сделай двумерный ассоциативный массив point[x][y]=true. Начиная новый контур запомни первую точку и жди пока не придешь к ней снова. Сделай также одномерный массив [[x1,y1],[x2,y2]...], из которого будешь удалять элементы соответствующие точкам, которые уже обработал - чтобы не искать следующую точку после того как контур замкнется, а просто взять первую из массива. Никакой математики, простая проверка наличия элемента в двумерном (ассоциативном) массиве.

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

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

1) Ищем для каждой точки две ближайшие.

2) проверяем связность, если у точки a ближайшая точка b, и у точки b одна из двух ближайших a, сцепляем их и получаем элемент контура.

3) Иначе выкидываем из соседей ту точку до которой связь дальше и ищем следующую по близости.

Есть и область точек, тоже местами перемешанных.

Т.е. именно с упорядовачиванием контура вообще нет каких-либо проблем, другое дело, что контуров будет много, например:

********
*    * *
*    ***
******
Контуров ты можешь найти
раз
******
*    *
*    *
******
два
      ***
      * *
      ***

три
********
*      *
*    ***
******

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

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

твоя задача не имеет решения, остортируй:

1      2
     3     4
6       5

это может быть как: 1-2-3-4-5-6 так и 1-2-4-3-5-6. С введением доп условий уже можно начинать её рассматривать.

можешь конечно построить выпуклую оболочку для всех точек, а потом пытаться «встраивать» точки в фигуру, т.е. напр. находить точку минимально отстоящую от границы и встраивать её в эту границу, т.е. была граница A,B нашли и к ней подошла точка C, тогда делаешь A,C,B. и т.д. продолжаешь пока есть точки вне фигуры: получишь один из непересекающихся контуров.

замечательного русского учёного Делоне обзывать всякими французскими именами.

Звиняй: уж больно фамилия французская.

<off>А немцы страшно возмущаются, когда их пОрше называют на французский манер поршЕ.</off>

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

А что это за такой алгоритм монте карло для нахождения контура?

\frac{1}{N}\sum_{i=1}{N} (\vec\i\cdot x_i + \vec\j\cdot y_i)

для быстрого отображения попробовал это. Работает. И опечатку видно:

- \sum_{i=1}{N}
+ \sum_{i=1}^{N}