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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_14.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_15.png?v=1)
![}
// 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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_17.png?v=1)
![// 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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_18.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_19.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_20.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_22.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_24.png?v=1)
![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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_25.png?v=1)
![// 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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_26.png?v=1)
![}
// 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](https://docx.uz/documents/0e35ac79-457c-4ab1-98ce-cd442a07ef7b/page_27.png?v=1)
Planar grafikning tashqi yuzi uchun barcha yuzlarni aniqlash algoritmlari