إيجاد نقطة تقاطع خطين مستقيمين

تعثر هذه الخوارزمية على نقطة تقاطع خطين مستقيمين، فلو افترضنا أنّ النقطتين A و B تمثّلان الخط المستقيم AB والنقطتين P و Q تمثّلان الخط المستقين PQ، فإنّ الخوارزمية تعيد إحداثيات نقطة تقاطع هذين المستقيمين.

مثال:

المدخلات : A = (1, 1), B = (4, 4)
        C = (1, 8), D = (2, 4)

المخرجات: The intersection of the given lines 
         AB and CD is: (2.4, 2.4)

المدخلات : A = (0, 1), B = (0, 4)
        C = (1, 8), D = (1, 4)
المخرجات : The given lines AB and CD are parallel.

لو فرضنا وجود نقطتين لهما الإحداثيات (x1, y1) و (x2, y2)، فإنّ المعادلتين اللتين تمثّلان الخطين المستقيمين الناشئين من هاتين النقطتين هما:

a1x + b1y = c1            (1)
a2x + b2y = c2            (2)

يمثّل حل هاتين المعادلتين نقطة تقاطع الخطين المستقيمين. ولإيجاد حلّ هاتين المعادلتين تُضرب المعادلة الأولى بالمقدار b2 والمعادلة الثانية بالمقدار b1 لنحصل على:

a1b2x + b1b2y = c1b2
a2b1x + b2b1y = c2b1

وبطرح المعادلة الثانية من المعادلة الأولى نحصل على:

(a1b2 – a2b1) x = c1b2 – c2b1

يمكن الحصول على قيمة الإحداثي x لنقطة التقاطع بحلّ هذه المعادلة، ويمكن الحصول على قيمة الإحداثي y بنفس الطريقة.

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

min (x1, x2) <= x <= max (x1, x2)
min (y1, y2) <= y <= max (y1, y2)

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

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

• C++‎:

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

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

// تعرض الدالة إحداثيات النقطة المعطاة
void displayPoint(pdd P) 
{ 
	cout << "(" << P.first << ", " << P.second 
		<< ")" << endl; 
} 

pdd lineLineIntersection(pdd A, pdd B, pdd C, pdd D) 
{ 
	// يمثّل الخطّ AB بالمعادلة a1x + b1y = c1
	double a1 = B.second - A.second; 
	double b1 = A.first - B.first; 
	double c1 = a1*(A.first) + b1*(A.second); 

	// يمثّل الخطّ CD بالمعادلة a2x + b2y = c2
	double a2 = D.second - C.second; 
	double b2 = C.first - D.first; 
	double c2 = a2*(C.first)+ b2*(C.second); 

	double determinant = a1*b2 - a2*b1; 

	if (determinant == 0) 
	{ 
		// FLT_MAX إذا كان الخطان متوازيين تعيد الدالة الزوج
		return make_pair(FLT_MAX, FLT_MAX); 
	} 
	else
	{ 
		double x = (b2*c1 - b1*c2)/determinant; 
		double y = (a1*c2 - a2*c1)/determinant; 
		return make_pair(x, y); 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	pdd A = make_pair(1, 1); 
	pdd B = make_pair(4, 4); 
	pdd C = make_pair(1, 8); 
	pdd D = make_pair(2, 4); 

	pdd intersection = lineLineIntersection(A, B, C, D); 

	if (intersection.first == FLT_MAX && 
		intersection.second==FLT_MAX) 
	{ 
		cout << "The given lines AB and CD are parallel.\n"; 
	} 

	else
	{ 
	// ملاحظة: يجب إجراء عملية تحقق إضافية إن كان المطلوب
	// إيجاد نقطة تقاطع قطعتين مستقيمتين
		cout << "The intersection of the given lines AB "
				"and CD is: "; 
		displayPoint(intersection); 
	} 

	return 0; 
}

• بايثون:

import sys
import decimal

# تعرض الدالة إحداثيات النقطة المعطاة
def displayPoint(pdd):
    print("{}, {}".format(pdd[0], pdd[1]))

def lineLineIntersection(A, B, C, D):
    # يمثّل الخطّ AB بالمعادلة a1x + b1y = c1
    a1 = B[1] - A[1]
    b1 = A[0] - B[0]
    c1 = a1 * A[0] + b1 * A[1]

   	# يمثّل الخطّ CD بالمعادلة a2x + b2y = c2
    a2 = D[1] - C[1]
    b2 = C[0] - D[0]
    c2 = a2 * C[0] + b2 * C[1]

    determinant = decimal.Decimal(a1 * b2 - a2 * b1)
	
    # MAX_EMAX إذا كان الخطان متوازيين تعيد الدالة الزوج

    if (determinant == decimal.Decimal('0')):
        return (decimal.MAX_EMAX, decimal.MAX_EMAX)
    else:
        x = (b2 * c1 - b1 * c2)/determinant
        y = (a1 * c2 - a2 - c1)/determinant
        return (decimal.Decimal(x), decimal.Decimal(y))


# اختبار الدوال السابقة

A = (decimal.Decimal('1.0'), decimal.Decimal('1.0'))
B = (decimal.Decimal('4.0'), decimal.Decimal('4.0'))
C = (decimal.Decimal('1.0'), decimal.Decimal('8.0'))
D = (decimal.Decimal('2.0'), decimal.Decimal('4.0'))

intersection = lineLineIntersection(A, B, C, D)

if (intersection[0] == decimal.MAX_EMAX and intersection[1] == decimal.MAX_EMAX):
    print("The given lines AB and CD are parallel")
else:
    # ملاحظة: يجب إجراء عملية تحقق إضافية إن كان المطلوب
	# إيجاد نقطة تقاطع قطعتين مستقيمتين
    print("The intersection of the given lines AB and CD is: ")
    displayPoint(intersection)

• جافا:

// يستخدم هذا الصنف لتخزين قيمتي الإحداثيين السيني والصادي لنقطة معينة 
class Point 
{ 
	double x,y; 
	
	public Point(double x, double y) 
	{ 
		this.x = x; 
		this.y = y; 
	} 
	
	// يعرض التابع إحداثيات النقطة المعطاة 
	static void displayPoint(Point p) 
	{ 
		System.out.println("(" + p.x + ", " + p.y + ")"); 
	} 
} 

class Test 
{	 
	static Point lineLineIntersection(Point A, Point B, Point C, Point D) 
	{ 
		// يمثّل الخطّ AB بالمعادلة a1x + b1y = c1 
		double a1 = B.y - A.y; 
		double b1 = A.x - B.x; 
		double c1 = a1*(A.x) + b1*(A.y); 
	
		// يمثّل الخطّ CD بالمعادلة a2x + b2y = c2 
		double a2 = D.y - C.y; 
		double b2 = C.x - D.x; 
		double c2 = a2*(C.x)+ b2*(C.y); 
	
		double determinant = a1*b2 - a2*b1; 
	
		if (determinant == 0) 
		{ 
			// FLT_MAX إذا كان الخطان متوازيين تعيد الدالة الزوج 
			return new Point(Double.MAX_VALUE, Double.MAX_VALUE); 
		} 
		else
		{ 
			double x = (b2*c1 - b1*c2)/determinant; 
			double y = (a1*c2 - a2*c1)/determinant; 
			return new Point(x, y); 
		} 
	} 
	
	// اختبار التوابع السابقة 
	public static void main(String args[]) 
	{ 
		Point A = new Point(1, 1); 
		Point B = new Point(4, 4); 
		Point C = new Point(1, 8); 
		Point D = new Point(2, 4); 
	
		Point intersection = lineLineIntersection(A, B, C, D); 
	
		if (intersection.x == Double.MAX_VALUE && 
			intersection.y == Double.MAX_VALUE) 
		{ 
			System.out.println("The given lines AB and CD are parallel."); 
		} 
	
		else
		{ 
			// ملاحظة: يجب إجراء عملية تحقق إضافية إن كان المطلوب
			// إيجاد نقطة تقاطع قطعتين مستقيمتين 
		System.out.print("The intersection of the given lines AB " + 
							"and CD is: "); 
		Point.displayPoint(intersection); 
		} 
	} 
}

مصادر

• صفحة Program for Point of Intersection of Two Lines في توثيق الخوارزميات في موقع GeeksforGeeks.