المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:تقاطع‌ خط و پاره‌خط‌ها

تقاطع خط و پاره خط‌ها

تعریف

یکی از روش‌های پیدا کردن محل تقاطع امتداد دو پاره خط با استفاده از اعداد مختلط صورت‌ می‌گیرد.در این روش به دلیل وجود امکان ضرب کردن متغیر‌ها و نقاط در یکدیگر مزیت‌هایی وجود دارد که به طور مثال می توان به نمایش نقطه برخورد خطوط به صورت یک عدد مختلط اشاره کرد .هم چنین در بسیاری از معادلات و محاسبات پیشرفته‌تر که به بررسی وضعیت نقاط و خطوط‌ می‌پردازد ، نمایش محل برخورد اجزا به صورت یک عدد ، کمک بسیاری در تحلیل بهتر معادلات‌ می‌کند.

الگوریتم

برای محاسبه محل تقاطع دو خط کافیست معادله آن دو را حل کرده و در صورتی که جواب داشته باشند آن دو خط متقاطع اند. حال برای بررسی این که آیا دو پاره خط با هم متقاطع هستند یا نه باید به صورت زیر عمل کنیم :


1.ابتدا محل تقاطع خطوط حامل پاره خط هارا در صورت وجود پیدا می کنیم.


2.سپس بررسی می کنیم که آیا نقطه محاسبه شده بر روی یکی از پاره خط ها قرار دارد یا نه.


برای انجام قسمت 1 کافیست معادله خط را با داشتن 2 نقطه از آن بدست آورده و آن ها را حل کنیم. برای قسمت 2 نیز می بایست پاره خط را با بردار نقطه تقاطع به مبدا انتقال دهیم و بررسی کنیم که آیا دو سر پاره خط در دو ربع متفاوت هستند یا خیر.

حل مساله برای اعداد مختلط

هر پاره خط در صفحه مختلط به وسیله 2 عدد قابل نمایش است که همان ابتدا و انتهای پاره خط‌ می‌باشد.مثلا ab پاره خطیست که عدد a یک سر آن و عدد b سر دیگر پاره خط است.حال برای پیدا کردن محل تقاطع 2 پاره خط بایستی شرط‌هایی لازم و کافی برای یک نقطه دلخواه مانند X بیابیم که در صورت برقراری آن‌ها نقطه X روی خط حاصل از امتداد پاره خط ab قرار داشته باشد.حال فرض کنید نقطه X روی خط حاصل از امتداد ab باشد ، در این صورت خواهیم داشت :

$$\frac {x-a} {b-a} =\overline {\left (\frac {x-a} {b-a} \right)},$$ بنابراین : $$ (x-a) (\overline {b}-\overline {a}) = (b-a) (\overline {x}-\overline {a}),$$

$$ (\overline {b}-\overline {a}) x-(b-a) \overline {x} = (\overline {b}-\overline {a}) a-(b-a) \overline {a} \tag1 $$

حال فرض کنید نقطه x همزمان روی خط cd (خط حاصل از امتداد پاره خط cd) نیز قرار دارد.بنابراین مشابها خواهیم داشت :

$$\frac {x-c} {d-c} =\overline {\left (\frac {x-c} {d-c} \right)},$$

بنابراین : $$ (x-c) (\overline {d}-\overline {c}) = (d-c) (\overline {x}-\overline {c}),$$

$$ (\overline {d}-\overline {a}) x-(d-c) \overline {x} = (\overline {d}-\overline {c}) c-(d-c) \overline {c} \tag2 $$

حال دو طرف معادله (1) را در (d-c) ضرب‌ می‌کنیم :

$$ (d-c) (\overline {b}-\overline {a}) x-(d-c) (b-a) \overline {x} = ((\overline {b}-\overline {a}) a-(b-a) \overline {a}) (d- c) \tag3 $$

هم چنین دو طرف معادله (2) را در (b-a) ضرب‌ می‌کنیم :

$$ (b-a) (\overline {d}-\overline {c}) x-(d-c) (b-a) \overline {x} = ((\overline {d}-\overline {c}) c-(d-c) \overline {c}) (b-a) \tag4 $$

حال از تفاضل معادله (3) و (4) خواهیم داشت :

$$ (d-c) (\overline {b}-\overline {a}) x-(b-a) (\overline {d}-\overline {c}) x = ((\overline {b}-\overline {a}) a-(b-a) \overline {a}) (d-c)-((\overline {d}-\overline {c}) c-(d-c) \overline {c}) (b-a),$$

که مقدار x بدست‌ می‌آید :

$$ x=\frac {((\overline {b}-\overline {a}) a-(b-a) \overline {a}) (d-c)-((\overline {d}-\overline {c}) c-(d-c) \overline {c}) (b-a)} {(d-c) (\overline {b}-\overline {a})-(b-a) (\overline {d}-\overline {c})} $$

پیاده‌سازی اولیه

برای پیاده سازی اعداد مختلط با استفاده از دستگاه مختصات دو بعدی‌ می‌بایست قوانین جمع و ضرب اعداد مختلط را برای دوتایی‌های (x,y) به وسیله ایجاد تعدادی تابع در برنامه تعریف کرد .اما به طور مستقل نیز‌ می‌توان با اضافه کردن کتاب خانه اعداد مختلط در برنامه ، از توابع تعریف شده در این کتاب خانه کمک گرفت :

#include <complex>
using namespace std;
typedef complex<double> point;
 
 
//The Dot And Cross Products
double dot (const point &a, const point &b) {return real (conj (a) * b);}
double cross (const point &a, const point &b) {return imag (conj (a) * b);}
 
// returns intersection of infinite lines ab and pq (undefined if they are parallel)
point intersect (const point &a, const point &b, const point &p, const point &q)
{double d1 = cross (p -a, b -a);
double d2 = cross (q -a, b -a);
return (d1 * q -d2 * p) / (d1 -d2);}

کابردها

یکی از ویژگی‌های این روش این است که‌ می‌توان مختصات محل تقاطع را به صورت یک نقطه داشت فلذا کار با آن و استفاده از آن در سایر معادلات بسیار آسان‌تر و قابل بررسی‌تر‌ می‌شود.هم چنین در محاسبه پوش محدب تعدادی نقطه و سایر تعاریف هندسی نیز کاربرد فراوانی دارد.


ابزار صفحه