التحقق من وجود نقطة معينة في قطاع الدائرة

من موسوعة حسوب
اذهب إلى: تصفح، ابحث

تتحقق هذه الخوارزمية من وجود النقطة المعطاة في قطاع الدائرة، وذلك بافتراض أن مركز الدائرة يقع في نقطة الأصل (0,0). مدخلات الخوارزمية هي زاوية بداية قطاع الدائرة وحجم القطاع كنسبة مئوية.

أمثلة:

Input :  Radius = 8 
         StartAngle = 0 
         Percentage = 12 
         x = 3 y = 4 
Output : Point (3, 4) exists in the circle 
         sector

Input : Radius = 12 
        Startangle = 45
        Percentage = 25  
        x = 3 y = 4 
Output : Point (3, 4) does not exist in 
         the circle sector

خطوات الخوارزمية

زاوية بداية القطاع هي 0 درجة، ونصف القطر هو r والنسبة المئوية للجزء الملون هي ‎12%. يمكن حساب زاوية نهاية القطاع بواسطة العلاقة:

360/النسبة المئوية + زاوية البداية

يمكن التحقق من وجود نقطة ذات الإحداثيات (x,y) في قطاع دائرة (مركزها نقطة الأصل) بحساب الإحداثيات القطبية لتلك النقطة ثم المرور عبر الخطوات السابقة:

1- تحويل النقطتين x, y إلى الإحداثيات القطبية باستخدام العلاقتين التاليتين:

Angle = atan(y/x);
Radius = sqrt(x * x + y * y);
2 - يجب أن تكون الزاوية المحسوبة بين زاوية بداية المقطع وزاوية نهايته، وأن يكون نصف القطر المحسوب بين 0 ونصف قطر الدائرة.

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

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

  • C++‎:
#include<bits/stdc++.h> 
using namespace std; 

void checkPoint(int radius, int x, int y, float percent, 
										float startAngle) 
{ 
	// حساب زاوية نهاية القطاع
	float endAngle = 360/percent + startAngle; 

	// حساب الإحداثيات القطبية
	float polarradius = sqrt(x*x+y*y); 
	float Angle = atan(y/x); 

	// التحقق من أن نصف القطر القطبي أقل من نصف قطر الدائرة
	// والتحقق من أنّ الزاوية المحسوبة تقع بين زاويتي بدء القطاع ونهاية القطاع
	if (Angle>=startAngle && Angle<=endAngle && polarradius<radius) 
		printf("Point (%d, %d) exist in the circle sector\n", x, y); 
	else
		printf("Point (%d, %d) does not exist in the circle sector\n", x, y); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int radius = 8, x = 3, y = 4; 
	float percent = 12, startAngle = 0; 
	checkPoint(radius, x, y, percent, startAngle); 
	return 0; 
}
  • بايثون:
import math 

def checkPoint(radius, x, y, percent, startAngle): 

	# حساب زاوية نهاية القطاع
	endAngle = 360 / percent + startAngle 

	# حساب الإحداثيات القطبية 
	polarradius = math.sqrt(x * x + y * y) 
	Angle = math.atan(y / x) 

	# التحقق من أن نصف القطر القطبي أقل من نصف قطر الدائرة
	# والتحقق من أنّ الزاوية المحسوبة تقع بين زاويتي بدء القطاع ونهاية القطاع
	if (Angle >= startAngle and Angle <= endAngle 
						and polarradius < radius): 
		print("Point (", x, ",", y, ") "
			"exist in the circle sector") 
	else: 
		print("Point (", x, ",", y, ") "
			"does not exist in the circle sector") 

# Driver code 
radius, x, y = 8, 3, 4
percent, startAngle = 12, 0

checkPoint(radius, x, y, percent, startAngle)
  • جافا:
class GFG 
{ 
static void checkPoint(int radius, int x, int y, float percent, 
										float startAngle) 
{ 

	// حساب زاوية نهاية القطاع
	float endAngle = 360/percent + startAngle; 

	// حساب الإحداثيات القطبية 
	double polarradius = Math.sqrt(x*x+y*y); 
	double Angle = Math.atan(y/x); 

	// التحقق من أن نصف القطر القطبي أقل من نصف قطر الدائرة
	// والتحقق من أنّ الزاوية المحسوبة تقع بين زاويتي بدء القطاع ونهاية القطاع
	if (Angle>=startAngle && Angle<=endAngle && polarradius<radius) 
		System.out.print("Point"+"("+x+","+y+")"+ 
		" exist in the circle sector\n"); 
	else
		System.out.print("Point"+"("+x+","+y+")"+ 
		" exist in the circle sector\n"); 
} 

// اختبار التابع السابق
public static void main(String arg[]) 
{ 
	int radius = 8, x = 3, y = 4; 
	float percent = 12, startAngle = 0; 
	checkPoint(radius, x, y, percent, startAngle); 
} 
}

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

Point(3, 4) exists in the circle sector
Time complexity = O(1)

مصادر