عرض مصدر Algorithms/point inside triangle

<noinclude>{{DISPLAYTITLE:التحقق من أن نقطة معينة موجودة داخل المثلث}}</noinclude>
تتحقق هذه الخوارزمية من وجود النقطة المعطاة بإحداثياتها (لتكن P) داخل المثلث الذي تحدده أحداثيات أركانه.

'''مثال:'''

النقطة P موجودة داخل المثلث وتعيد الخوارزمية قيمة صحيحة، أما النقطة P‎'‎ فتقع خارج المثلث وتعيد الخوارزمية قيمة خاطئة.

<source lang="text">              B(10,30)
                / \
               /   \
              /     \
             /   P   \      P'
            /         \
     A(0,0) ----------- C(20,0) </source>
== مبدأ عمل الخوارزمية ==

لنفترض أنّ إحادثيات أركان المثلث الثلاثة هي <code>(x1, y1)</code> و <code>(x2, y2)</code> و <code>(x3, y3)</code>، وأنّ إحداثيات النقطة المعطاة هي <code>(x, y)</code>.

# نحسب مساحة المثلث المعطى وذلك باستخدام العلاقة التالية: <code>A = [ x1(y2 – y3) + x2(y3 – y1) + x3(y1-y2)]/2</code>.
# نحسب مساحة المثلث <code>PAB</code> باستخدام العلاقة السابقة، ولتكن هذه المساحة A1.
# نحسب مساحة المثلث <code>PBC</code> باستخدام العلاقة السابقة، ولتكن هذه المساحة A2.
# نحسب مساحة المثلث <code>PAC</code> باستخدام العلاقة السابقة، وتلكن هذه المساحة A3.
# إن كانت النقطة P داخل المثلث فيجب أن تتحقق العلاقة التالية: <code>A1 + A2 + A3 = A</code>.

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

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

* C++‎:

<source lang="c++">#include <bits/stdc++.h> 
using namespace std; 

/* دالة مساعدة لحساب مساحة المثلث المتشكل من النقاط:
(x1, y1), (x2, y2) و (x3, y3) */
float area(int x1, int y1, int x2, int y2, int x3, int y3) 
{ 
return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0); 
} 

/* دالة مساعدة للتحقق من أنّ النقطة P تقع ضمن حدود المثلث المتشكّل من النقاطة الثلاثة المعطاة */
bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y) 
{ 
/* ABC حساب مساحة المثلث */
float A = area (x1, y1, x2, y2, x3, y3); 

/* PBC حساب مساحة المثلث */
float A1 = area (x, y, x2, y2, x3, y3); 

/* PAC حساب مساحة المثلث */
float A2 = area (x1, y1, x, y, x3, y3); 

/* PAB حساب مساحة المثلث */
float A3 = area (x1, y1, x2, y2, x, y); 
	
/* التحقق من أنّ مجموع المساحات الثلاثة يساوي مساحة المثلث الأصلي */
return (A == A1 + A2 + A3); 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
/* P(10, 15) التحقق من أنّ النقطة 
موجودة داخل المثلث المتشكّل من النقاط
A(0, 0), B(20, 0) و C(10, 30) */
if (isInside(0, 0, 20, 0, 10, 30, 10, 15)) 
	printf ("Inside"); 
else
	printf ("Not Inside"); 

return 0; 
} 
</source>
* بايثون:

<source lang="python"># دالة مساعدة لحساب مساحة المثلث المتشكل من النقاط: 
# (x1, y1), (x2, y2) و (x3, y3) 

def area(x1, y1, x2, y2, x3, y3): 

	return abs((x1 * (y2 - y3) + x2 * (y3 - y1) 
				+ x3 * (y1 - y2)) / 2.0) 


# دالة مساعدة للتحقق من أنّ النقطة P تقع ضمن حدود 
# المثلث المتشكّل من النقاط الثلاثة المعطاة 
def isInside(x1, y1, x2, y2, x3, y3, x, y): 

	# ABC حساب مساحة المثلث 
	A = area (x1, y1, x2, y2, x3, y3) 

	# PBC حساب مساحة المثلث 
	A1 = area (x, y, x2, y2, x3, y3) 
	
	# PAC حساب مساحة المثلث 
	A2 = area (x1, y1, x, y, x3, y3) 
	
	# PAC حساب مساحة المثلث 
	A3 = area (x1, y1, x2, y2, x, y) 
	
	# التحقق من أنّ مجموع المساحات الثلاثة يساوي مساحة المثلث الأصلي 
	if(A == A1 + A2 + A3): 
		return True
	else: 
		return False

# اختبار الدوال السابقة 
# P(10, 15) التحقق من أنّ النقطة 
# موجودة داخل المثلث المتشكّل من النقاط
# A(0, 0), B(20, 0) و C(10, 30) 
if (isInside(0, 0, 20, 0, 10, 30, 10, 15)): 
	print('Inside') 
else: 
	print('Not Inside') </source>
* جافا:

<source lang="java">import java.util.*; 

class GFG { 
	
	/* دالة مساعدة لحساب مساحة المثلث المتشكل من النقاط:
	(x1, y1), (x2, y2) و (x3, y3) */
	static double area(int x1, int y1, int x2, int y2, 
										int x3, int y3) 
	{ 
	return Math.abs((x1*(y2-y3) + x2*(y3-y1)+ 
									x3*(y1-y2))/2.0); 
	} 
	
	/* دالة مساعدة للتحقق من أنّ النقطة P تقع ضمن حدود
	المثلث المتشكّل من النقاطة الثلاثة المعطاة */
	static boolean isInside(int x1, int y1, int x2, 
				int y2, int x3, int y3, int x, int y) 
	{ 
	/* ABC حساب مساحة المثلث */
		double A = area (x1, y1, x2, y2, x3, y3); 
	
	/* PBC حساب مساحة المثلث */
		double A1 = area (x, y, x2, y2, x3, y3); 
	
	/* PAC حساب مساحة المثلث */
		double A2 = area (x1, y1, x, y, x3, y3); 
	
	/* PAB حساب مساحة المثلث */
		double A3 = area (x1, y1, x2, y2, x, y); 
		
	/* التحقق من أنّ مجموع المساحات الثلاثة يساوي مساحة المثلث الأصلي */
		return (A == A1 + A2 + A3); 
	} 
	
	/* اختبار التوابع السابقة */
	public static void main(String[] args) 
	{ 
		/* P(10, 15) التحقق من أنّ النقطة 
موجودة داخل المثلث المتشكّل من النقاط
A(0, 0), B(20, 0) و C(10, 30) */
	if (isInside(0, 0, 20, 0, 10, 30, 10, 15)) 
		System.out.println("Inside"); 
	else
		System.out.println("Not Inside"); 
			
	} 
} </source>
== مصادر ==

* صفحة [https://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/ Check whether a given point lies inside a triangle or not] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: الخوارزميات الهندسية]]