Разбиение картинной плоскости

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

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

На этих же принципах основан алгоритм Варнака. Картинная плоскость разбивается на 4 равные части. При этом возможны следующие случаи:

· область пуста (в нее не попадает ни одной проекции), следовательно она закрашивается цветом фона;

· область целиком занята проекцией одной грани, следовательно она закрашивается цветом грани;

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

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

Дата добавления: 2014-01-11