پرش به محتویات

تقاطع دایره و خط

با داشتن مختصات مرکز دایره، شعاع آن و معادله‌ی یک خط، باید نقاط تقاطع آن‌ها را پیدا کنید.

راه حل

به جای حل دستگاه دو معادله، به صورت هندسی به مسئله نزدیک می‌شویم. به این ترتیب از دیدگاه پایداری عددی به جوابی دقیق‌تر می‌رسیم.

بدون از دست دادن کلیت مسئله، فرض می‌کنیم که مرکز دایره در مبدأ مختصات قرار دارد. اگر اینطور نباشد، آن را به مبدأ منتقل کرده و ثابت $C$ را در معادله‌ی خط تصحیح می‌کنیم. بنابراین، یک دایره به مرکز $(0,0)$ و شعاع $r$ و یک خط با معادله‌ی $Ax+By+C=0$ داریم.

ابتدا نقطه‌ای روی خط را پیدا می‌کنیم که به مبدأ مختصات نزدیک‌ترین باشد، یعنی $(x_0, y_0)$. اولاً، این نقطه باید در فاصله‌ی زیر باشد:

$$ d_0 = \frac{|C|}{\sqrt{A^2+B^2}} $$

دوماً، از آنجایی که بردار $(A, B)$ بر خط عمود است، مختصات این نقطه باید با مختصات این بردار متناسب باشد. چون فاصله‌ی نقطه تا مبدأ را می‌دانیم، کافی است بردار $(A, B)$ را به این طول مقیاس‌بندی کنیم تا به نتیجه‌ی زیر برسیم:

$$\begin{align} x_0 &= - \frac{AC}{A^2 + B^2} \\ y_0 &= - \frac{BC}{A^2 + B^2} \end{align}$$

علامت‌های منفی ممکن است بدیهی نباشند، اما با جایگذاری $x_0$ و $y_0$ در معادله‌ی خط به راحتی قابل تأیید هستند.

در این مرحله می‌توانیم تعداد نقاط تقاطع را مشخص کنیم و حتی در حالتی که یک یا صفر نقطه وجود دارد، جواب را پیدا کنیم. در واقع، اگر فاصله‌ی $(x_0, y_0)$ تا مبدأ، یعنی $d_0$، از شعاع $r$ بزرگتر باشد، پاسخ صفر نقطه است. اگر $d_0=r$ باشد، پاسخ یک نقطه یعنی $(x_0, y_0)$ است. اگر $d_0<r$ باشد، دو نقطه‌ی تقاطع وجود دارد و اکنون باید مختصات آنها را پیدا کنیم.

پس می‌دانیم که نقطه‌ی $(x_0, y_0)$ داخل دایره قرار دارد. دو نقطه‌ی تقاطع، یعنی $(a_x, a_y)$ و $(b_x, b_y)$، باید روی خط $Ax+By+C=0$ قرار داشته باشند و باید در فاصله‌ی یکسان $d$ از $(x_0, y_0)$ باشند. این فاصله به راحتی پیدا می‌شود:

$$ d = \sqrt{r^2 - \frac{C^2}{A^2 + B^2}} $$

توجه داشته باشید که بردار $(-B, A)$ با خط هم‌راستا است، و بنابراین می‌توانیم با جمع و تفریق بردار $(-B,A)$ که به طول $d$ مقیاس‌بندی شده، با نقطه‌ی $(x_0, y_0)$، نقاط مورد نظر را پیدا کنیم.

در نهایت، معادلات دو نقطه‌ی تقاطع عبارتند از:

$$\begin{align} m &= \sqrt{\frac{d^2}{A^2 + B^2}} \\ a_x &= x_0 + B \cdot m, a_y = y_0 - A \cdot m \\ b_x &= x_0 - B \cdot m, b_y = y_0 + A \cdot m \end{align}$$

اگر دستگاه معادلات اصلی را با روش‌های جبری حل می‌کردیم، احتمالاً به جوابی با شکلی متفاوت و خطای بیشتر می‌رسیدیم. روش هندسی که در اینجا شرح داده شد، ملموس‌تر و دقیق‌تر است.

پیاده‌سازی

همانطور که در ابتدا اشاره شد، فرض می‌کنیم که مرکز دایره در مبدأ قرار دارد، و بنابراین ورودی برنامه شعاع دایره $r$ و پارامترهای $A$، $B$ و $C$ از معادله‌ی خط است.

double r, a, b, c; // given as input
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
    puts ("no points");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
    puts ("1 point");
    cout << x0 << ' ' << y0 << '\n';
}
else {
    double d = r*r - c*c/(a*a+b*b);
    double mult = sqrt (d / (a*a+b*b));
    double ax, ay, bx, by;
    ax = x0 + b * mult;
    bx = x0 - b * mult;
    ay = y0 - a * mult;
    by = y0 + a * mult;
    puts ("2 points");
    cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}

مسائل تمرینی