8.6. БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
Заполнение области между сторонами многоугольника является, вероятно, первым из предложенных и наиболее широко используемым в машинной графике алгоритмом заполнения. Совершенно очевидно, что им целесообразно пользоваться при решении тех прикладных задач, в которых один и тот же контур приходится воспроизводить многократно, как, например, в фотонаборе. Еще одной прикладной областью, в которой уместно применение метода заполнения между сторонами многоугольника, является
плоская мультипликация (синтез на ЭВМ двухмерных динамических изображений), в которой контуры могут переноситься, но не поворачиваться. Алгоритм 8.1 представляет собой вариант алгоритма YX, описанного в монографии [1.4] и модифицированного на основе анализа работы алгоритмов, используемых в фотонаборных устройствах. Большая часть «усилий» этих алгоритмов затрачивается на получение адекватного кодового представления контура. Их применение может оказаться чрезвычайно неэффективным при решении таких прикладных задач, в которых некоторый заданный контур будет заполняться очень небольшое число раз. В этих случаях, особенно при работе на растровых графических устройствах, лучше пользоваться алгоритмами заполнения области на основе анализа значений пикселов. Отказ от аналоговой топологической информации, характеризующей контур, не может пройти бесследно, хотя при решении некоторых прикладных задач эта информация всегда остается недоступной. Ряд работ посвящен методам решения данной задачи в случаях, когда контур задается в виде некоторого набора неупорядоченных пикселов В статьях [81, 83, 8.4] предлагаются модифицированные варианты заполнения на основе критерия четности. В последней работе описано обобщение алгоритма 8.3, позволяющее корректно осуществлять заполнение неполных областей при условии, что не существует пикселов, через которые проходит более двух дуг контура либо проходят две дуги контура, одна из которых содержит экстремум по координате у. Алгоритмы заполнения по критерию связности описаны в работах [6.10, 82, 8.5]. Алгоритм, представленный в работе (8.2], не обладает корректностью, что и было отмечено в работе [6.10], в которой изложен корректный алгоритм, реализующий, в сущности, обход В-ГСС.
8.7. ЗАДАЧИ
(см. скан)
