Преобразовать растровое изображение в многоугольник - (обратное растрирование)

Question

Учитывая растровое изображение с несколькими пятнами сплошного цвета, какой алгоритм вы бы использовали для построения полигонов той же формы, что и пятна?

Это можно сделать в несколько этапов: многоугольник с высоким разрешением может быть впоследствии сокращен с помощью алгоритма наилучшего соответствия. Бонусные баллы, если вы можете сказать мне, как разрезать получившиеся полигоны на выпуклые компоненты, чтобы они могли без проблем отображаться в OpenGL.

Answer 1

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

Хорошие алгоритмы разбиения полигонов можно найти в «Вычислительной геометрии в C» Джоспа О'Руркса, ISBN 0-521-44034-3 или по запросу алгоритмы вогнутого разбиения многоугольника , такие как это

Answer 2

Это довольно распространено в ГИС - например, извлечение функций автоматически из аэрофотосъемки. Выбранный инструмент OpenSource:

http://www.gdal.org/gdal_polygonize.html

http://www.gdal.org/gdal__alg_8h1465355355355355h5b5)