Algorithms/rectangle overlap

تتحقق هذه الخوارزمية من تداخل مستطيلين بعضهما ببعض، ويمكن تمثيل المستطيل بزوج من الإحداثيات هما، إحداثيات الركن العلوي الأيسر، وإحداثيات الركن السفلي الأيمن. وهذا يعني أنّ هذه الخوارزمية ستتطلب أربعة إحداثيات هي:

l1: إحداثيات الركن العلوي الأيسر للمستطيل الأول
r1: إحداثيات الركن السفلي الأيمن للمستطيل الأول

l2: إحداثيات الركن العلوي الأيسر للمستطيل الثاني
r2: إحداثيات الركن السفلي الأيمن للمستطيل الثاني

يكون مستطيلان متداخلين عندما يتحقق أحد الشرطين التاليين:

1. يكون أحد المستطيلين فوق الحافة العلوية للمستطيل الآخر.
2. يكون أحد المستطيلين على الجانب الأيسر للحافة اليسرى للمستطيل الآخر.

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

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

• C++‎:

#include<bits/stdc++.h> 

struct Point 
{ 
	int x, y; 
}; 

// تعيد الدالة قيمة صحيحة إن تداخل المستطيلان المعطيان
bool doOverlap(Point l1, Point r1, Point l2, Point r2) 
{ 
	// إن كان أحد المستطيلين على يسار المستطيل الآخر
	if (l1.x > r2.x || l2.x > r1.x) 
		return false; 

	// إن كان المستطيلين فوق المستطيل الآخر
	if (l1.y < r2.y || l2.y < r1.y) 
		return false; 

	return true; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	Point l1 = {0, 10}, r1 = {10, 0}; 
	Point l2 = {5, 5}, r2 = {15, 0}; 
	if (doOverlap(l1, r1, l2, r2)) 
		printf("Rectangles Overlap"); 
	else
		printf("Rectangles Don't Overlap"); 
	return 0; 
}

• بايثون:

class Point: 
	def __init__(self, x, y): 
		self.x = x 
		self.y = y 

# تعيد الدالة قيمة صحيحة إن تداخل المستطيلان المعطيان
def doOverlap(l1, r1, l2, r2): 
	
	# إن كان أحد المستطيلين إلى يسار المستطيل الآخر
	if(l1.x > r2.x or l2.x > r1.x): 
		return False

	# إن كان أحد المستطيلين فوق المستطيل الآخر
	if(l1.y < r2.y or l2.y < r1.y): 
		return False

	return True

# اختبار الدالة السابقة
if __name__ == "__main__": 
	l1 = Point(0, 10) 
	r1 = Point(10, 0) 
	l2 = Point(5, 5) 
	r2 = Point(15, 0) 

	if(doOverlap(l1, r1, l2, r2)): 
		print("Rectangles Overlap") 
	else: 
		print("Rectangles Don't Overlap")

• جافا:

class GFG { 

static class Point { 

		int x, y; 
	} 

// تعيد الدالة قيمة صحيحة إن تداخل المستطيلان المعطيان
static boolean doOverlap(Point l1, Point r1, Point l2, Point r2) { 
		// إن كان أحد المستطيلين إلى يسار المستطيل الآخر 
		if (l1.x > r2.x || l2.x > r1.x) { 
			return false; 
		} 

		// إن كان أحد المستطيلين فوق المستطيل الآخر
		if (l1.y < r2.y || l2.y < r1.y) { 
			return false; 
		} 

		return true; 
	} 

	/* اختبار التابع السابق */
	public static void main(String[] args) { 
		Point l1 = new Point(),r1 = new Point(), 
				l2 = new Point(),r2 = new Point(); 
		l1.x=0;l1.y=10; r1.x=10;r1.y=0; 
		l2.x=5;l2.y=5; r2.x=15;r2.y=0; 

		if (doOverlap(l1, r1, l2, r2)) { 
			System.out.println("Rectangles Overlap"); 
		} else { 
			System.out.println("Rectangles Don't Overlap"); 
		} 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Rectangles Overlap

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(1)‎ وذلك لعدم احتواء الشيفرة على حلقات تكرارية أو استدعاءات تعاودية.

مصادر

• صفحة Find if two rectangles overlap في توثيق الخوارزميات في موقع GeeksforGeeks.