Алгоритм Коена — Сазерленда
(Перенаправлено з Алгоритм Коена-Сазерленда)
Алгоритм Коена — Сазерленда (англ. Cohen-Sutherland algorithm) — алгоритм відсікання відрізків, тобто алгоритм, який дозволяє визначити частину відрізка, яка перетинає прямокутник. Був розроблений Деном Коеном[en] і Айвеном Сазерлендом у Гарварді в 1966–1968 рр., І опублікований на конференції AFIPS в 1968 .[1][2]
Опис алгоритму[ред. | ред. код]
Алгоритм поділяє площину на 9 частин прямими, які утворюють сторони прямокутника. Кожній з 9 частин присвоюється чотирьохбітний код. Біти (від молодшого до старшого) означають «лівіше», «правіше», «нижче», «вище». Іншими словами, у тих трьох частин площини, які зліва від прямокутника, молодший біт дорівнює 1, і так далі.
Алгоритм визначає код кінців відрізка. Якщо обидва коди дорівнюють нулю, то відрізок повністю знаходиться в прямокутнику. Якщо бітове "І" кодів не дорівнює нулю, то відрізок не перетинає прямокутник (так як це означає, що обидві кінців відрізка знаходяться з однієї сторони прямокутника). В інших випадках, алгоритм вибирає кінець, що знаходиться поза прямокутником, знаходить найближчу до неї точку перетину відрізка з однієї з ліній, що утворює сторони прямокутника, і використовує цю точку перетину як новий кінець відрізка. Укорочений відрізок знову пропускається через алгоритм.
Реалізації[ред. | ред. код]
Реалізація на мові С для двовимірної моделі.
#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 */
else if (code & TOP) {
c->x += (a->x - b->x) * (r->y_min - c->y) / (a->y - b->y);
c->y = r->y_min;
} else if (code & BOT) {
c->x += (a->x - b->x) * (r->y_max - c->y) / (a->y - b->y);
c->y = r->y_max;
}
/* оновлюємо код */
if (code == code_a) {
a = c;
code_a = vcode(r,a);
} else {
b = c;
code_b = vcode(r,b);
}
}
/* коди рівні 0, отже обидві точки в прямокутнику */
return 0;
}
Реалізація мовою C++ для тривимірної моделі.
# define BOTTOM 1 // 00 000001
# define LEFT 2 // 00 000010
# define TOP 4 // 00 000100
# define RIGHT 8 // 00 001000
# define BACK 16 // 00 010000
# define FRONT 32 // 00 100000
typedef struct Area {
float xlt, ylt, zlt; // Координати лівого верхнього кута ближньої грані
float xrb, yrb, zrb; // Координати правого нижнього кута дальньої грані
} Area;
int GetCode ( const float point[1][4], const Area &anArea ) {
int code = 0;
if (point [0] [1]> anArea.ylt) // Точка вище області відсікання
code | = TOP;
else if (point [0] [1] <anArea.yrb) // Точка нижче області відсікання
code | = BOTTOM;
if (point [0] [0]> anArea.xrb) // Точка правіше області відсікання
code | = RIGHT;
else if (point [0] [0] <anArea.xlt) // Точка лівіше області відсікання
code | = LEFT;
if (point [0] [2] <anArea.zlt) // Точка перед областю відсікання
code | = FRONT;
else if (point [0] [2]> anArea.zrb) // Точка за областю відсікання
code | = BACK;
return code;
}
// Тривимірне відсікання методом Коена-Сазерленда.
// Beg - координати початку відрізка [xn, yn, zn, 1]
// End - координати кінця відрізка [xk, yk, zk, 1]
// AnArea - координати області, яка відтинає
void CS_Clip (const float beg [1] [4], const float end [1] [4], const Area & anArea)
{
// Коди кінців відрізка
int outcode0 = 0, outcode1 = 0, outcodeOut = 0;
char codes[2][7] = {"000000","000000"};
float temp[2][1][4];
// Прапор видимості і прапор завершення відсікання
bool accept = false, done = false;
outcode0 = GetCode (beg, codes [0], anArea); // Обчислюємо початкові коди кінців відрізка
outcode1 = GetCode( end, codes[1],anArea );
do
{
float x, y, z;
if (! (outcode0 | outcode1)) {// Відрізок повністю видимий
accept = true;
done = true;
}
else if (outcode0 & outcode1) // Відрізок повністю невидимий
done = true;
else {// Відрізок частково видимий. Обчислення точок перетину відрізка та області відсікання
outcodeOut = outcode0 ? outcode0: outcode1;
if( outcodeOut & TOP ) {
x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.ylt-beg[0][1])/(end[0][1]-beg[0][1]);
z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.ylt-beg[0][1])/(end[0][1]-beg[0][1]);
y = anArea.ylt;
}
else if( outcodeOut & BOTTOM ) {
x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.yrb-beg[0][1])/(end[0][1]-beg[0][1]);
z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.yrb-beg[0][1])/(end[0][1]-beg[0][1]);
y = anArea.yrb;
}
else if( outcodeOut & RIGHT ) {
y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.xrb-beg[0][0])/(end[0][0]-beg[0][0]);
z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.xrb-beg[0][0])/(end[0][0]-beg[0][0]);
x = anArea.xrb;
}
else if( outcodeOut & LEFT ) {
y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.xlt-beg[0][0])/(end[0][0]-beg[0][0]);
z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.xlt-beg[0][0])/(end[0][0]-beg[0][0]);
x = anArea.xlt;
}
else if( outcodeOut & FRONT ) {
x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.zlt-beg[0][2])/(end[0][2]-beg[0][2]);
y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.zlt-beg[0][2])/(end[0][2]-beg[0][2]);
z = anArea.zrb;
}
else if( outcodeOut & BACK ) {
x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.zrb-beg[0][2])/(end[0][2]-beg[0][2]);
y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.zrb-beg[0][2])/(end[0][2]-beg[0][2]);
z = anArea.zlt;
}
if ( outcodeOut == outcode0 ) {
temp[0][0][0] = x;
temp[0][0][1] = y;
temp[0][0][2] = z;
outcode0 = GetCode( temp[0],codes[0],anArea );
}
else {
temp[1][0][0] = x;
temp[1][0][1] = y;
temp[1][0][2] = z;
outcode1 = GetCode( temp[1], codes[1],anArea );
}
}
}while ( !done );
if( accept ) { // Відрізок повністю видимий. Відрізок на екран.
LINE(temp[0],temp[1]);
}
}
Примітки[ред. | ред. код]
- ↑ A Critical History of Computer Graphics and Animation. Section 4: Basic and applied research moves the industry (англ.).
- ↑ 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.
Посилання[ред. | ред. код]
- Вільна реалізація[недоступне посилання з серпня 2019] на python
- JavaScript polyline clipping library using Cohen-Sutherland algorithm [Архівовано 18 лютого 2017 у Wayback Machine.]
- Animated JavaScript implementation
- Delphi implementation [Архівовано 21 квітня 2017 у Wayback Machine.]