Поиск контрастных цветов [расстояние до точки, как мера контраста]

Перебрать 8 вершин - не так уж накладно. Можно и другой метрикой воспользоваться, кстати.

Есть группа точек внутри куба, как найти точку максимально удаленную от них?

точку на поверхности куба надо искать?

Смутные воспоминания о задачах оптимизации и численных методах подсказывают слова типа «метод сопряженных градиентов», но не знаю, можно ли ими пользоваться для этого случая.

Перебрать 8 вершин - не так уж накладно. Можно и другой метрикой воспользоваться, кстати.

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

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

как найти точку максимально удаленную от них?

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

Получаем сложность порядка O(N).

кажись тут есть обоснование того, что решение - это одна из вершин.

http://ru.wikipedia.org/wiki/Симплекс-метод

Перебрать 8 вершин - не так уж накладно. Можно и другой метрикой воспользоваться, кстати.

При чем здесь вершины? А если одна из уже существующих точек лежит на вершине?

Вообще так как точки добавляются в куб, то вершины достаточно быстро будут заняты.

Наверное стоило мне описать вообще цель задачи... а то я придумал метод и ищу способ реализации и даже не знаю подходит ли мне метод.

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

Плюс еще интересным кажется поиск оттенков цвета. Есть ли какие-то известные методы? Библы?

Предлагаю заранее ограничить возможные цвета. А потом из цветов, которые заранее известны как контрастные ко всем возможныи выбирать.

А отдельно координаты (р, г, б составляющии) разве нельзя посчитать?

А вообще при совсем случайном выборе цветов часто будет вырвиглазие появляться, может лучше предопределить множество приемлимых?

Переведи в HSV модель, проще будет. Для одного цвета, например, - прямо противоположный на цветовом круге. Для нескольких (навскидку) - найти средний и получить контрастный к нему.

нас уже двое :)

Думал об этом - создать палитру скажем из 1000 цветов и выбирать цвет как crc32 mod 1000.

Но как сгенерить начальную 1000? Опять встает вопрос поиска наиболее контрастных друг к другу цветов. А если брать меньше соответственно получим рост вероятности коллизий.

Симплекс-метод оптимизирует линейную функцию, а у ТС-а - квадратичная.

Симплекс-метод оптимизирует линейную функцию, а у ТС-а - квадратичная.

никто не мешает ТС сделать метрику |.|₁

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

Но как сгенерить начальную 1000? Опять встает вопрос поиска наиболее контрастных друг к другу цветов. А если брать меньше соответственно получим рост вероятности коллизий.

навскидку два варианта:

1) ограничить цветовую палитру. Допустим убрать зеленый.

2) ограничить яркость до 0.5.

3) комбинация из этих двух.

Это приведет только к бедности палитры.

Разве модуль - это линейная функция?

> задача за уши принянута.

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

пока наткнулся только на один лиловый-тошнотик

Есть предложения по тому [как сделать/где взять] такую палитру, кроме подбора руками?

К сожалению, нет. Самому надо подобное в одном проекте сделать, но пока отложил «на потом».

Это приведет только к бедности палитры.

Я так не думаю.

яркость <=0.5 для всех цветов. яркость 1.0 для тех, которые надо выделять.

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

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

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

навряд ли нужен именно куб. Цвет нужно расклаывать в Lab, соответственно светимость (L) сразу отбрасываем т.к. она нерелеванта воспринимаемому констрасту цветов.

Остается некое мн-во в плоскости (a,b), по нему распределены цвета равномерно согласно их восприятию человеческим глазом/мозгом. Вот это самое пр-во можно резать на равномерные квадратики-сэмплы и искать среди них самую удалённую точку от всех.

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

точку на поверхности куба надо искать?

очевидно, что наиболее удаленная точка куба от заданной - одна из его вершин;-)

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

очевидно, что наиболее удаленная точка куба от заданной - одна из его вершин;-)

это совершенно не очевидно.

Если считать расстояние как sqrt((x-x0)**2+(y-y0)**2+(z-z0)**2)? Очевидно же.

Если считать расстояние как sqrt((x-x0)**2+(y-y0)**2+(z-z0)**2)? Очевидно же.

вообще не очевидно. Причем я не знаю даже так ли это.

Ааа, лол. Так мы же о множестве точек, а не одной единственной говорим.

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

Ну или попробуйте описать сферу так, что бы ее центр совпадал с заданной точкой, а куб касался сферы. Угадайте с трех раз, какой точкой (точками) куб коснется ОПИСАННОЙ сферы?;-)

Так мы же о множестве точек, а не одной единственной говорим.

И чего? Вам надо максимизировать выражение sqrt((x-x0)**2+(y-y0)**2+(z-z0)**2), так? При этом все (x, y, z) принадлежат кубу.

И чего? Вам надо максимизировать выражение sqrt((x-x0)**2+(y-y0)**2+(z-z0)**2), так? При этом все (x, y, z) принадлежат кубу.

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

яркость <=0.5 для всех цветов. яркость 1.0 для тех, которые надо выделять.

А, вот оно что. Да - это логично и просто. Но встал еще и вопрос о поиске первой тысячи.

яркость <=0.5 для всех цветов. яркость 1.0 для тех, которые надо выделять.

А, вот оно что. Да - это логично и просто. Но встал еще и вопрос о поиске первой тысячи.

ты не сделаешь 1000 цветов так, чтобы они сильно отличались между собой. Поэтому на данный вопрос можно смело забить, брать последние 3 байта из хеша и делить каждый из них на два.

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

Тьфу... я туплю, виноват, у ТС-а группа точек. Ну чего, тогда наверное надо гуглить «сетки воронова». Исходные точки являются центрами ячеек, искомая точка будет лежать на границе ячеек, в узле. Понятно что решений будет много... и в 3D эта задача весьма нетривиальна, я бы взял какую нить готовую библиотеку, если они есть.

В том-то и дело, что найти готового решения не смог.

Однако вот что нашлось, с подачи mashina: http://ru.wikipedia.org/wiki/Формула_цветового_отличия

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

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

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

Вот Вам например «радужная» одномерная палитра http://a-iv.ru/trash/rainbow_pal.png

и вот координаты узлов ломаной в RGB пр-ве:

(0,0,0), (1,0,0), (1,.5,0), (1,1,0), (0,1,0), (0,1,1), (0,0,1), (1,0,1), (1,1,1)

считается что сторона RGB куба 1, всего 9 точек, т.е. 8 отрезков, берем чиселку, шкалируем, смотрим на какой отрезок она попала, смотрим гжде она на отрезке, высчитываем цвет.

Ты случаем отвечает не на то сообщение где я привожу ссылку на поиск цветов в пространстве Lab? Не?

<...> считается что сторона RGB куба 1, всего 9 точек, т.е. 8 отрезков, берем чиселку, шкалируем, смотрим на какой отрезок она попала, смотрим гжде она на отрезке, высчитываем цвет.

и как он будет выберать дополнительные цвета из этого отрезка? У вас явно решение какой-то другой задачи.

Если опираться на цветовую модель HSV, то, вследствие её нелинейного восприятия, далеко не все цвета будут заметно различаться. Так, пространство H (при S=100%, V=100%) можно разделить на 24 цвета: 0, 30, 45, 53, 60, 67, 75, 90, 120, 150, 165, 173, 180, 187, 195, 210, 240, 270, 285, 293, 300, 307, 315, 330 (http://ompldr.org/vZGUwbQ/spectrum-24.png).

При уменьшении S или V количество различимых оттенков становится меньше. При S=0 цвета сводятся к серой гамме, при V=0 - к чисто чёрному цвету. Квантование V разумно принять как 0, 50, 75, 100%. Квантование S положим 0, 25, 50, 75, 100%.

Итак, считаем. При S=0 пусть будет 5 оттенков (добавим V=25%), при S=25..100% — 4*3*24 = 288 оттенков. Итого: 293 оттенка.

Сомневаюсь, что на реальной диаграмме можно различить даже такое количество цветов (и объектов), незначительное, по сравнению с 16 млн цветов режима True Color.

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

Зачем. mashina правильно сказал - задачу нужно решать специальными средствами. А в данном случае это указанное пространство Lab и еще можно LCH.

Я уже написал функции перехода от RGB к Lab (и обратно на всякий случай). И реализовал CIE76 и CIE94 для Lab (в CIE94 перехожу от Lab прямо к LCH не используя внешнюю функцию пока) и их же для html цветов. Есть правда подозрение что в вычислении CIE94 ошибка... CIE2000 лениво делать, тем более что, как я понял, он не намного лучше CIE94.

Теперь нужно придумать как быстро выбирать цвет с максимальным E по CIE#...

Теперь нужно придумать как быстро выбирать цвет с максимальным E по CIE#...

Очень быстро, наверное, никак. Самое простое и не мозголомкое - сэмплирование пространства на заданное колво точек и просчёт для них расстояний + выборка наиболее подходящих.

Это практически тоже самое, что и использование заранее заданной палитры и поиск в ней максимально отдалённых цветов.

Уже догадался. Но хотя бы поиск контрастного цвета к одному легко выполняется. Причем контрастного в реале, а не в RGB.

Вот только че-то недогоняю - у меня после рабочего дня вообще мозги не варят или ветер не дует - разве это обратные преобразования:

http://www.brucelindbloom.com/index.html?Equations.html

set a [expr {cos($Hv) * $Cv}]
set b [expr {sin($Hv) * $Cv}]

    set H [expr {atan2($bv, $av)}]
    if {$H < 0} {
      set H [expr {360 + $H}]
    } elseif {$H >= 360} {
      set H [expr {$H - 360}]
    }
    set C [expr {sqrt($av*$av + $bv*$bv)}]