Режим машинной обработки и вывода данных, при котором значительная часть выводимой информации имеет графический вид. В режиме графического вывода отображается самая различная информация от простых гистограмм и других графиков до сложных карт и технических чертежей. Среди задач К.г. - задачи: отсечения (clipping) - отсечение геометрических объектов по границам определенной области, например, при отображении или обновлении информации; если область является прямоугольником, то ее называют прямоугольником отсечения (clip rectangle); видимости (visibility problem) или построения множества всех точек, из которых видны все вершины простого многоугольника; освещенности (illumination) или построения множества точек на поверхности, которые видны (освещаются) из данной точки пространства; построения выпуклой оболочки (construction of convex hull), построения многоугольника, являющегося выпуклой оболочкой конечного множества точек на плоскости или невыпуклого многоугольника; локализации точки (point-location) - нахождение ответа на вопросы: принадлежит ли заданная точка заданному множеству или какому из заданного набора непересекающихся множеств принадлежит заданная точка; о максимумах множества точек (maximal of a point set) - определение точек имеющих экстремальные значения по одной из координат. Для плоскости самой левой, самой правой, самой верхней и самой нижней точек. В компьютерной графике существует ряд методов решения перечисленных задач, среди которых метод сканирования на плоскости или заметания плоскости (plane-sweep technique). В этом методе воображаемая вертикальная линия сканирования перемещается слева направо, пересекая геометрические объекты. В процессе обработки решаются задачи, относящиеся только к частям объектов, лежащим слева от линии сканирования. Когда линия сканирования перемещается достаточно далеко, то вся задача оказывается решенной. Например, при нахождении всех точек пересечения конечного множества отрезков на плоскости, последнюю можно разбить вертикальными прямыми, проходящими через концы всех отрезков, на полосы, внутри которых лежат точки пересечения тех отрезков, которые пересекают эти полосы; метод полос (slab method) - метод решения задачи локализации точки, при котором плоский прямолинейный граф разбивается на трапеции проведением горизонтальных линий через все его вершины. В каждой полосе трапеции можно упорядочить вдоль горизонтальной оси. Метод полос является частным случаем метода заметания.
RSS
Реклама
