Быстрая сортировка массива объектов на основе их известного сходства друг с другом с помощью C

Question

У меня есть произвольно упорядоченный массив C целых чисел.

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

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

Какой лучший способ сделать это?

Answer 1

Во-первых, я предполагаю, что вы собираетесь использовать функцию qsort или аналогичную для сортировки, и вам нужна функция сравнения, чтобы перейти к ней.Эти функции сравнения ведут себя как memcnp и strcmp - возвращая целое число для обозначения меньше, равно или больше чем.

Один из способов сделать это - обработать все значение цвета как одно большоечисло для сравнения:

int bright_hue_compare(const void * a, const void * b) {
    int rc = bright_compare(a, b);
    if (!rc) {
        rc = hue_compare(a, b);
    }
    return rc;
}

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

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

int bright_hue_inverse_compare(const void * a, const void * b) {
    int rc = bright_hue_compare(a, b);
    if (rc) {
       return 0;
    }
    return random(); // so that they are the same so randomize greater/lesser
}

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

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

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

Answer 2

Вы можете попробовать преобразовать свой цвет из цветового пространства HSL (я полагаю, вы используете его, так как вы упомянули оттенок и яркость) в CIELAB. В цветовом пространстве CIELAB вы можете легко вычислить сходство цветов, как его воспринимает человеческий глаз. Рассчитав это расстояние, вы сможете отсортировать цвета.

Answer 3

Один из способов - начать с выбора объекта, а затем выполнить поиск оставшихся объектов с помощью вашей метрической функции, чтобы найти ближайший / самый дальний объект. Повторите это для каждого объекта, который вы добавляете в список вывода. Алгоритм O(n^2), что не так уж и плохо.

Answer 4

PMG прав в своем комментарии.Исходя из того, что вы сказали, нет причин не использовать быструю сортировку с функцией сравнения клиентов.Посмотрите ссылку, которую PMG разместил в своем комментарии для получения дополнительной информации, и убедитесь, что ваша функция сравнения (int (*compar)(const void *, const void *)) делает магию для вас.