7.6. КРИВЫЕ И ЛИНИИ НА ДИСКРЕТНОЙ СЕТКЕ

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

кривой или некоторой целой области. Кроме того, евклидово определение прямой как кратчайшего расстояния между двумя точками теряет смысл при определении расстояния на сетке. В примере, приведенном на рис. 7.13, представлены два к-маршрута между точками А и В, каждый из которых состоит из шести пикселов.

Рис. 7.13 Иллюстрация неединственности кратчайшего пути между двумя точками на дискретной сетке. Пикселы, образующие первый маршрут, обозначены единицами; пикселы, образующие второй маршрут, — двойками; пикселы, обозначенные тройками, принадлежат обоим маршрутам

Рис. 7.14. Пикселы линии, связывающей точки 0 и 7, снабжены числовыми метками, а пикселы, образующие линию помечены строчными буквами; пикселы, снабженные двумя метками, входят одновременно в обе линии

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

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

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

точка пересечения с вертикальной линией и нам необходимо выкрасить все отрезки прямых, расположенные слева от в зеленый цвет. В результате получим несколько зеленых пикселов (от а до ), а также один красный пиксел (3) слева от вертикали

Наличие сообразного определения для тонких линий представляет также интерес с точки зрения таких задач, как заполнение контура (см. гл. 8) и прореживание области (см. гл. 9). Решение обеих задач предполагает реализацию геометрических операций на дискретной сетке. Ниже мы введем критерий, позволяющий различать тонкие кривые и толстые области. Затем кратко обсудим способы, облегчающие решение геометрических задач.