Нужен алгоритм разбиения _растровой_ фигуры на выпукл части

[ori]

Добрый день!

Нужен алгоритм разбиения растровой фигуры на выпуклые части.

Буду рад любой информации - собственно алгоритму, его названию, имени автора или ссылке.

PS как это сделать для векторной фигуры, я знаю. Но не хочется делать преобразования растр --> вектор --> разбиение --> растр. Может быть, есть решение для растра?

Если вопрос не в тему - подскажите, пожалуйста, куда его переместить.

С уважением - ori

[PAV]

Переношу из математического раздела в CS

Мне кажется, что задачу следует как-то уточнить. Всегда ведь можно разбить растровое изображение на горизонтальные или вертикальные интервалы (или даже на отдельные пиксели), которые выпуклые.

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

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

Добавлено спустя 53 минуты 59 секунд:

Попробуйте заглянуть в известную книгу Павлидис Т. — Алгоритмы машинной графики и обработки изображений, глава 8 "заполнение контура". Это вроде близко к теме.

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