7.6.1. СЛУЧАЙ МНОЖЕСТВА ПИКСЕЛОВ, НЕ ЯВЛЯЮЩЕГОСЯ КРИВОЙ

Прежде чем перейти к определению тонких областей, определим противоположное понятие.

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

На рис. 7.15, а представлен пример полной области, который, в частности, показывает, что в полную область входят пикселы, расположенные за пределами ее контура. (Это было невозможно, если бы не было предусмотрено условие относительно четырех пикселов.) С топологической точки зрения полная область соответствует открытому множеству.

Грубо говоря, область является полной, если сетка дискретизации достаточно «точна» для того, чтобы ни одна из границ не раздваивалась Условие н-связности является существенным в

Рис. 7.15. Иллюстрации к определению 7.6: а — полная область; б — неоднозначность при построении контура, возникающая в результате исключения условия н-связности

том отношении, что позволяет избежать возникновения неоднозначных ситуаций, типа представленной на рис. 7.15, б. Это свойство оказывается полезным в случаях, когда желательно, чтобы форма контура отражала форму объекта. Заполнение таких контуров, кроме того, можно осуществлять с помощью какого-либо простого алгоритма (см разд. 8.3) и, следовательно, указанное свойство имеет существенное значение для машинной графики. Сформулируем достаточное условие, гарантирующее получение исключительно полных областей.

Теорема 7.2. Если диаметр окружности, упоминаемой в определении совместимости, равен а не то всё множества пикселов, получаемые в результате дискретизации, являются полными

Доказательство. На рис 7.16 представлена наименьшая область, удовлетворяющая условиям данной теоремы, очевидно, что она содержит по меньшей мере, девять пикселов, которые образуют полную область. Области с большими размерами можно представить как объединения таких областей и, следовательно, при их дискретизации также могут быть получены полные множества пикселов. Если — радиус окружности, то

Практическое значение теоремы 7.2 состоит в том, что с ее помощью можно определить размеры элемента сетки дискретизации, и, следовательно, дискретизацию любого заданного набора двухуровневых изображений можно осуществлять таким образом, чтобы в результате получались исключительно полные области. Пусть — диаметр наименьшей вписанной окружности, удовлетворяющей условиям определения 7.4. В таком случае значение следует выбирать меньшим или равным . С другой стороны, если бы нашей целью было лишь сохранение формы, то значение можно было бы выбрать меньшим или равным

Рис. 7.16. (см. скан) Иллюстрации к доказательству теоремы 7.2: а — область, ширина которой меньше имеет пустую внутреннюю часть, — область с минимальной шириной имеет непустую внутреннюю часть, в — область с шириной имеет непустую внутреннюю часть независимо от расположения сетки дискретизации

Отношение двух этих размеров сетки дискретизации равно Следовательно, для дискретизации, обеспечивающей получение только полных областей, требуется в пять раз больше выборочных точек, чем для дискретизации, при которой не все области оказываются полными. В большинстве прикладных задач пятикратное увеличение необходимого объема памяти и соответственное увеличение времени обработки оказывается слишком дорогим удовольствием. Единственным важным исключением служит машинная графика, в которой высокое разрешение может потребоваться по эстетическим соображениям. Однако даже в машинной графике может возникнуть необходимость работать с областями, которые не являются полными. Мы же используем отсутствие полноты для определения линий и кривых на некоторой дискретной сетке.