إيجاد الخط الذي يمرّ بنقطتين

تعثر هذه الخوارزمية على معادلة الخط المستقيم الذي يمرّ بنقطتين (لتكونا P و Q)في مستوى الإحداثيات.

يمكن استخدام هذه الخوارزمية في العديد من المسائل الهندسية، مثل إيجاد نقطة تقاطع خطين مستقيمين وإيجاد مركز الدائرة المحيطة بمثلث circumcenter وإيجاد مركز الدائرة التي يحيط بها المثلث incenter وغيرها.

مثال:

Input : P(3, 2)
        Q(2, 6)
Output : 4x + 1y = 14

Input : P(0, 1)
        Q(2, 4)
Output : 3x + -2y = -2

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

لنفترض أنّ لدينا النقطتين P(x1, y1)‎ و Q(x2, y2)‎.

يمكن تمثيل أيّ خطّ مستقيم بالمعادلة الرياضية العامة:

ax + by = c

ولو فرضنا أنّ النقطتين السابقتين يحقّقان هذه المعادلة، فسنحصل على:

ax1 + by1 = c
ax2 + by2 = c

يمكن حل هاتين المعادلتين للحصول على قيم a و b و c:

a = y2 - y1
b = x1 - x2
c = ax1 + by1

يمكن اشتقاق هذه القيم عن طريق الحصول على الميل slope بطريقة مباشرة ثم إيجاد قيمة القطع intercept للخط المستقيم. ويمكن اتباع الطريقة التالية لاشتقاق هذه القيم:

ax1 + by1 = c ...(i)
ax2 + by2 = c ...(ii)

نساوي المعادلة الأولى بالمعادلة الثانية:

ax1 + by1 = ax2 + by2
=> a(x1 - x2) = b(y2 - y1)

وبمساواة الجانب الأيمن من المعادلة مع الجانب الأيسر منها يمكن الحصول على:

a = (y2 - y1)
AND
b = (x1 - x2)

وبهذا:

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

وبوضع هذه القيم في المعادلة الأولى نحصل على:

c = ax1 + by1

وهكذا نحصل على قيم a و b و c والذي يعني أنّنا حصلنا على الخط في مستوى الإحداثيات.

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

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

• C++‎:

#include <iostream> 
using namespace std; 

// يستخدم زوج القيم هذا لتخزين الإحداثيين السيني والصادي للنقة
#define pdd pair<double, double> 

// تحسب الدالة معادلة الخط المستقيم المارّ بنقطتين
void lineFromPoints(pdd P, pdd Q) 
{ 
	double a = Q.second - P.second; 
	double b = P.first - Q.first; 
	double c = a*(P.first) + b*(P.second); 

	if(b<0) 
	{ 
	cout << "The line passing through points P and Q is: "
		<< a << "x - " << b << "y = " << c << endl; 
	} 
	else
	{ 
	cout << "The line passing through points P and Q is: "
		<< a << "x + " << b << "y = " << c << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	pdd P = make_pair(3, 2); 
	pdd Q = make_pair(2, 6); 
	lineFromPoints(P, Q); 
	return 0; 
}

• بايثون:

# تحسب الدالة معادلة الخط المستقيم المارّ بنقطتين
def lineFromPoints(P,Q): 

	a = Q[1] - P[1] 
	b = P[0] - Q[0] 
	c = a*(P[0]) + b*(P[1]) 

	if(b<0): 
		print("The line passing through points P and Q is:", 
			a ,"x ",b ,"y = ",c ,"\n") 
	else: 
		print("The line passing through points P and Q is: ", 
			a ,"x + " ,b ,"y = ",c ,"\n") 

# اختبار الدالة السابقة
if __name__=='__main__': 
	P = [3, 2] 
	Q = [2, 6] 
	lineFromPoints(P,Q)

• جافا:

class GFG 
{ 

// يستخدم زوج القيم هذا لتخزين الإحداثيين السيني والصادي للنقطة
static class Pair 
{ 
	int first, second; 

		public Pair(int first, int second) 
		{ 
			this.first = first; 
			this.second = second; 
		} 
	
	
} 

// تحسب الدالة معادلة الخط المستقيم المار بنقطتين
static void lineFromPoints(Pair P, Pair Q) 
{ 
	int a = Q.second - P.second; 
	int b = P.first - Q.first; 
	int c = a*(P.first) + b*(P.second); 

	if(b < 0) 
	{ 
		System.out.println("The line passing through points P and Q is: "
						+ a + "x " + b + "y = " + c); 
	} 
	else
	{ 
		System.out.println("The line passing through points P and Q is: "
						+ a + "x + " + b + "y = " + c); 
	} 
} 

// اختبار التوابع السابقة
public static void main(String[] args) 
{ 
	Pair P = new Pair(3, 2); 
	Pair Q = new Pair(2, 6); 
	lineFromPoints(P, Q); 
} 
}

مصادر

• صفحة Program to find line passing through 2 Points في توثيق الخوارزميات في موقع GeeksforGeeks.