Сортировка массива точек эффективно в C?

Мне нужно отсортировать точечный массив (точка - это структура с двумя типами float - одна для x и одна для y) особым образом.

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

Illustration

Мне нужно это, чтобы иметь возможность конвертировать произвольные многоугольники в массивы с треугольными полосами, которые затем можно использовать с помощью GLes. Каким будет наиболее эффективный способ сортировки этих точек, используя либо указатели (т.е. передавая и переставляя указатели на точечные структуры), либо напрямую копируя и перемещая данные в структурах?

Ответы

Ответ 1

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

Кажется (судя по вашим другим вопросам), что вы в конечном счете ищете триангуляцию. И, вполне возможно, триангуляция многоугольника или многоугольников (в отличие от множества независимых точек). Если это так, я бы предложил вам взглянуть на некоторые основные алгоритмы триангуляции, например, на основе монотонного разложения. Проблема, которую вы здесь представляете, на самом деле выглядит как попытка (возможно, ошибочная) сделать что-то подобное монотонному разложению.

Ответ 2

Я бы использовал qsort() с пользовательской функцией compare(), которую, как отмечал @stefan, сортирует по убыванию, затем чередует (max/min) для x.

Ответ 3

Я настоятельно рекомендую вам использовать Треугольник Delaunay. OpenCV (доступно на C) имеет приятную реализацию.

Ответ 4

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

*

         *
                 *
*
    *
    *

Ответ 5

Я бы рекомендовал напрямую перемещать данные из структур.

Размер точечной структуры составляет от 8 до 16 байт (16 байтов, если float равен 8 байтам). Если вы сортируете массив через указатели, вы копируете почти такой же объем данных (или такой же объем данных, если float имеет 4 байта и 8 байтов указателя на 64-битной системе).

Я бы рекомендовал сортировать по указателю, если структура большая.

Ответ 6

Кажется, вы пытаетесь изобрести какую-то монотонную многоугольную цепочку. Некоторые методы триангуляции многоугольников кратко описаны в wiki и здесь со ссылками на код

Ответ 7

Сначала вы должны найти среднее (среднее значение) точек (на основе горизонтальных значений). Это разделит набор точек налево и вправо. Затем соберите 2 набора на основе значения по вертикали. Затем вы можете просто перебирать вершину из каждого набора: взять верхний элемент из левого набора, затем верхний элемент справа.. и т.д.

Чтобы найти медиану, существует короткий алгоритм, основанный на быстрой сортировке. Но быстрее, чем быстро сортировать. Просто рекурсия со стороны, где медиана (не на обоих, как в быстрой сортировке).

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