التحقق من وقوع ثلاث نقاط على استقامة واحدة

تتحقق هذه الخوارزمية من وقوع ثلاث نقاط على استقامة واحدة (colinear).

مثال:

Input : (1, 1), (1, 4), (1, 5)
Output : Yes 
The points lie on a straight line

Input : (1, 5), (2, 5), (4, 6)
Output : No 
The points do not lie on a straight line

دورة علوم الحاسوب

• 57 ساعة فيديو تدريبية
• من الصفر دون الحاجة لخبرة مسبقة
• شهادة معتمدة من أكاديمية حسوب
• متابعة أثناء الدورة من فريق مختص

اشترك الآن

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

هناك طريقتان يمكن من خلالهما معرفة ما إذا كانت النقاط الثلاثة المعطاة واقعة على استقامة واحدة.

الطريقة الأولى

تقع ثلاث نقاط على استقامة واحدة إذا كانت مساحة المثلث الذي يتكوّن من هذه النقاط تساوي صفرًا؛ لذا يمكن التحقق من مساحة المثلث لمعرفة ما إذا كانت النقاط الثلاثة على استقامة واحدة أم لا.

يمكن استخدام المعادلة التالية لإيجاد مساحة المثلث:

0.5 * [x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)]

تمثّل المعادلة أعلاه نصف قيمة المحدّد determinant للمصفوفة التالية:

x1 x2 x3
y1 y2 y3
1   1  1

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

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

• C++‎:

#include <bits/stdc++.h> 
#include <math.h> 
#include <stdlib.h> 

using namespace std; 
void collinear(int x1, int y1, int x2, 
			int y2, int x3, int y3) 
{ 
	// حساب مساحة المثلث 
	// لا تُضرب المعادلة بالمقدار 0.5
	// وذلك لتجنب الأخطاء الحاصلة في حسابات الفاصلة العائمة
	int a = x1 * (y2 - y3) + 
			x2 * (y3 - y1) + 
			x3 * (y1 - y2); 

	if (a == 0) 
		cout << "Yes"; 
	else
		cout << "No"; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int x1 = 1, x2 = 1, x3 = 1, 
		y1 = 1, y2 = 4, y3 = 5; 
	collinear(x1, y1, x2, y2, x3, y3); 
	return 0; 
}

• بايثون:

def collinear(x1, y1, x2, y2, x3, y3): 
	
	""" حساب مساحة المثلث 
		لا تُضرب المعادلة بالمقدار 0.5
		وذلك لتجنب الأخطاء الحاصلة في حسابات الفاصلة العائمة """
	a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) 

	if (a == 0): 
		print "Yes"
	else: 
		print "No"

# اختبار الدالة السابقة
x1, x2, x3, y1, y2, y3 = 1, 1, 1, 1, 4, 5
collinear(x1, y1, x2, y2, x3, y3)

• جافا:

class GFG 
{ 
	
	static void collinear(int x1, int y1, int x2, 
						int y2, int x3, int y3) 
	{ 
		
			// حساب مساحة المثلث 
			// لا تُضرب المعادلة بالمقدار 0.5
			// وذلك لتجنب الأخطاء الحاصلة في حسابات الفاصلة العائمة
		int a = x1 * (y2 - y3) + 
				x2 * (y3 - y1) + 
				x3 * (y1 - y2); 
	
		if (a == 0) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
		
	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int x1 = 1, x2 = 1, x3 = 1, 
			y1 = 1, y2 = 4, y3 = 5; 
							
		collinear(x1, y1, x2, y2, x3, y3); 

	} 
}

الطريقة الثانية

يجب أن يكون ميل أيّ زوج من النقاط الثلاثة مساويًا لميل الزوج الآخر من النقاط، لتكون النقاط الثلاثة على استقامة واحدة.

فعلى سبيل المثال إن كان لدينا النقاط (x1, y1) و (x2, y2) و (x3, y3) فيجب أن يكون مي الخط المستقيم الرابط بين النقطتين (x2, y2) و (x3, y3) مساويًا لميل الخط المستقيم الرابط بين النقطتين (x1, y1) و (x2, y2).

أي أنّ:

(y3 - y2)/(x3 - x2) = (y2 - y1)/(x2 - x1)

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

• C++‎:

#include <stdio.h> 
#include <math.h> 

void collinear(int x1, int y1, int x2, 
			int y2, int x3, int y3) 
{ 
	if ((y3 - y2) * (x2 - x1) == 
		(y2 - y1) * (x3 - x2)) 
		printf("Yes"); 
	else
		printf("No"); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int x1 = 1, x2 = 1, x3 = 0, 
		y1 = 1, y2 = 6, y3 = 9; 
	collinear(x1, y1, x2, y2, x3, y3); 
	return 0; 
}

• بايثون:

def collinear(x1, y1, x2, y2, x3, y3): 
	
	if ((y3 - y2)*(x2 - x1) == (y2 - y1)*(x3 - x2)): 
		print ("Yes") 
	else: 
		print ("No") 

# اختبار الدالة السابقة
x1, x2, x3, y1, y2, y3 = 1, 1, 0, 1, 6, 9
collinear(x1, y1, x2, y2, x3, y3);

• جافا:

import java.io.*; 

class GFG { 

static void cool_line(int x1, int y1, int x2, 
			int y2, int x3, int y3) 
{ 
	if ((y3 - y2) * (x2 - x1) == 
		(y2 - y1) * (x3 - x2)) 
		System.out.println("Yes"); 
	else
		System.out.println("No"); 
} 

// اختبار التابع السابق
	
	public static void main (String[] args) { 
		int a1 = 1, a2 = 1, a3 = 0, 
		b1 = 1, b2 = 6, b3 = 9; 
	cool_line(a1, b1, a2, b2, a3, b3); 
		
		
	} 
}

مصادر

• صفحة Program to check if three points are collinear في توثيق الخوارزميات في موقع GeeksforGeeks.