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

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

برای پاسخ به این سوالات اول به سراغ تعریف نقطه و نحوه قرارگیری اشیا در فضاهای دو بعدی و سه بعدی می‌ریم، دستگاه مختصاتی که از این به بعد روی اون کار خواهیم کرد رو معرفی می‌کنیم و سپس به سراغ تعریف خط و بردار می‌ریم، کاربرد خط و بردار می‌تونه در تعریف مسیر حرکت یک شی یا مشخص کردن لبه‌های اون تو فضا باشه و در پایان بعد از بررسی برخی از ویژگی‌های خطوط یا بردارها به بررسی یک نمونه از سیستم‌های تشخیص برخورد دو شی می‌پردازیم، یعنی سیستم line-line collision detection.

نقطه

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

هندسه تحلیلی

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

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

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

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

بر روی محور y، مقادیر بالای مرکز مختصات، مثبت و مقادیر پایین، منفی هستند.

محل یک نقطه در یک صفحه نیز با یک جفت عدد مشخص می‌شود، که عدد اول مشخص کننده محل نقطه روی محور x و عدد دوم مشخص کننده محل نقطه روی محور y است. برای مثال در نمودار بالا، نقطه A دارای مختصات (۴ ,۳) است و نقطه B در محل (۱ ,۲-) قرار گرفته است. توجه داشته باشید که ترتیب اعداد در این سیستم نمایش بسیار مهم است.

کاربرد هندسه تحلیلی

دونستن محل قرار گیری تعدادی از نقاط به ما می‌تونه در موارد زیر کمک کنه:

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

حالا فرض کنیم قصد داریم تا شش شی که محل قرار گیری آنها (با نمادهای A تا F مشخص شده‌اند) را روی صفحه نمایش قرار دهیم. برای این کار، نقاط مشخص شده (۰ ,۰)A و (۲ ,۱)B و (۳ ,۴)C و (۲ ,۱-)D و (۱- ,۲-)E و (۲- ,۳)F را روی دستگاه مختصات دکارتی رسم می‌کنیم.

حالا می‌توانیم با استفاده از توابع و تغییر وضعیت مقادیر x و y نقاط، آنها را روی صفحه جابجا کنیم.

باید دقت کنیم تا بین دستگاه مختصات دکارتی با سیستم مختصات نمایشگرها اشتباه نکنیم. در نظر داشته باشید که در دستگاه مختصات دکارتی جهت مثبت محور y به سمت بالاست ولی سیستم مختصات نمایشگرها طوری طراحی شده تا صفحه نمایش را بتوانیم از بالا به پایین مقدار دهی کنیم، از همین رو در سیستم مختصات نمایشگرها جهت مثبت محور y به سمت پایین است.

در یکی مراحلRendering Pipeline ، تبدیل مختصات دکارتی به مختصات صفحات نمایش اتفاق می‌افتد. در آینده و در یکی از قسمت‌های همین مجموعه راجع به تغییر و تبدیلات دستگاه‌های مختصاتی صحبت خواهیم کرد.

هندسه تحلیلی در فضا

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

مختصات دکارتی (x, y, z) نقطه‌ای در فضا را نشان می‌دهد که محل تقاطع محورهای مختصات با صفحاتی است که این نقطه از آنها می‌گذرد و بر این محورها عمودند.

لازم به ذکر است که جهت محورهای دستگاه مختصات دکارتی در فضا تابع قانون مشخصی نیست، اما دستگاهی که ما قصد کار کردن با آن را داریم، همان‌طور که در شکل بالا مشخص است، راستای مثبت محور y آن به سمت بالا است و راستای مثبت محور z آن به سمت خارج از صفحه و به سمت نظاره‌گر است. این دستگاه یک دستگاه راست گرد است. از آنجایی که دستگاه مورد استفاده در OpenGL نیز با این دستگاه یکی است، به عقیده من، کار کردن با این دستگاه دارای مزیت بیشتری نسبت به دستگاه‌های دیگر است.

نمایش مکان‌های سه بعدی

حالا فرض کنیم قصد داریم محل نقطه (۵ ,۴ ,۲)P را در فضا مشخص کنیم. برای انجام این کار، دو واحد در راستای مثبت محور x، چهار واحد در راستای مثبت محور y و پنج واحد در راستای مثبت محور z حرکت می‌کنیم. حالا می‌توانیم با استفاده از توابع و تغییر وضعیت مقادیر x و y و z هر نقطه مشخصی در فضا، آنها را در فضا جابجا کنیم.

ذخیره سازی نقاط در کد

برای ذخیره سازی مختصات نقاط در کد می‌توانیم دو رویکرد کلی را در نظر بگیریم. رویکرد اول ذخیره مختصات نقاط در نوع‌های داده‌ای ساده و موجود مثل آرایه‌هاست و رویکرد دوم که قوی‌تر از رویکرد اول و مبتنی بر اصول شی ‌گرایی است، پیاده سازی نقاط با استفاده از structure ها یا class هاست.

مزیت ذخیره سازی مختصات نقاط در آرایه‌ها، در سرعت فراخوانی، سهولت کار با آنها و مصرف حافظه کم‌تر توسط آنهاست، اما رویکرد دوم و پیاده سازی نقاط با استفاده از structure یا class، به ما اجازه می‌دهد تا با استفاده از Operator Overloading اعمالی مانند جمع و تفریق را بر روی نقاط ذخیره شده امکان پذیر کنیم و یا به راحتی برای کار با اشیا ساخته شده، توابعی را در بدنه structure یا classمان تعریف کنیم.

// Some various data types which can be used to store points
/****************************************************************************/
// I. an array of floats.

float point3d[3];
/****************************************************************************/
// II. a structure holding 3 floats.

struct Point3d
{
    float x, y, z;

    // The overloaded addition operator
    Point3d operator+(const Point3d &P2) const
    {
        Point3d temp = 
        {    
            this->x + P2.x,
            this->y + P2.y,
            this->z + P2.z
        };
        
        return temp;
    }
};
/****************************************************************************/
// Using this structure, adding two points:

Point3d A, B, C;
C = A + B;
خط

خط در هندسه به معنی اتصال یا امتداد دو نقطه در یک راستا و بر روی یک صفحه است.

اما به بیان دیگر اگر یک معادله خطی را در نظر بگیریم، هر زوج مرتبی که در معادله مفروض صدق کند، به عنوان یک جواب این معادله شناخته می‌شود. حال اگر تمام جواب‌های یک معادله خطی را روی یک دستگاه مختصات رسم کنیم، طرح ایجاد شده را خط می‌نامیم. دلیل نامگذاری این دسته از معادلات به نام معادلات خطی همین موضوع است. شکل فوق جواب‌های معادله y = ۳x + ۱ را نشان می‌دهد.

به طور کلی می‌توانیم بگوییم که نمودار هر معادله به صورت Ax + By = C یک خط صاف است، اگر و فقط اگر هر دو مقدار A و B به طور همزمان برابر با صفر نباشند.

خصوصیات یک خط

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

برای مثال مهندسان راه و ساختمان برای محاسبه شیب بستر جاده، اختلاف ارتفاع مسیر جاده را بر مسافت متناظر در امتداد سطح افقی تقسیم می‌کنند و معمولا حاصل را به صورت درصدی بیان می‌کنند. برای اطلاعات عمومی بد نیست که بدانیم، معمولا در طول ساحل دریا، شیب مسیر خط آهن کمتر از ۲ درصد است و در نواحی کوهستانی ممکن است به ۴ درصد برسد و شیب بزرگراه‌ها نیز معمولا کمتر از ۵ درصد است. منبع تصویر فوق سایت The Math You Need It, When You Need It است.

برای بهتر روشن شدن موضوع لازم است مفهموم نمو را بررسی کنیم.

در واقع نمو میزان تغییرات خالص مختصات ذره‌ای است که در یک صفحه از یک مکان به مکان دیگری حرکت می‌کند. این تغییرات با تفریق مختصات نقطه آغاز از نقطه پایان محاسبه میشود. معمولا این تغییرات را با علائم Δx و Δy نشان میدهیم. علامت Δ یکی از حروف بزرگ الفبای یونانی است که معادل حرف d در زبان انگلیسی است و با توجه به حرف اول کلمه differenece به معنی تفاضل انتخاب شده است.

پس وقتی ذره‌ای از نقطه (x۱, y۱) به نقطه (x۲, y۲) حرکت می‌کند مقدار نمو آن به صورت زیر محاسبه می‌شود:

Δy = y۲ - y۱
Δx = x۲ - x۱

منبع تصویر فوق سایت Math Warehouse است.

همانطور که در تصویر مشاهده می‌کنید میزان نمو عمودی یعنی Δy برابر با ۱ و میزان نمو طولی یعنی Δ برابر با ۳ است. همانطور که گفتیم برای محاسبه شیب خط باید مقدار Δy را بر مقدار Δx تقسیم کنیم، پس شیب خط موجود شکل برابر با ۱/۳ است.

m = Δy/Δx = ۱/۳

به یاد داشت باشید که شیب خط مستقل از دو نقطه‌ای است که روی خط انتخاب می‌کنیم.

محاسبه شیب خط در کد

برای محاسبه شیب خط بین دو نقطه، با توجه به تعریف نقاط در قسمت قبل در کد داریم:

// input:  P1 – an array of 2 floats representing point 1
//         P2 – an array of 2 floats representing point 2
// output: the slope of a line between 2 given points

float SlopeBetweenPoints(float *P1, float *P2)
{
    return (P2[1] – P1[1]) / (P2[0] – P1[0]);
}
/****************************************************************************/
// input:  P1 – an structure holding 2 floats representing point 1
//         P2 – an structure holding 2 floats representing point 2
// output: the slope of a line between 2 given points

float SlopeBetweenPoints(Point2d P1, Point2d P2)
{
    return (P2.y – P1.y) / (P2.x – P1.x);
}
خطوط موازی

فرض کنید دو خط زیر که حاصل از دو معادله y = (۱/۲)x + ۱ و ۳x + ۶y = -۱۲- را داریم: شیب هر دو خط برابر با ۱/۲ است، این دو خط را موازی می‌نامیم. در ریاضیات برای خطوط، تعریفی به نام زاویه میل داریم. زاویه میل یک خط که محور xها را قطع می‌کند، کوچکترین زواویه‌ای است که اگر اندازه گیری را در خلاف عقربه‌های ساعت از محور x و در حول نقطه تقاطع انجام دهیم، به دست می‌آید. طبق این تعریف، شیب یک خط از مقدار tan این زاویه محاسبه می‌شود. پس می‌توان دو خط موازی را خطوطی در نظر گرفت که زاویه میل‌های آنها با هم برابر است.

خطوط عمود

مورد دیگری که درباره وضعیت دو خط نسبت به هم، از روابط بین مقدار شیب این دو خط قابل بررسی است، عمود بودن دو خط بر هم است. دو خط عمود بر هم یا متعامد، خطوطی هستند که حاصلضرب شیب آنها در یکدیگر، همواره برابر با ۱- باشد. شکل بالا وضعیت دو خط y = (-۳/۲)x + ۴ و y = (۲/۳)x + ۱ را نشان می‌دهد.

محاسبه شیب خط عمود در کد

برای محاسبه شیب خط عمود بر یک خط در کد، با استفاده از شیب حساب شده در قسمت قبلی می‌توانیم از تابع زیر استفاده کنیم:

// input:  slope of a line
// output: slope of the orthogonal line

float PerpendicularSlope(float slope)
{
    return –1 / slope;
}

فرض کنیم که در حال برنامه نویسی یک بازی هستیم که در آن برای ما زاویه بین راستای برخورد دو جسم مهم است، با اطلاع از این نکته که اگر دو خط بر هم عمود باشند، حاصلضرب شیب آنها برابر با ۱- است، به راحتی می‌توانیم زمانی که راستای برخورد دو جسم بر هم عمود بوده است را متوجه شویم.

// input:  slope1 – the slope of the first line
//         slope2 – the slope of our second line
// output: true if the lines are orthogonal, else false

bool ArePerpendicular(float slope1, float slope2)
{
    if(slope1 * slope2 == -1)
    {
        return true;
    }
    return false;
}
محاسبه معادله خط

اگر با دقت به شیب خطوطی که تا الان بدست آوردیم نگاه کنیم، متوجه می‌شویم که اگر برای همه معادلات این خطوط، فرم Ax + By = C را حالت استاندارد در نظر بگیریم، شیب این خطوط برابر با m = -A/B است.

مثلا در معادله ۲x + y = ۵ شیب خط برای مقادیر A = ۲ و B = ۱ برابر با m = -A/B = -۲/۱ = -۲ است.

با تمام اینها برای خطوط می‌توانیم به دو معادله پرکاربرد زیر برسیم:

معادله شیب-عرض از مبدا:
y = mx + b
این خط دارای شیب m و عرض از مبدا b است.

معادله نقطه-شیب:
y - y۱ = (x - x۱)m
این خط از نقطه (x۱, y۱) و با شیب m می‌گذرد.

بین تمام حالت‌های موجود، معادله شیب-عرض از مبدا، از بقیه پر کاربردتر است و برای ما استفاده از آن در کد، از آنجایی که در این معادله مقدار y برابر با مقدار سایر اعضای معادله است، راحت‌تر است. دقت کنید که در معادله شیب-عرض از مبدا، b بیانگر عرض از مبدا یا عرضی است که در آن خط محور yها را قطع می‌کند.

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

هر چند بعدها به بررسی این مورد خواهیم پرداخت، اما یکی از مزایای دیگر معادله نقطه-شیب قابلیت استفاده از آن در فضای سه بعدی و بر روی بردارهاست.

نکات تکمیلی شیب خطوط

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

> به روز رسانی

کاربردها در تشخیص برخورد

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

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

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

شکل زیر وضیعت دو خط y = ۳x + ۴ و y = ۲/۳x - ۲/۳ را نشان می‌دهد. طبق شکل، می‌بینیم که نقطه (۲- ,۲-) در هر دو معادله صدق می‌کند، پس این نقطه، نقطه تقاطع دو معادله است. در ضمن تقاوت شیب دو خط در این مثال را در نظر داشته باشید.

شکل زیر نمایش دهنده وضعیت دو خط ۳x + ۶y = ۶- و x + ۲y = ۲- نسبت به یکدیگر است. طبق شکل مشخص است که این بار دو خط نه تنها در یک نقطه، بلکه در مجوعه بی‌پایانی از نقاط با هم اشتراک دارند، به این دو خط، دو خط منطبق می‌گوییم. در نظر داشته باشید که شیب و عرض از مبدا این دو خط با هم برابر است.

و در پایان دو خط ۴ = y + x و ۴ = y + x- هم نسبت به هم وضعیتی مانند شکل زیر دارند: وضعیت این دو خط نسبت به هم، موازی است. شیب این دو خط هم نسبت به هم یکسان است، ولی عرض از مبدا آنها با هم متفاوت است.

پس به طور کلی یک دستگاه معادلات خطی در صفحه، می‌تواند دارای یکی از سه حالات زیر باشد:

  • تنها دارای یک جواب، در صورتی که شیب دو خط با هم برابر نباشند.
  • دارای بی‌نهایت جواب، در صورتی که دارای شیب و عرض از مبدا یکسان باشند
  • بدون جواب، در صورتی که دارای شیب یکسان باشند ولی عرض از مبدا دو خط با هم تفاوت داشته باشد.


بررسی یک مثال کاربردی:

توپی روی صحفه در حال حرکت در مسیری صاف و مستقیم است و مسیر حرکت آن با معادله x + ۲y = -۲- مشخص می‌شود، و محل قرار گیری دیوار هم روی خطی به معادله ۳x - ۶y = -۶ است. آیا این توپ با دیوار برخورد خواهد کرد؟

راه حل:

ابتدا معادله هر دو خط را به فرم شیب-عرض از مبدا در می‌آوریم.

  • x + ۲y = -۲ -> y = ۱/۲x - ۱-
  • ۳x - ۶y = -۶ -> y = ۱/۲x + ۱


مشهود است که شیب دو خط با هم مساوی و برابر مقدار ۱/۲ است. پس به سراغ عرض از مبداها می‌رویم، عرض از مبدا معادله حرکت توپ برار با ۱- و عرض از مبدا معادله محل قرارگیری دیوار برابر با ۱+ است، پس دستگاه معادله این دو خط دارای جواب نیست و دو خط با هم موازیند، پس توپ هیچگاه با دیوار برخورد نخواد کرد.

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

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

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

برای مثال دو معادله زیر را در نظر داشته باشید:

  • ۳x + ۲y = ۱۰
  • ۴x + ۳y = ۶


برای تبدیل این سیستم به یک سیستم ساده‌تر، ابتدا تلاش می‌کنیم تا با استفاده از عمل سطری ضرب یک سطر در یک عدد غیر صفر، ضریب یکی از دو متغیر را در هر دو معادله با یکدیگر برابر کنیم. برای مثال، به سراغ y می‌رویم، برای یکسان سازی ضریب y در هر دو معادله کافی است تا معادله اول را در ۳ و معادله دوم را در ۲ ضرب کنیم. دستگاه جدید را به شکل زیر بازنویسی می‌کنیم:

  • ۹x + ۶y = ۳۰
  • ۸x + ۶y = ۱۲


قدم بعدی ترکیب کردن این دو معادله با هم و تبدیل آنها به یک معادله است. برای انجام کار می‌توان یک معادله را از معادله دیگر کم کرد یا دو معادله را با یکدیگر جمع کرد. برای نمونه، در مثال بالا، معادله دوم را از معادله اول کم می‌کنیم و داریم:

  • ۹x + ۶y = ۳۰
  • (۸x + ۶y = ۱۲)-
  • x + ۰y = ۱۸
  • x = ۱۸


معادله به دست آمده، ترکیب خطی دو معادله نامیده می‌شود، حال از معادله به دست آمده می‌دانیم که مقدار x در جواب نهایی، بابر با ۱۸ است. حالا می‌توانیم با جایگذاری این مقدار در یکی از معادلات اولیه، مقدار متغییر دیگر را بدست آوریم. پس داریم:

  • ۵۴ + ۲y = ۱۰
  • y = -۲۲


پس جواب این دستگاه معادلات برابر با (۱۸ ,۲۲) است و این نقطهُ محل برخورد دو معادله خط ما را نشان می‌دهد.

۲جایگذاری: جایگذاری روش دیگری است که می‌تواند در حل دستگاه‌ معادلات ما را کمک کند، باز هم در هر مرحله فقط قادر به محاسبه جواب یکی از متغیرها هستیم. برای استفاده از جایگذاری، ابتدا باید یکی از معادلات را بر حسب یکی از متغیرها حل کنیم، و سپس، جواب حاصل را به عنوان مقدار آن متغیر در سایر معادلات جایگذاری کنیم.

فرض کنید که دو معادله زیر را داریم:

  • x + ۲y = ۵
  • ۳x -۲y = -۱


معادله اول را بر حسب x بدست می‌آوریم و داریم:

  • x = -۲y + ۵


حال با جایگذاری مقدار بدست آمده برای x در معادله دوم داریم:

  • ۶y + ۱۵ -۲y = -۱-
  • ۸y = -۱۶-
  • y = ۲


حال با به دست آمدن مقدار y و جایگذاری مقدار آن در معادله اولیه، می‌توانیم مقدار x را پیدا کنیم:

  • x = -۲(۲) + ۵
  • x = ۱


پس جواب معادله مورد نظر نقطه (۲ ,۱) است.

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

ظاهرا حالا زمان مناسبی برای این خواهد بود که در کد هم با استفاده از روش‌های توضیح داده شده، امکان برخورد یا محل برخورد دو خط را بررسی کنیم.

طبق مواردی که تا اینجا بررسی کردیم، می‌دانیم که معادله یک خط و تمام نقاط روی آن را می‌توان به از فرم زیر بدست آورد:

  • (y - y۱ = m(x - x۱


اگر در معادله بالا m را برابر با شیب خط در نظر بگیریم و نقطه (x۱, y۱) را هر نقطه دلخواهی روی خط لحاظ کنیم و معادله‌های دو خط متفاوت را به شکل زیر بازنویسی کنیم، خواهیم داشت:

  • y = m۱(x - x۱) + y۱
  • y = m۲(x - x۲) + y۲


با برابر قرار دادن دو معادله بالا و حل معادله جدید برای x خواهیم داشت:

  • (x = (m۱x۱ - m۲x۲ + y۲ - y۲) / (m۱ - m۲


حالا تابعی را معرفی می‌کنیم با گرفتن دو خط به عنوان ورودی، نقطه برخورد این دو خط با یکدیگر را محاسبه می‌کند، اما قبل از استفاده از این تابع لازم است تا مطمئن شویم که دو خط با هم موازی نیستند:

//input: L1Point - a 2D point along our first line
//       L1Slope - the slope of our first line
//       L2Point - a 2D point along our second line
//       L2Slope - the slope of our second line
//output: an array of float holding a point

float *LineIntersect(Point2d L1Point, float L1Slope,
    				 Point2d L2Point, float L2Slope)
{
    float temp[2] = { 0, 0 };
    temp[0] = ((L1Slope * L1Point.x) - (L2Slope * L2Point.x) +
        		L2Point.y - L1Point.y) / (L1Slope - L2Slope);

    temp[1] = L1Slope * temp[0] - L1Slope *L1Point.x + L1Point.y;

    return temp;
}

کد کامل این مطلب را می‌توانید از اینجا دریافت کنید.