Алгоритм Коэна — Сазерленда

Алгоритм Коэна — Сазерленда

Алгоритм Коэна — Сазерленда (англ. Cohen-Sutherland) — алгоритм отсечения отрезков, то есть алгоритм, позволяющий определить часть отрезка, которая пересекает прямоугольник. Был разработан Дэном Коэном и Айвеном Сазерлендом в Гарварде в 1966—1968 гг., и опубликован на конференции AFIPS в 1968.^[1][2]

Описание алгоритма

Алгоритм разделяет плоскость на 9 частей прямыми, которые образуют стороны прямоугольника. Каждой из 9 частей присваивается четырёхбитный код. Биты (от младшего до старшего) значат «левее», «правее», «ниже», «выше». Иными словами, у тех трёх частей плоскости, которые слева от прямоугольника, младший бит равен 1, и так далее.

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

Пример реализации

Пример реализации на языке C:

#define LEFT  1  /* двоичное 0001 */
#define RIGHT 2  /* двоичное 0010 */
#define BOT   4  /* двоичное 0100 */
#define TOP   8  /* двоичное 1000 */
 
/* точка */
struct point {
	double x, y;
};
 
/* прямоугольник */
struct rect {
	double x_min, y_min, x_max, y_max;
};
 
/* вычисление кода точки
   r : указатель на struct rect; p : указатель на struct point */
#define vcode(r, p) \
	((((p)->x < (r)->x_min) ? LEFT : 0)  +  /* +1 если точка левее прямоугольника */ \
	 (((p)->x > (r)->x_max) ? RIGHT : 0) +  /* +2 если точка правее прямоугольника */\
	 (((p)->y < (r)->y_min) ? BOT : 0)   +  /* +4 если точка ниже прямоугольника */  \
	 (((p)->y > (r)->y_max) ? TOP : 0))     /* +8 если точка выше прямоугольника */
 
/* если отрезок ab не пересекает прямоугольник r, функция возвращает -1;
   если отрезок ab пересекает прямоугольник r, функция возвращает 0 и отсекает
   те части отрезка, которые находятся вне прямоугольника */
int cohen_sutherland (const struct rect *r, struct point *a, struct point *b)
{
	int code_a, code_b, code; /* код конечных точек отрезка */
	struct point *c; /* одна из точек */
 
	code_a = vcode(r, a);
	code_b = vcode(r, b);
 
	/* пока одна из точек отрезка вне прямоугольника */
	while (code_a || code_b) {
		/* если обе точки с одной стороны прямоугольника, то отрезок не пересекает прямоугольник */
		if (code_a & code_b)
			return -1;
 
		/* выбираем точку c с ненулевым кодом */
		if (code_a) {
			code = code_a;
			c = a;
		} else {
			code = code_b;
			c = b;
		}
 
		/* если c левее r, то передвигаем c на прямую x = r->x_min
		   если c правее r, то передвигаем c на прямую x = r->x_max */
		if (code & LEFT) {
			c->y += (a->y - b->y) * (r->x_min - c->x) / (a->x - b->x);
			c->x = r->x_min;
		} else if (code & RIGHT) {
			c->y += (a->y - b->y) * (r->x_max - c->x) / (a->x - b->x);
			c->x = r->x_max;
		}
		/* если c ниже r, то передвигаем c на прямую y = r->y_min
		   если c выше r, то передвигаем c на прямую y = r->y_max */
		if (code & BOT) {
			c->x += (a->x - b->x) * (r->y_min - c->y) / (a->y - b->y);
			c->y = r->y_min;
		} else if (code & TOP) {
			c->x += (a->x - b->x) * (r->y_max - c->y) / (a->y - b->y);
			c->y = r->y_max;
		}
 
		/* обновляем код */
		if (code == code_a)
			code_a = vcode(r,a);
		else
			code_b = vcode(r,b);
	}
 
	/* оба кода равны 0, следовательно обе точки в прямоугольнике */
	return 0;
}

Примечания

1. ↑ A Critical History of Computer Graphics and Animation. Section 4: Basic and applied research moves the industry (англ.). Проверено 26 февраля 2009.
2. ↑ Robert F. Sproull, Ivan E. Sutherland A clipping divider // AFIPS Joint Computer Conferences : Proceedings of the December 9-11, 1968, fall joint computer conference. — New York: ACM, 1968. — Т. I. — С. 765—775.

См. также

• Отсечение
• Алгоритм Уайлера — Атертона