একটি লাইন দুটি পয়েন্টকে সংযুক্ত করে। এটি গ্রাফিক্স-এ একটি বেসিক এলিমেন্ট। একটি লাইন আঁকতে, আপনাকে দুটি পয়েন্টের প্রয়োজন যেসবের মাঝপথে আপনি একটি স্ক্রিনে লাইন আঁকতে পারেন এবং গ্রাফিক্সের ভাষায় আমরা পয়েন্টগুলকে পিক্সেল বলি এবং প্রতিটি পিক্সেল ইন্টিজার কোঅর্ডিনেটের সাথে যুক্ত। আমাদের পূর্ণসংখ্যা কোঅর্ডিনেট দেওয়া আছে (x1, y1) এবং (x2, y2) রূপে যেখানে, x1 < x2 এবং y1 < y2। কাজটি হল মিডপয়েন্ট লাইন জেনারেশন অ্যালগরিদম ব্যবহার করে পয়েন্ট ১ অর্থাৎ (x1, y1) এবং পয়েন্ট ২ অর্থাৎ (x2, y2)-এর মাঝপথে সকল মিড-পয়েন্ট গণনা করা।
স্ক্রিনে লাইন জেনারেশন করার জন্য তিনটি ভিন্ন অ্যালগরিদম ব্যবহৃত হয় এবং সেগুলো হল:-
- DDA অ্যালগরিদম
- ব্রেসেনহ্যাম'স লাইন জেনারেশন (Bresenham's Line Generation)
- মিড-পয়েন্ট অ্যালগরিদম (Mid-Point Algorithm)
মিড-পয়েন্ট অ্যালগরিদম
মিড-পয়েন্ট লাইন অ্যালগরিদম ব্যবহার করে লাইন আঁকার ধাপসমূহ:-
- বর্তমান অবস্থান পয়েন্ট ব্যবহার করে মিডল পয়েন্ট গণনা করুন অর্থাৎ East(Xp+1, Yp) এবং North East(Xp+1, Yp+1) হল মিডল পয়েন্ট(Xp+1, Yp+1/2)।
- এখন, মিডল পয়েন্ট স্ক্রিনে পরবর্তী কোঅর্ডিনেটের লোকেশন নির্ধারণ করবে অর্থাৎ:
- যদি মিডল পয়েন্ট লাইনের উপরে থাকে, তবে পরবর্তী কোঅর্ডিনেট হবে EAST-এ।
- যদি মিডল পয়েন্ট লাইনের নিচে থাকে, তবে পরবর্তী কোঅর্ডিনেট হবে NORTH EAST-এ।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - int x_1 = 3, int y_1 = 3, int x_2 = 10, int y_2 = 8
আউট - লাইন জেনারেশন অ্যালগরিদমের মাধ্যমে মিড-পয়েন্টগুলো: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8
ব্যাখ্যা - আমাদের কোঅর্ডিনেট দেওয়া আছে x_1 = 3, x_2 = 10, y_1 = 3, y_2 = 8। তাই ধাপগুলো হবে প্রথমে dx = x_2 - x_1 = 10 - 3 = 7 এবং dy = y_2 - y_1 = 8 - 3 = 5 হিসাব করুন এবং চেক করুন dy dx-এর চেয়ে কম কিনা। এখন d = 5 - (7 / 2) = 2 হিসাব করুন। প্রথম পয়েন্ট হবে x_1 এবং y_1। সেগুলো প্রিন্ট করুন। এখন, যতক্ষণ x_1 < x_2:x_1 কে ১ বাড়ান এবং চেক করুন যদি d < 0 তবে d = d + dy সেট করুন অন্যথায়, d = d + (dy - dx) সেট করুন এবং y_2 কে ১ বাড়ান।
ইন - int x_1 = 2, int y_1 = 2, int x_2 = 3, int y_2 = 4
আউট - লাইন জেনারেশন অ্যালগরিদমের মাধ্যমে মিড-পয়েন্টগুলো: 2,2 3,3 3,4
ব্যাখ্যা - আমাদের কোঅর্ডিনেট দেওয়া আছে x_1 = 2, x_2 = 2, y_1 = 3, y_2 = 4। মিড-পয়েন্ট লাইন জেনারেশন অ্যালগরিদম প্রয়োগ করে সকল মিড-পয়েন্ট পিক্সেল আউটপুট হিসেবে গণনা করব।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
- পূর্ণসংখ্যা পয়েন্ট ইনপুট নিন int x_1, int y_1, int x_2, int y_2 হিসেবে। Mid_Point(x_1, y_1, x_2, y_2) ফাংশন কল করুন লাইন জেনারেট করতে।
- Mid_Point(x_1, y_1, x_2, y_2) ফাংশনের ভিতরে:
- dx = x_2 - x_1 এবং dy = y_2 - y_1 হিসাব করুন।
- চেক করুন IF dy <= dx তবে d = dy - (dx / 2) এবং first_pt = x_1 এবং second_pt = y_1 সেট করুন।
- first_pt এবং second_pt প্রিন্ট করুন।
- যতক্ষণ first_pt < x_2: first_pt কে ১ বাড়ান এবং চেক করুন IF d < 0 তবে d = d + dy সেট করুন। ELSE, d = d + (dy - dx) সেট করুন এবং second_pt কে ১ বাড়ান। first_pt এবং second_pt প্রিন্ট করুন।
- ELSE IF dx < dy তবে d = dx - (dy/2) এবং first_pt = x_1 এবং second_pt = y_1 সেট করুন এবং first_pt এবং second_pt প্রিন্ট করুন।
- WHILE second_pt < y_2। WHILE-এর ভিতরে second_pt কে ১ বাড়ান। চেক করুন IF d < 0 তবে d = d + dx সেট করুন। ELSE, d = d + (dx - dy) সেট করুন এবং first_pt কে ১ বাড়ান।
- first_pt এবং second_pt প্রিন্ট করুন।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
void Mid_Point(int x_1, int y_1, int x_2, int y_2){
int dx = x_2 - x_1;
int dy = y_2 - y_1;
if(dy <= dx){
int d = dy - (dx / 2);
int first_pt = x_1;
int second_pt = y_1;
cout<< first_pt << "," << second_pt << "\n";
while(first_pt < x_2){
first_pt++;
if(d < 0){
d = d + dy;
}
else{
d = d + (dy - dx);
second_pt++;
}
cout << first_pt << "," << second_pt << "\n";
}
}
else if(dx < dy){
int d = dx - (dy/2);
int first_pt = x_1;
int second_pt = y_1;
cout << first_pt << "," << second_pt << "\n";
while(second_pt < y_2){
second_pt++;
if(d < 0){
d = d + dx;
}
else{
d += (dx - dy);
first_pt++;
}
cout << first_pt << "," << second_pt << "\n";
}
}
}
int main(){
int x_1 = 3;
int y_1 = 3;
int x_2 = 10;
int y_2 = 8;
cout<<"Mid-Points through Line Generation Algorithm are: ";
Mid_Point(x_1, y_1, x_2, y_2);
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি জেনারেট হবে
Mid-Points through Line Generation Algorithm are: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8
