التحقق من مرور الخط المستقيم عبر نقط الأصل

تتحقق هذه الخوارزمية من مرور الخط المستقيم ذي الإحداثيات (x1, y1) و (x2, y2) عبر نقطة الأصل ذات الإحداثيات (0,0).

مثال:

Input : (x1, y1) = (10, 0)
        (x2, y2) = (20, 0)
Output : Yes

من الواضح أنّ الخطّ المستقيم في المثال السابق يمرّ عبر نقطة الأصل وذلك لأنّ الخطّ المستقيم يقع على المحور السيني فقط.

Input : (x1, y1) = (1, 28)
        (x2, y2) = (2, 56)
Output : Yes

مبدأ عمل الخوارزمية

يمكن التعبير عن الخط المستقيم المارّ عبر نقطتين إحادثياتهما هي (x1, y1) و (x2, y2) بالمعادلة التالية:

y-y1 = ((y2-y1) / (x2-x1))(x-x1) + c

وإن كان الخط المستقيم يمرّ بنقطة الأصل فهذا يعني أنّ c = 0 فتصبح المعادلة بذلك:

y-y1 = ((y2-y1) / (x2-x1))(x-x1)

ولما كانت إحداثيات نقطة الأصل هي (0, 0) فإنّ المعادلة تصبح:

x1(y2-y1) = y1(x2-x1)

إنّ حقّق الخط المستقيم المعادلة السابقة فهذا يعني أنّه يمر عبر نقطة الأصل.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

bool checkOrigin(int x1, int y1, int x2, int y2) 
{ 
return (x1 * (y2 - y1) == y1 * (x2 - x1)); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	if (checkOrigin(1, 28, 2, 56) == true) 
	cout << "Yes"; 
	else
	cout << "No"; 
	return 0; 
}

• بايثون:

def checkOrigin(x1, y1, x2, y2): 
	return (x1 * (y2 - y1) == y1 * (x2 - x1)) 
	
# اختبار الدالة السابقة
if (checkOrigin(1, 28, 2, 56) == True): 
	print("Yes") 
else: 
	print("No")

• جافا:

import java.io.*; 

class GFG { 
	
	static boolean checkOrigin(int x1, int y1, 
									int x2, int y2) 
	{ 
		return (x1 * (y2 - y1) == y1 * (x2 - x1)); 
	} 

	// اختبار التابع السابق
	public static void main (String[] args) 
	{ 
		if (checkOrigin(1, 28, 2, 56) == true) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

مصادر

• صفحة Check if a line passes through the origin في توثيق الخوارزميات في موقع GeeksforGeeks.