Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari
![C++ dasturlash tili orqali dasturlarni yozish uchun ishlatiladi. Bu tilda yozilgan
dasturlar yoki kodlar bilan kompyuter va boshqa qurilmalar orasida
kommunikatsiya o'rnatish, ilovalarni yaratish va boshqalar kabi bir nechta
vazifalarni bajarish mumkin. C++ oson sintaksisga ega bo'lib, yuqori darajadagi
ulushi va effektiv qollanishi bilan ajralib turadi. Bu yaxshi yonuvchi tili
hisoblanadi, chunki u odatda tezkor va qulay ishlashda yordam beradi.
Planar grafikning tashqi yuzlarini aniqlash uchun foydalaniladigan algoritmlardan
biri, "Tashqi Yuzlarin Aniqlanishi" (Face Culling) algoritmidir. Bu algoritmda,
grafikni belgilangan bir burchak orqali ko'zga ko'rinishida o'zgartirish va
ko'rsatkichlar orqali yaxlitlash va kutlash amaliyotlari bajariladi.
2.3. Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash
algoritmlarini C++ dasturlash tilda ifodalash
Ushbu algoritm dastur kodi bir qator qilib beriladi:
vector<Face> TashqiYuzlarniAniqlash(vector<Face> grafik) {
vector<Face> tashqiYuzlar;
for (int i = 0; i < grafik.size(); i++) {
for (int j = 0; j < grafik.size(); j++) {
if(i!=j&&grafik[i].toshqaQo'yilmagan() && grafik[j].toshqaQo'yilmagan())
{
if (Perpendicular(grafik[i], grafik[j])) {
if (InFront(grafik[i], grafik[j])) {
grafik[i].toshqaQoy();
} else {
14](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_14.png)
![grafik[j].toshqaQoy();
}
}
}
}
}
for (int i = 0; i < grafik.size(); i++) {
if (grafik[i].toshqaQo'yilmagan()) {
tashqiYuzlar.push_back(grafik[i]);
}
}
return tashqiYuzlar;
}
Bu dastur kodi, grafik objektlarining toshqadan qo'yilmaganligini
(toshqaQo'yilmagan()) va ularning perpendikulyar bo'lishini (Perpendicular())
aniqlaydi. Shuningdek, bir yuzning boshqa yuzdan oldin joylashib
joylanmaganligini (InFront()) aniqlaydi. Tashqi yuzlar ro'yxatida aniqlangan Face
obyektlarini saqlab, uni qaytaradi.
15](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_15.png)
![}
// Planar grafik tashqi yuzini topish uchun boshqaruvchi funksiya
vector<Point> convexHull(vector<Point> points, int n) {
if (n < 3)
return vector<Point>(); // Kamida 3 ta nuqta kerak
vector<Point> hull;
// Chapmoqda eng kichik va opoq nuqta
int leftMost = 0;
for (int i = 1; i < n; i++) {
if (points[i].x < points[leftMost].x)
leftMost = i;
else if (points[i].x == points[leftMost].x && points[i].y < points[leftMost].y)
leftMost = i;
}
int current = leftMost, next;
do {
// Nuqtani eng o'lchamli ko'chirish
hull.push_back(points[current]);
next = (current + 1) % n;
for (int i = 0; i < n; i++) {
17](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_17.png)
![// Agar i-nuqta current -> next ya'ni g'ildirakda yoki i-nuqta hull-da emas
bo'lsa
if (orientation(points[current], points[i], points[next]) == 2) {
next = i; // next ni i-ga almashtiramiz
}
}
current = next; // current ni next ga almashtiramiz
} while (current != leftMost); // Chapmoqgacha davom etadi
return hull;
}
// Boshqa funksiyada malumotlarni kiritib, convexHull funksiyasini chaqirib
natijani ekranga chiqaramiz
int main() {
int n;
cout << "Nechta nuqta kiritasiz? ";
cin >> n;
vector<Point> points(n);
cout << "Nuqtalarni kiriting (x, y):\n";
for (int i = 0; i < n; i++) {
18](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_18.png)
![cin >> points[i].x >> points[i].y;
}
vector<Point> convexHullPoints = convexHull(points, n);
cout << "Tashqi yuzdagi (convex hull) nuqtalar:\n";
for (int i = 0; i < convexHullPoints.size(); i++) {
cout << convexHullPoints[i].x << " " << convexHullPoints[i].y << "\n";
}
return 0;
}
Ushbu dastur convex hull (tashqi yuz) problemasini hal qiluvchi Andrew's
monotone chain algoritmini amalga oshiradi. Foydalanuvchi n ta nuqta kiritadi va
dastur tashqi yuzdagi nuqtalarni topadi va chiqaradi. Dastur davomida
foydalanuvchi nuqtalarni x va y koordinatalari bilan kiritadi.
# include <iostream>
# include <vector>
using namespace std;
struct Point {
int x, y;
};
// Nuqtalarni taxlaydigan qavsni teskari bo'lishini tekshirish
bool isClockwise ( const Point& p1, const Point& p2, const Point& p3) {
int result = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
return result < 0 ;
}
// Nuqtalarning tashqi yuzini topish
vector<Point> findConvexHull (vector<Point> points) {
int n = points. size ();
if (n < 3 ) {
19](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_19.png)
![return {};
}
int leftmost = 0 ;
for ( int i = 1 ; i < n; i++) {
if (points[i].x < points[leftmost].x) {
leftmost = i;
}
}
int current = leftmost;
vector<Point> hull;
do {
hull. push_back (points[current]);
int next = (current + 1 ) % n;
for ( int i = 0 ; i < n; i++) {
if ( isClockwise (points[current], points[i], points[next])) {
next = i;
}
}
current = next;
} while (current != leftmost);
return hull;
}
int main () {
vector<Point> points = {
{ 0 , 0 },
{ 1 , 3 },
{ 2 , 1 },
{ 3 , 4 },
{ 5 , 2 },
{ 6 , 3 },
{ 8 , 0 },
{ 9 , 2 }
};
vector<Point> convexHull = findConvexHull (points);
cout << "Tashqi yuz nuqtalari: " ;
for ( const Point& point : convexHull) {
cout << "(" << point.x << ", " << point.y << ") " ;
}
return 0 ;
}
Ushbu kod tashqi yuz nuqtalarini topish algoritmini implement qiladi. Kodda,
`Point` struct'i nuqta koordinatalarini saqlash uchun foydalaniladi. `isClockwise`
funksiya nuqtalarning taxlash tartibini tekshirib, `findConvexHull` funksiya tashqi
20](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_20.png)
![return false;
}
bool isPlanar(Point polygon[], int n) {
if (n < 3) {
return false;
}
for (int i = 0; i < n; i++) {
int next = (i + 1) % n;
for (int j = i + 1; j < n; j++) {
int nextj = (j + 1) % n;
if (doIntersect(polygon[i], polygon[next], polygon[j], polygon[nextj])) {
return false;
}
}
}
return true;
}
int main() {
Point polygon[] = {{0, 0}, {1, 1}, {1, 0}};
int n = sizeof(polygon) / sizeof(polygon[0]);
if (isPlanar(polygon, n)) {
cout << "Bu planar grafik" << endl;
} else {
cout << "Bu planar grafik emas" << endl;
}
return 0;
}
O'zingiz uchun quyidagi C++ kodi yordamida planar grafikning tashqi yuzini
aniqlash algoritmini ko'rishishingiz mumkin:
#include<iostream>
using namespace std;
struct Point {
int x, y;
22](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_22.png)
![int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// umumiy holatda bunday nuqta ifodasi kerak emas
if (o1 != o2 && o3 != o4)
return true;
// Nuqtalar kesishmasa, ular bir-birini tomirlashishiga masalan ekan
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false; // Kesishma yo'q
}
// Planar grafikda hamma yuzlarni tekshirish funksiyasi
bool isPlanar(Point polygon[], int n) {
// Tanlangan kvadrat xususiyatlari uchun barcha burchaklarni tekshiring
24](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_24.png)
![for (int i = 0; i < n; i++) {
Point p1 = polygon[i];
Point p2 = polygon[(i + 1) % n];
// Aeroplan grafikning umumiy holatda qarasida kesishayotgan yuzlarini
tekshirish
for (int j = i + 1; j < n; j++) {
Point q1 = polygon[j];
Point q2 = polygon[(j + 1) % n];
if (doIntersect(p1, p2, q1, q2))
return false; // kesishma mavjud
}
}
return true; // Planar grafik
}
int main() {
25](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_25.png)
![// N ta nuqta to'plami bilan planar grafikni ko'rsatadi
Point polygon[] = { {1, 1}, {3, 1}, {3, 2}, {2, 2}, {2, 3}, {1, 3} };
int n = sizeof(polygon) / sizeof(polygon[0]);
if (isPlanar(polygon, n))
cout << "Bu bir planar grafik" << endl;
else
cout << "Bu bir planar grafik emas" << endl;
return 0;
Ushbu dastur kodida, C++ tilida qushilganida, berilgan nuqtalar massivini
ko'rsatadi. Agar u planar grafik bo'lsa, so'rov natija sifatida "Bu bir planar grafik"
degan natija chiqariladi. Aks holda "Bu bir planar grafik emas" degan xabar
beriladi. Ushbu algoritmda barcha yuzlar zarur ekanligini tekshiriladi, keyinchalik
ular orasidagi kesishishlarni aniqlash uchun qo'llaniladi.
2.4. Dasturni murakkabligini baholash
# include <iostream>
# include <vector>
using namespace std;
struct Point {
int x, y;
};
// Nuqtalarni taxlaydigan qavsni teskari bo'lishini tekshirish
bool isClockwise ( const Point& p1, const Point& p2, const Point& p3) {
int result = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
return result < 0 ;
26](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_26.png)
![}
// Nuqtalarning tashqi yuzini topish
vector<Point> findConvexHull (vector<Point> points) {
int n = points. size ();
if (n < 3 ) {
return {};
}
int leftmost = 0 ;
for ( int i = 1 ; i < n; i++) {
if (points[i].x < points[leftmost].x) {
leftmost = i;
}
}
int current = leftmost;
vector<Point> hull;
do {
hull. push_back (points[current]);
int next = (current + 1 ) % n;
for ( int i = 0 ; i < n; i++) {
if ( isClockwise (points[current], points[i], points[next])) {
next = i;
}
}
current = next;
} while (current != leftmost);
return hull;
}
int main () {
vector<Point> points = {
{ 0 , 0 },
{ 1 , 3 },
{ 2 , 1 },
{ 3 , 4 },
{ 5 , 2 },
{ 6 , 3 },
{ 8 , 0 },
{ 9 , 2 }
};
vector<Point> convexHull = findConvexHull (points);
cout << "Tashqi yuz nuqtalari: " ;
for ( const Point& point : convexHull) {
cout << "(" << point.x << ", " << point.y << ") " ;
}
return 0 ;
}
27](/data/documents/c168eab5-9f41-4176-a176-b92cae32e94c/page_27.png)
Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari Mundarija KIRISH 1-bob………………………………………………………………………………4 1. 1. Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari tushunchasi ………………………………………………………………………5 2-bob 2.1. Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari tushunchasi ………………………………………………………………………5 2.2. Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmiga oid misollar ………………………………………………………………………5 2.3. Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlarini C++ dasturlash tilda ifodalash ……………………………………………………5 2.4. Dasturni murakkabligini baholash ……………………………………………5 Xulosa ……………………………………………………………….........………30 Foydanilgan adabiyotlar ………………………………………………....……31 1
Kirish Planar grafikning tashqi yüzini aniqlash uchun bir necha algoritmlar mavjud. Planar grafik, barcha qatorlari qarshilashm asligi (crossing) yoki faqat bitta birikmali (multiple) qator (edge)ning mavjudligini bildiradi. Quyidagi algoritmlar planar grafikning tashqi yüzini aniqlashda foydalaniladi: 1. Planarlık testi (Planarity Test): Bu algoritmlar grafikning bir nechta qanchalarini muqobil qatorlarning kesishmasini tekshiradi. Engelessan to'plami (Face of a Graph) usulini ishlatadi. 2. PQ daraxti (PQ-tree): Bu algoritmda, grafikning barcha tashqi yuzlarni topish uchun " PQ daraxti " strukturasidan foydalaniladi. 3. Gramiy-Di-Battista algoritmi: Bu algoritm birikmalarning kirishmasini aniqlash uchun ishlatiladi. Qatorlar orasidagi pontos uyg'unligini bildiradi. 4. Tarjima algoritmlari (Embedding algorithms): Bu tarz algoritmlar grafikni planar bir koordinat sistemiga joylashtirish uchun foydalaniladi. Bu koordinat sistemga ko'chirilgan grafik tashqi yüzini olish uchun bir bita tarjima algoritmasidan foydalanish mumkin. Bu algoritmlardan har biri, grafikning to'plamlarni, qatorlarni va yuzlarni aniqlashning turli xususiyatlariga ega bo'lishi mumkin. Tashqi yuzini aniqlash algoritmlari kompyuter grafikasi, kartografiya, tizimlar va boshqa sohalarda foydalaniladi. Planar grafikalarni tashqi yuzini aniqlash algoritmlari ning muallifi Robert Endre Tarjan hisoblanadi. U uning adiblari, qo'yilmalar yuzasining 2
birakilmaslari, qadamlashtirilgan bunyod etish va boshqalar, planar grafikalar bilan bog'liq sohalarda yuqori darajada faol bo'lib, bu sohaga katta qo'shimcha hissa kiritgan. Tarjan aniqlovchiligi muhim matematik vositalardan biri sifatida tanilgan va planar grafikalar sohasidagi yutuqlarni aniqlashda muvaffaqiyatli qo'llanilgan. 1-bob 1.1.SPlanar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari tushunchasi Planar grafik, ikki boylik grafiklardan iborat bo'lgan grafik turlari jismini tushuntiradi. Bu turlar x va y o'qlari orqali boshqa boshqa nuqtalarni bog'lash orqali ko'rsatiladi. Planar grafiklarda nuqta, chiziq, ko'ordinata akseksiya, maydon va boshqa elementlar bilan ishlovchi metod va tushunchalar qo'llaniladi. Planar grafiklarni tashqi yuzlari esa, planar grafiklarning plotterlar, monitorlar, printerlar yoki boshqa chizish vositalariga aylantirilgan formatlardagi ko'rinishlari hisoblanadi. Bu tashqi yuzlar arqali ma'lumotlar o'qilishi, ko'rishishi va ulardan foydalanishga imkon beradi. Bu faqat nazariy ta'riflar hisoblanadi. Planar grafikning yuzlari, bir otvetarafoq, quti yoki boshqa geometrik asoslar ustida joylashtirilgan geometrik shakllardir. Ular, bir-birini kesmagan yoki bir-biriga tegishli bo'lgan chiziqlarni umumiy holatda butunlay o'zgartirishsiz chizish imkoniyatiga ega bo'lgan uch xarakteristikadan iboratdir: 1. Yuzlar qatlamlari: Har bir yuz qatlami bir-qatlamga tegishli girih bo'lib, bitta yuzning bir-tomonli hajmi va tartiblanishi bilan ta'minlanadi. 2. Qatlamlar tarmog'i: Yuzlar qatlamlari butunlay urtasiga tez-tez taklif etilgan bo'lib, bir-birini kesmagan aylana bo'lib chiziladi. 3. Tashkil etish shartlari: Planar grafikning har bir yuzi, asosiy grafik tashkil etish prinsiplari va qoidalari asosida joylashtiriladi 3
Ushbu tushunchalar, planar grafikda yuzlar haqida ma'lumot berishda yordam berishi mumkin bo'lgan yordamchi bir tavsifdir Planar grafik, bir xaritada qo'yg'anga qo'yilgan xech turdagi grafiklardir, masalan, uchburchaklar, to'g'ri to'rtburchaklar va boshqalar. Grafikda barcha yo'l, yuz va boshqa birlashmalarning uchburchaklarga qo'yilgan gradientlari to'g'ri kesishishi mumkin emas. Yuzlar tasviri, bir sovrin suyuq trafik holatida quvurla mo'ljalangan bir material yuzi orqali tasvirlanadi. Grafikda har bir yuz, yuzlarning mosligi va ularning ko'rsatish tartiblari bilan ifodalangan eng to'g'ri loyihalardan birini ifodalaydi. Yuzlar orqali oynashgan maqolalarga yoki obyektlarga murojaat qilish mumkin. Planar grafikning yuzlar orasidagi aloqalariga "yuzboshqaruv" deyiladi. Yuzboshqaruv, har bir yuzning qaysi boshqa yuz bilan biriktirilganligini ifodalaydi. Ikkita yuz bir-biriga toqqa tiyilgan bo'lsa, ulardagi aloqa "kattalashish" deb ataladi. Boshqa so'zlar bilan aytganda, yuzlar orasidagi aloqa oldindan belgilanganlik, bemalol topiladigan yuzlarning yo'naltirilishi orqali aniq bo'ladi. Bunday belgilar asosida planar grafikning umumiy muhit soni va yuzlarning umumiy soni topilishi mumkin.Planar grafik, qatorlar va burchaklar bilan ifodalangan grafikdir, lekin boshqa elementlar (masalan, yuzlar) bir biriga tegishlilikka ega emas. Planar grafikda har bir burchak faqat bir nechta qatorlar bilan bog'langanligi uchun u planar deb ataladi. Yuzlar, bir grafikdagi qatorlar to'plamining ifodalangan qismidir. Bu yuzlar, qatlarni ajratish orqali hosildor bo'lib, yozuvchi uchun aloqador ma lumotlar berganlikda foydalaniladi. Amalda,ʼ planar grafikda yuzlar va qatorlar orasidagi aloqalar, yuzlar qatlarni tegishlantirish orqali ifodalangan. Bu aloqalar planar grafiklarni aylanib-yugurishsiz ifodalaydi.Planar grafik, grafikning bir joyida yoza, bunday qatorlar o'zaro kesishmaydigan bir ko'rgazmani tashkil etadi. Ya'ni, bu grafikdagi har bir qatorda faqat bir ta'velzor (yoki bombozlik) bo'ladi. Yuzlar, planar grafikning qatorlar orqali ajratilgan tekisliklaridir. Yuzlar bir-biriga tegmasdan va bo'shliksizdirlar. 4
Umul qiling, planar grafikning yuzlar va qatorlar ko'ptir. Yuzlar o'rnatish, operatsiyalar va graflar teoriyasi sohasidagi muxim mavzulardan biridir. lanar grafik, boshqa bir deganicha, qoidalariga javob beruvchi grafikdir, ya'ni bir xil ko'plikni kesishuvchan holda aks ettirmaydi 2.2.Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmiga oid misollar Planar grafiklar, bir cho'miladagi harakat bilan yuqoriga chiqmaydigan bir yuzsizlikda chizilgan grafiklardir. Bu misollar, planar grafiklarni ko'rsatadi. 1. Chapdagi misolda, uchta doira berilgan. Ular haqiqiyayam da doira yuqoriga chiqmaydi. Shuningdek, ular qo'llar ichida ham kesib yuruvchilar yo'q. A---B | <!-- Doiralar --> | <!-- kesib yuruvchilar --> C---D 2. Keyingi misolda, uchta to'rtburchak berilgan. Bir biriga uzluksiz chechaklar bilan kesib yurilgan. Bu kesib yurikalarning har biri to'rtburchakni ikkita qirralariga bog'langan. ---- | | 5