দুটি বৃত্তের সাধারণ স্পর্শক নির্ণয়#
দুটি বৃত্ত দেওয়া আছে। এদের সকল সাধারণ স্পর্শক বের করতে হবে, অর্থাৎ এমন সকল সরলরেখা যেগুলো একই সাথে উভয় বৃত্তকে স্পর্শ করে।
বর্ণিত অ্যালগরিদমটি সেই ক্ষেত্রেও কাজ করবে যেখানে একটি (বা উভয়) বৃত্ত বিন্দুতে পরিণত হয়। অর্থাৎ, একটি প্রদত্ত বিন্দু দিয়ে একটি বৃত্তের স্পর্শক নির্ণয় করতেও এই অ্যালগরিদম ব্যবহার করা যায়।
সাধারণ স্পর্শকের সংখ্যা#
দুটি বৃত্তের সাধারণ স্পর্শকের সংখ্যা ০, ১, ২, ৩, ৪ এবং অসীম হতে পারে। বিভিন্ন ক্ষেত্রের জন্য নিচের ছবিগুলো দেখুন।
এখানে আমরা অধঃপতিত ক্ষেত্রগুলো বিবেচনা করব না, অর্থাৎ যখন বৃত্ত দুটি সমপাতিত (এক্ষেত্রে অসীম সংখ্যক সাধারণ স্পর্শক থাকে), অথবা একটি বৃত্ত অন্যটির ভেতরে থাকে (এক্ষেত্রে কোনো সাধারণ স্পর্শক নেই, অথবা বৃত্ত দুটি স্পর্শক হলে একটি সাধারণ স্পর্শক আছে)।
বেশিরভাগ ক্ষেত্রে দুটি বৃত্তের চারটি সাধারণ স্পর্শক থাকে।
বৃত্ত দুটি যদি পরস্পর স্পর্শক হয়, তাহলে তাদের তিনটি সাধারণ স্পর্শক থাকবে, তবে এটি একটি অধঃপতিত ক্ষেত্র হিসেবে বোঝা যায়: যেন দুটি স্পর্শক একত্রিত হয়ে গেছে।
এছাড়াও, নিচে বর্ণিত অ্যালগরিদমটি সেই ক্ষেত্রেও কাজ করবে যখন একটি বা উভয় বৃত্তের ব্যাসার্ধ শূন্য: এক্ষেত্রে যথাক্রমে দুটি বা একটি সাধারণ স্পর্শক থাকবে।
সংক্ষেপে, অসীম স্পর্শকের ক্ষেত্র ব্যতীত সকল ক্ষেত্রে আমরা সর্বদা চারটি স্পর্শক খুঁজব (অসীম স্পর্শকের ক্ষেত্রটি আলাদাভাবে সামলাতে হবে এবং এখানে আলোচনা করা হয়নি)। অধঃপতিত ক্ষেত্রে কিছু স্পর্শক সমপাতিত হবে, তবুও এই ক্ষেত্রগুলো সামগ্রিক চিত্রে মানানসই হবে।
অ্যালগরিদম#
অ্যালগরিদমের সরলতার জন্য, সাধারণতা না হারিয়ে আমরা ধরে নেব যে প্রথম বৃত্তের কেন্দ্র $(0, 0)$ স্থানাঙ্কে। (যদি এমন না হয়, তাহলে পুরো চিত্রকে সরিয়ে এটি অর্জন করা যায়, এবং সমাধান পাওয়ার পর প্রাপ্ত সরলরেখাগুলো আবার পেছনে সরানো যায়।)
$r_1$ এবং $r_2$ দ্বারা প্রথম ও দ্বিতীয় বৃত্তের ব্যাসার্ধ এবং $(v_x,v_y)$ দ্বারা দ্বিতীয় বৃত্তের কেন্দ্র ও মূলবিন্দু থেকে ভিন্ন বিন্দু $v$-এর স্থানাঙ্ক বোঝানো হচ্ছে। (দ্রষ্টব্য: আমরা সেই ক্ষেত্র বিবেচনা করছি না যেখানে উভয় বৃত্ত একই।)
সমস্যাটি সমাধানের জন্য আমরা সম্পূর্ণ বীজগাণিতিক পদ্ধতি অনুসরণ করব। আমাদের $ax + by + c = 0$ আকারের সকল সরলরেখা বের করতে হবে যেগুলো মূলবিন্দু থেকে $r_1$ দূরত্বে এবং বিন্দু $v$ থেকে $r_2$ দূরত্বে অবস্থিত। এছাড়াও আমরা সরলরেখার নরমালাইজেশন শর্ত আরোপ করি: সহগের বর্গের যোগফল একের সমান হতে হবে (এটি প্রয়োজন, অন্যথায় একই সরলরেখার জন্য $ax + by + c = 0$ আকারে অসীম সংখ্যক উপস্থাপনা থাকবে)। মোট আমরা কাঙ্ক্ষিত $a, b, c$-এর জন্য এই সমীকরণ ব্যবস্থা পাই:
$$\begin{align} a^2 + b^2 &= 1 \\ \mid a \cdot 0 + b \cdot 0 + c \mid &= r_1 \\ \mid a \cdot v_x + b \cdot v_y + c \mid &= r_2 \end{align}$$পরমান মান থেকে মুক্তি পেতে লক্ষ্য করুন যে এই ব্যবস্থায় পরমান মান খোলার মাত্র চারটি উপায় আছে। সকল উপায় একটি সাধারণ ক্ষেত্র দ্বারা বিবেচনা করা যায়, যদি আমরা পরমান মান খোলাকে এভাবে বুঝি যে ডানপক্ষের সহগকে -১ দ্বারা গুণ করা যেতে পারে। অন্যভাবে বলতে গেলে, আমরা এই ব্যবস্থায় আসি:
$$\begin{align} a^2 + b^2 &= 1 \\ c &= \pm r_1 \\ a \cdot v_x + b \cdot v_y + c &= \pm r_2 \end{align}$$$d_1 = \pm r_1$ এবং $d_2 = \pm r_2$ সংকেত ব্যবহার করে, আমরা এই সিদ্ধান্তে আসি যে ব্যবস্থাটির চারটি সমাধান থাকবে:
$$\begin{align} a^2 + b^2 &= 1 \\ c &= d_1 \\ a \cdot v_x + b \cdot v_y + c &= d_2 \end{align}$$এই ব্যবস্থার সমাধান একটি দ্বিঘাত সমীকরণ সমাধানে নেমে আসে। আমরা সকল জটিল হিসাব বাদ দিয়ে সরাসরি প্রস্তুত উত্তর দিচ্ছি:
$$\begin{align} a &= {( d_2 - d_1 ) v_x \pm v_y \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} } \\ b &= {( d_2 - d_1 ) v_y \pm v_x \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} } \\ c &= d_1 \end{align}$$মোট আমরা চারের বদলে আটটি সমাধান পেলাম। তবে অতিরিক্ত সমাধানগুলো কোথা থেকে আসে তা বুঝতে সহজ: আসলে শেষ ব্যবস্থায় শুধুমাত্র একটি সমাধান নেওয়াই যথেষ্ট (যেমন, প্রথমটি)। কারণ, $\pm r_1$ এবং $\pm r_2$ নেওয়ার জ্যামিতিক অর্থ হলো: আমরা আসলে প্রতিটি বৃত্তের কোন পাশে সরলরেখা আছে তা বাছাই করছি। তাই শেষ ব্যবস্থা সমাধান করতে যে দুটি পদ্ধতি আসে তা অপ্রয়োজনীয়: দুটি সমাধানের একটি বেছে নিলেই যথেষ্ট (শুধু অবশ্যই চারটি ক্ষেত্রেই একই পরিবারের সমাধান বাছাই করতে হবে)।
শেষ যে বিষয়টি আমরা এখনও বিবেচনা করিনি তা হলো, প্রথম বৃত্ত মূলত মূলবিন্দুতে না থাকলে সরলরেখাগুলো কীভাবে সরাতে হবে। তবে এটি সরল: সরলরেখার সমীকরণের রৈখিকতা থেকে বোঝা যায় যে $a \cdot x_0 + b \cdot y_0$ মান (যেখানে $x_0$ ও $y_0$ প্রথম বৃত্তের মূল কেন্দ্রের স্থানাঙ্ক) সহগ $c$ থেকে বিয়োগ করতে হবে।
ইমপ্লিমেন্টেশন#
প্রথমে আমরা সকল প্রয়োজনীয় ডাটা স্ট্রাকচার এবং অন্যান্য সহায়ক সংজ্ঞা বর্ণনা করি:
struct pt {
double x, y;
pt operator- (pt p) {
pt res = { x-p.x, y-p.y };
return res;
}
};
struct circle : pt {
double r;
};
struct line {
double a, b, c;
};
const double EPS = 1E-9;
double sqr (double a) {
return a * a;
}তারপর সমাধানটি এভাবে লেখা যায় (যেখানে কল করার জন্য মূল ফাংশন হলো দ্বিতীয়টি; এবং প্রথম ফাংশনটি একটি সহায়ক):
void tangents (pt c, double r1, double r2, vector<line> & ans) {
double r = r2 - r1;
double z = sqr(c.x) + sqr(c.y);
double d = z - sqr(r);
if (d < -EPS) return;
d = sqrt (abs (d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back (l);
}
vector<line> tangents (circle a, circle b) {
vector<line> ans;
for (int i=-1; i<=1; i+=2)
for (int j=-1; j<=1; j+=2)
tangents (b-a, a.r*i, b.r*j, ans);
for (size_t i=0; i<ans.size(); ++i)
ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
return ans;
}