ইউক্লিডিয়ান সমতল জ্যামিতিতে একটি কোয়াড্রিল্যাটারেল (চতুর্ভুজ) চারটি শিরোনাম এবং চারটি বাহু দিয়ে গঠিত একটি পলিগন। এর অন্য নামগুলো হল 4-gon ইত্যাদি এবং কখনও কখনও এগুলোকে বর্গ, ডিসপ্লে স্টাইল ইত্যাদি নামেও ডাকা হয়।
এই আর্টিকেলে আমরা দিয়ে गये পয়েন্ট থেকে সম্ভাব্য কোয়াড্রিল্যাটারেল সংখ্যা বের করার পদ্ধতি ব্যাখ্যা করব। এই সমস্যায় আমাদের বের করতে হবে কার्तেসিয়ান প্লেনে দেওয়া চারটি পয়েন্ট (x, y) দিয়ে কতগুলো কোয়াড্রিল্যাটারেল তৈরি করা সম্ভব। উদাহরণ:
ইনপুট : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 ) আউটপুট : 1 ব্যাখ্যা : একটি কোয়াড্রিল্যাটারেল তৈরি করা যায় (ABCD)
ইনপুট : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 ) আউটপুট : 3 ব্যাখ্যা : ৩টি কোয়াড্রিল্যাটারেল তৈরি করা যায় (ABCD), (ABDC) এবং (ADBC)।
সমাধানের পদ্ধতি
প্রথমে চেক করব ৪টি পয়েন্টের মধ্যে ৩টি কোলিনিয়ার (একই রেখায় অবস্থিত) কিনা। যদি হ্যাঁ হয়, তবে পয়েন্টগুলো দিয়ে কোনো কোয়াড্রিল্যাটারেল তৈরি করা যাবে না।
এরপর চেক করব ৪টি পয়েন্টের মধ্যে ২টি সমান কিনা। যদি হ্যাঁ হয়, তবে কোনো কোয়াড্রিল্যাটারেল তৈরি করা যাবে না।
এখন চেক করব ডায়াগোনালদোয়ে ইন্টারসেক্ট করে কিনা। যদি হ্যাঁ হয়, তবে শুধু একটি কোয়াড্রিল্যাটারেল তৈরি করা সম্ভব, যাকে কনভেক্স কোয়াড্রিল্যাটারেল বলা হয়।
মোট ইন্টারসেকশন = ১
যদি ডায়াগোনাল ইন্টারসেক্ট না করে, তবে তিনটি সম্ভাব্য কোয়াড্রিল্যাটারেল তৈরি করা যায়, যাকে কনকেভ (concave) কোয়াড্রিল্যাটারেল বলা হয়।
মোট ইন্টারসেকশন = ০
উদাহরণ
#include <iostream> using namespace std; struct Point{ // পয়েন্ট int x; int y; }; int check_orientation(Point i, Point j, Point k){ int val = (j.y - i.y) * (k.x - j.x) - (j.x - i.x) * (k.y - j.y); if (val == 0) return 0; return (val > 0) ? 1 : 2; } // লাইন সেগমেন্ট ইন্টারসেক্ট করে কিনা চেক bool check_Intersect(Point A, Point B, Point C, Point D){ int o1 = check_orientation(A, B, C); int o2 = check_orientation(A, B, D); int o3 = check_orientation(C, D, A); int o4 = check_orientation(C, D, B); if (o1 != o2 && o3 != o4) return true; return false; } // ২টি পয়েন্ট সমান কিনা চেক bool check_similar(Point A, Point B){ // যদি সমান পাওয়া যায় তবে false রিটার্ন অর্থাৎ কোয়াড্রিল্যাটারেল বানাবে না if (A.x == B.x && A.y == B.y) return false; // সমান না পাওয়া গেলে true রিটার্ন return true; } // তিনটি পয়েন্ট কোলিনিয়ার কিনা চেক bool check_collinear(Point A, Point B, Point C){ int x1 = A.x, y1 = A.y; int x2 = B.x, y2 = B.y; int x3 = C.x, y3 = C.y; if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2)) return false; else return true; } // main function int main(){ struct Point A,B,C,D; A.x = -2, A.y = 8;// A(-2, 8) B.x = -2, B.y = 0;// B(-2, 0) C.x = 6, C.y = -1;// C(6, -1) D.x = 0, D.y = 8;// D(0, 8) // চেক করো ৩টি পয়েন্ট কোলিনিয়ার কিনা bool flag = true; flag = flag & check_collinear(A, B, C); flag = flag & check_collinear(A, B, D); flag = flag & check_collinear(A, C, D); flag = flag & check_collinear(B, C, D); // যদি কোলিনিয়ার পাওয়া যায় if (flag == false){ cout << "Number of quadrilaterals possible from the given points: 0"; return 0; } // চেক করো ২টি পয়েন্ট সমান কিনা bool same = true; same = same & check_similar(A, B); same = same & check_similar(A, C); same = same & check_similar(B, D); same = same & check_similar(C, D); same = same & check_similar(A, D); same = same & check_similar(B, C); // যদি সমান পয়েন্ট থাকে if (same == false){ cout << "Number of quadrilaterals possible from the given points: 0"; return 0; } // চেক করো ডায়াগোনাল ইন্টারসেক্ট করে কিনা flag = true; if (check_Intersect(A, B, C, D)) flag = false; if (check_Intersect(A, C, B, D)) flag = false; if (check_Intersect(A, B, D, C)) flag = false; if (flag == true) cout << "Number of quadrilaterals possible from the given points: 3"; else cout << "Number of quadrilaterals possible from the given points: 1"; return 0; }
আউটপুট
Number of quadrilaterals possible from the given points : 1
উপরোক্ত কোডের ব্যাখ্যা
এই কোড নিচের ধাপগুলো অনুসরণ করে বোঝা যায়:
চেক করো যেকোনো তিনটি পয়েন্ট কোলিনিয়ার কিনা এবং যদি হ্যাঁ হয়, তবে কোয়াড্রিল্যাটারেল সংখ্যা: ০
চেক করো যেকোনো দুটি পয়েন্ট সমান কিনা এবং যদি হ্যাঁ হয়, তবে কোয়াড্রিল্যাটারেল সংখ্যা: ০
চেক করো যেকোনো লাইন সেগমেন্ট ইন্টারসেক্ট করে কিনা:
হ্যাঁ হলে কোয়াড্রিল্যাটারেল সংখ্যা: ১
না হলে কোয়াড্রিল্যাটারেল সংখ্যা: ৩
উপসংহার
এই আর্টিকেলে আমরা দেওয়া ৪টি পয়েন্ট থেকে তৈরি হতে পারে সকল সম্ভাব্য কোয়াড্রিল্যাটারেল বের করেছি। আমরা বুঝেছি কোয়াড্রিল্যাটারেল সংখ্যা কোলিনিয়ারিটি, ইন্টারসেকশন এবং ওরিয়েন্টেশনের ওপর কিভাবে নির্ভর করে। আমরা একই জন্য C++ প্রোগ্রাম লিখেছি, এবং এই প্রোগ্রাম C, Java, Python বা অন্য ভাষায়ও লেখা যায়।
