التحقق من أن نقطة معينة موجودة داخل المثلث

تتحقق هذه الخوارزمية من وجود النقطة المعطاة بإحداثياتها (لتكن P) داخل المثلث الذي تحدده أحداثيات أركانه.

مثال:

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

              B(10,30)
                / \
               /   \
              /     \
             /   P   \      P'
            /         \
     A(0,0) ----------- C(20,0)

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

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

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

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

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

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; 
}

بايثون:

# دالة مساعدة لحساب مساحة المثلث المتشكل من النقاط: 
# (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')

جافا:

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"); 
			
	} 
}

مصادر

صفحة Check whether a given point lies inside a triangle or not في توثيق الخوارزميات في موقع GeeksforGeeks.