Лян-Барский алгоритмі - Liang–Barsky algorithm - Wikipedia

Жылы компьютерлік графика, Лян-Барский алгоритмі (атымен Сіз-Донг Лян және Барский Брайан ) Бұл сызықты қиып алу алгоритм. Лян-Барский алгоритмі түзудің параметрлік теңдеуін және қиылысу терезесінің диапазонын сипаттайтын теңсіздіктерді түзу мен қиылысуды анықтайды клип терезесі. Осы қиылыстармен сызықтың қай бөлігін салу керек екенін біледі. Бұл алгоритм қарағанда тиімді Коэн-Сазерленд. Лян-Барский кесу алгоритмінің идеясы сызық қиылыстарын есептеудің алдында мүмкіндігінше көп тестілеуден өткізу.

Алдымен түзудің әдеттегі параметрлік түрін қарастырыңыз:

Нүкте клип терезесінде, егер болса

және

оны 4 теңсіздік түрінде көрсетуге болады

қайда

Соңғы жол сегментін есептеу үшін:

  1. Қиып алу терезесінің шетіне параллель сызық бар сол шекара үшін.
  2. Егер сол үшін болса , , содан кейін сызық толығымен сыртта болады және оны жоюға болады.
  3. Қашан , сызық сырттан клип терезесінің ішінен және қашан өтеді , сызық ішінен сыртқа қарай жалғасады.
  4. Нөлдік емес үшін , қиылысу нүктесін береді.
  5. Әр жол үшін есептеңіз және . Үшін , ол үшін шекараларды қараңыз (яғни сырттан ішке). Ал арасында ең үлкені болу . Үшін , ол үшін шекараларды қараңыз (яғни ішінен сыртқа). Ал минимум болуы керек . Егер , сызық сыртта, сондықтан қабылданбайды.
// Лян - Барский жолын кесу алгоритмі# қосу<iostream># қосу<graphics.h># қосу<math.h>қолдану аттар кеңістігі std;// бұл функция максимумды бередіжүзу максимум(жүзу arr[],int n) {  жүзу м = 0;  үшін (int мен = 0; мен < n; ++мен)    егер (м < arr[мен])      м = arr[мен];  қайту м;}// бұл функция минимумды бередіжүзу мини(жүзу arr[], int n) {  жүзу м = 1;  үшін (int мен = 0; мен < n; ++мен)    егер (м > arr[мен])      м = arr[мен];  қайту м;}жарамсыз liang_barsky_clipper(жүзу xmin, жүзу ymin, жүзу xmax, жүзу ymax,                          жүзу x1, жүзу y1, жүзу x2, жүзу y2) {  // айнымалыларды анықтау  жүзу p1 = -(x2 - x1);  жүзу p2 = -p1;  жүзу p3 = -(y2 - y1);  жүзу p4 = -p3;  жүзу q1 = x1 - xmin;  жүзу q2 = xmax - x1;  жүзу q3 = y1 - ymin;  жүзу q4 = ymax - y1;  жүзу posarr[5], негарр[5];  int артқы = 1, жоққа шығару = 1;  posarr[0] = 1;  негарр[0] = 0;  тіктөртбұрыш(xmin, ymin, xmax, ymax); // кесу терезесін салу  егер ((p1 == 0 && q1 < 0) || (p2 == 0 && q2 < 0) || (p3 == 0 && q3 < 0) || (p4 == 0 && q4 < 0)) {      outtextxy(80, 80, «Сызық қию терезесіне параллель!»);      қайту;  }  егер (p1 != 0) {    жүзу r1 = q1 / p1;    жүзу r2 = q2 / p2;    егер (p1 < 0) {      негарр[жоққа шығару++] = r1; // теріс р1 үшін оны теріс жиымға қосыңыз      posarr[артқы++] = r2; // және оң массивке p2 қосыңыз    } басқа {      негарр[жоққа шығару++] = r2;      posarr[артқы++] = r1;    }  }  егер (p3 != 0) {    жүзу r3 = q3 / p3;    жүзу r4 = q4 / p4;    егер (p3 < 0) {      негарр[жоққа шығару++] = r3;      posarr[артқы++] = r4;    } басқа {      негарр[жоққа шығару++] = r4;      posarr[артқы++] = r3;    }  }  жүзу xn1, yn1, xn2, yn2;  жүзу rn1, rn2;  rn1 = максимум(негарр, жоққа шығару); // теріс жиымның максимумы  rn2 = мини(posarr, артқы); // оң массивтің минимумы  егер (rn1 > rn2)  { // қабылдамау    outtextxy(80, 80, «Жол кесу терезесінің сыртында!»);    қайту;  }  xn1 = x1 + p2 * rn1;  yn1 = y1 + p4 * rn1; // жаңа ұпайларды есептеу  xn2 = x1 + p2 * rn2;  yn2 = y1 + p4 * rn2;  бояу(КИАН);  түзу(xn1, yn1, xn2, yn2); // жаңа жолды салу  setlinestyle(1, 1, 0);  түзу(x1, y1, xn1, yn1);  түзу(x2, y2, xn2, yn2);}int негізгі() {  cout << " nЛян-барский сызығы »;  cout << " nЖүйе терезесінің шығысы: (0,0) төменгі сол жақта және (631, 467) оң жақта «;  cout << " nТерезенің координаттарын енгізіңіз (wxmin, wxmax, wymin, wymax): «;  жүзу xmin, xmax, ymin, ymax;  cin >> xmin >> ymin >> xmax >> ymax;  cout << " n(X1, y1) және (x2, y2) жолдарының соңғы нүктелерін енгізіңіз: «;  жүзу x1, y1, x2, y2;  cin >> x1 >> y1 >> x2 >> y2;  int gd = АЙҚЫНДАУ, gm;  // C ++ үшін winbgim кітапханасын пайдалану, графикалық режимді инициализациялау  инитограф(&gd, &gm, "");  liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);  гетч();  жақын граф();}

Сондай-ақ қараңыз

Сол мақсатта қолданылатын алгоритмдер:

Әдебиеттер тізімі

Сыртқы сілтемелер