Cách xác định một điểm có nằm trong tam giác?

Ta sẽ viết được phương trình đi qua 3 cạnh:

• chú ý trọng tâm luôn nằm trong tam giác
  => điểm đó cùng phía với trọng tâm ở cả 3 phương trình đường thẳng

Một cách

@Gio mới học cấp 3 xong hay sao mà nhớ cái vị cùng phía vậy

À. Nếu không nhớ cách đó thì có thể dùng diên tích:
F(A,B,C) giả sử là diện tích tam giác ABC
nếu M nằm trong tam giác thì
s=f(a,b,m)+f(b,c,m)+f(c,a,m)=f(a,b,c)
nếu m nằm ngoài thì s lớn hơn

mình thích cái cách này

Chính xác, cách này là cách mà hồi trước Đạt dùng để làm

Google thì thấy cách này, cách này là sao @Gio?

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    bool b1, b2, b3;

    b1 = sign(pt, v1, v2) < 0.0f;
    b2 = sign(pt, v2, v3) < 0.0f;
    b3 = sign(pt, v3, v1) < 0.0f;

    return ((b1 == b2) && (b2 == b3));
}

How to determine if a point is in a 2D triangle?

sáng dậy đọc thấy cái topic của a Đạt , lên trường loằng ngoằng 1 lúc ra cái code này . . e nghĩ dùng kiến thức cấp 3 là tính tương đối của điểm với đường thẳng cũng ngon a ạ … .
đây là code của e . a và mọi người xem thử rồi góp ý cho e nhé …

#include <iostream>
#include <math.h>
using namespace std ;

float a1,b1,c1,
	  a2,b2,c2,
	  a3,b3,c3;
float x,y;
float tich , q,w,e ;
void main () 
{
	cout << " nhap phuong trinh 3 canh cua tam giac duoi dang a.x + b.y + c = 0 " << endl ;
	cout << "canh thu nhat :" << endl ;
	cin >> a1 >> b1 >> c1 ;
	cout << "canh thu hai : " << endl ;
	cin >> a2 >> b2 >> c2 ;
	cout << "canh thu ba : " << endl ;
	cin >> a3 >> b3 >> c3 ;
	cout << "nhap toa do diem can xet : " << endl ;
	cin >> x >> y ;
	cout << "phuong trinh 3 canh : " << endl ;
	cout << a1 << ".x + " << b1 << ".y + " << c1 << "= 0 " << endl ;
	cout << a2 << ".x + " << b2 << ".y + " << c2 << "= 0 " << endl ;
	cout << a3 << ".x + " << b3 << ".y + " << c3 << "= 0 " << endl ;
	cout << "M(" << x << ";" << y << ")" << endl ;
	q = a1*x + b1*y + c1 ;
	w = a2*x + b2*y + c2 ;
	e = a3*x + b3*y + c3 ;
	tich = q*w*e ;
	if ( tich < '0' )
		cout << "diem thuoc tam giac! " << endl ;
	else 
		cout << "diem khong thuoc tam giac! " << endl ;
	system ("pause") ;
}   

P/s : nếu nhập lung tung thi toàn là điểm nằm ngoài thôi …

P/s : nếu nhập lung tung thi toàn là điểm nằm ngoài thôi

vậy cho luôn cái input ví dụ đi cho nó máu

Điểm A, B, C và điểm cần test ấy

@ltd làm sao cho điểm chắc chắn nằm trong tam giác đc ạ , e chưa cho tam giác đó là tam giác nào cả . e viết để có thể kiểm tra với nhiều tam giác a ạ … . tức là mỗi lần chạy phải nhập 3 phương trình 3 cạnh + điểm cần xét ạ . nhưng phải biết phương trình tổng quát của 3 cạnh của tam giác đó + tọa độ điểm cần xét thì ct mới chạy được , e đang nghiên cứu cho cái nhập tọa độ 3 đỉnh của tam giác cơ mà hơi phức tạp chút ạ .

Cái này là cross clock wise thường dc dùng trong thuật toán hình học. Nếu hàm sign này âm hoặc dương thì nó luôn cùng chiều hoặc ngược chiều kim đồng hồ

bạn nói rõ hơn về cái hàm sign này đi

Cái này cũng dễ hiểu mà:
Bỏ qua th đặc biệt thì đường thẳng đi qua P1,P có dạng
(x-px)/(p1x-px)=(y-py)/(p1y-py)
quy đồng và đưa về pt tổng quát=> xét điêm P2 thay vào pt
=> ta có hàm sign như trên

cách xét diện tích của 3 tam giác con rất hay @Gio . tối nay e phải thử code theo kiểu đó xem có ngắn ko , vì e mới học nên code rất dài và chưa có tối ưu được , e vẫn theo kiểu xét tương đối giữa 1 điểm vs phương trình 3 cạnh của tam giác nhưng e đã sửa lại code để có thể nhập 1 tam giác dưới dạng 3 đỉnh hoặc phương trình 3 cạnh của nó . trong quá trình code e lại thấy xuất hiện các trường hợp đặc biệt là nếu mình nhập lung tung hoặc mình nhập sai thì có thể xảy ra trường hợp đặc biệt là không có 1 tam giác nào cả . thế nên e đã thêm phần phân biệt xem có phải là tam giác hay ko . sau đây là code của e , khá dài ạ . e cũng ko biết có thể tối ưu nó theo cách nào nữa . e đã test thử và thấy ok rồi …

#include <iostream>
#include <math.h>
using namespace std ;

void main () 
{
	float x,y;
	float tich,q , w,e ;
	int c ;
	cout << "bam 1 neu ban co phuong trinh cua 3 canh giac ! " << endl ;
	cout << "bam 2 neu ban co toa do 3 dinh cua tam giac ! " << endl ;
	cin >> c ;
	switch (c)
	{
	case 1 :
		{
		float a1,b1,c1,
			  a2,b2,c2,
			  a3,b3,c3;
		cout << " nhap phuong trinh 3 canh cua tam giac duoi dang a.x + b.y + c = 0 " << endl ;
		cout << "canh thu nhat :" << endl ;
		cin  >> a1  >> b1 >> c1 ;
		cout << "canh thu hai : " << endl ;
		cin  >> a2 >> b2 >> c2 ;
		cout << "canh thu ba : " << endl ;
		cin  >> a3 >> b3 >> c3 ;
		cout << "nhap toa do diem can xet : " << endl ;
		cin >> x >> y ;
		cout << "phuong trinh 3 canh : " << endl ;
		cout << a1 << ".x + " << b1 << ".y + " << c1 << "= 0 " << endl ;
		cout << a2 << ".x + " << b2 << ".y + " << c2 << "= 0 " << endl ;
		cout << a3 << ".x + " << b3 << ".y + " << c3 << "= 0 " << endl ;
		cout << "M(" << x << ";" << y << ")" << endl ;
		// neu co 2 duong thang song song . 
		if (a1/a2 == b1/b2 || a2/a3 == b2/b3 || a1/a3 == b1/b3 )
		{
			cout << " 3 duong thang da cho khong tao thanh tam giac ! " << endl ;
		}
		else 
		{
		q = a1*x + b1*y + c1 ;
		w = a2*x + b2*y + c2 ;
		e = a3*x + b3*y + c3 ;
		tich = q*w*e ;
		if ( tich > 0 )
			cout << "diem khong thuoc tam giac! " << endl ;
		else 
			cout << "diem thuoc tam giac! " << endl ;
		}
		}
		break ;
	
	case 2 :
		{
		float xA,yA;
		float xB,yB;
		float xC,yC;
		cout << " nhap phuong trinh 3 dinh cua tam giac " << endl ;
		cout << " nhap toa do dinh thu nhat " << endl ;
		cin >> xA >> yA ;
		cout << " nhap toa do dinh thu hai " << endl ;
		cin >> xB >> yB ;
		cout << " nhap toa do dinh thu ba " << endl ;
		cin >> xC >> yC ;
		cout << "nhap toa do diem can xet : " << endl ;
		cin >> x >> y ;
		cout << " toa do cac diem " << endl ; 
		cout << "A(" << xA << ";" << yA << ")" << endl ;
		cout << "B(" << xB << ";" << yB << ")" << endl ;
		cout << "C(" << xC << ";" << yC << ")" << endl ;
		cout << "M(" << x << ";" << y << ")" << endl ;
		// neu AB >= BC + AC || BC >= AB + AC || AC >= AB + BC 
		if ( sqrt((xA-xB)*(xA-xB)+(yA-yB)*(yA-yB)) >= sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB)) + sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC)) || 
			sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB)) >= sqrt((xA-xB)*(xA-xB)+(yA-yB)*(yA-yB)) + sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC)) ||
			sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC)) >= sqrt((xA-xB)*(xA-xB)+(yA-yB)*(yA-yB)) + sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB))
			) 
		{
			cout << " 3 diem da cho khong tao thanh tam giac ! " << endl ;
		}
		else 
		{
		q = (x-xA)/(xB-xB)-(y-yA)/(yB-yA);
		w = (x-xB)/(xC-xB)-(y-yB)/(yC-yB);
		e = (x-xC)/(xA-xC)-(y-yC)/(yA-yC);
		tich = q*w*e ;
		if ( tich > 0 )
			cout << "diem khong thuoc tam giac! " << endl ;
			
		else 
			cout << "diem thuoc tam giac! " << endl ;
		}
		}
		break ;
	default :
		break ;
	}
	
	system ("pause") ;
}

P/s : @ltd @Gio , các a có cách nào khiến code e ngắn hơn mà vẫn giữ được ý tưởng ko ạ .

struct point{ float x,y;}
float dientich(point &a,point&b,point&c){
float d1=b.x-a.x,
d2=b.y-a.y,d3=c.x-a.x,d4=c.y-a.y;
return abs(d1*d4-d2*d3)/2;
}

cái này là a làm theo pp diện tích ạ ?

http://www.blackpawn.com/texts/pointinpoly/default.html

Em tìm được cái này mà hơi khó hiểu. Em làm thì chạy ra kq sai.

    float sign(Point2D p1, Point2D p2, Point2D p3)
{
	Point2D _Vector1, _Vector2;


	_Vector1.x = p1.x - p3.x;
	_Vector1.y = p1.y - p3.y;
	_Vector2.x = p2.x - p3.x;
	_Vector2.y = p2.y - p3.y;


	return _Vector1.x * _Vector2.y - _Vector2.x * _Vector1.y;
}



    bool pointInTriangle(Point2D p1, Point2D p2, Point2D p3, Point2D p)
    {
    	if (((sign(p, p1, p2) < 0) && (sign(p, p1, p3) < 0) && (sign(p, p2, p3) < 0)) || ((sign(p, p1, p2) > 0) && (sign(p, p1, p3) > 0) && (sign(p, p2, p3) > 0)))
    	{
    		return true;
    	}
    	return false;
    }

Cách giải @genius_hcmus đưa ra có giống cách @Gio nói không ta. Đọc lướt qua thì có vẻ giống. Nhưng chưa vào xem

Ta sẽ viết được phương trình đi qua 3 cạnh:- chú ý trọng tâm luôn nằm trong tam giác=> điểm đó cùng phía với trọng tâm ở cả 3 phương trình đường thẳng

Em không có viết phương trình, em làm theo cách trên stackoverflow mà sao ra kq chưa đúng.
Em viết tọa độ vector ra rồi nhân theo định thức đó a.

Hình như công thức của bác bị sai nêu mà yB - yA = 0 thì không tính đc e có thử rồi

#include<stdio.h>
int main() {
	int xA, yA, xB, yB, xC, yC, xD, yD;
	int ABAC;
	float BA, CB, AC, Tich;
	float t1, t2, t3, t4, t5, t6;
	printf("Nhap A(xA,yA):");
	printf("\nxA=");
	scanf_s("%d", &xA);
	printf("\nyA=");
	scanf_s("%d", &yA);
	printf("\nNhap B(xB,yB):");
	printf("\nxB=");
	scanf_s("%d", &xB);
	printf("\nyB=");
	scanf_s("%d", &yB);
	printf("\nNhap C(xC,yC):");
	printf("\nxC=");
	scanf_s("%d", &xC);
	printf("\nyC=");
	scanf_s("%d", &yC);
	printf("\nNhap D(xD,yD):");
	printf("\nxD=");
	scanf_s("%d", &xD);
	printf("\nyD=");
	scanf_s("%d", &yD);
	ABAC = (xB - xA) * (yC - yA) - (yB - yA) * (xC - xA);
	if (ABAC == 0) {
		printf("\nba diem A, B, C khong phai la mot tam giac");
	}
	else {
		printf("\nba diem A, B, C la mot tam giac");
		BA = (xD - xA) / (xB - xA) - (yD - yA) / (yB - yA);
		CB = (xD - xB) / (xC - xB) - (yD - yB) / (yC - yB);
		AC = (xD - xC) / (xA - xC) - (yD - yC) / (yA - yC);
		Tich = BA * CB * AC;
		if (Tich > 0) {
			printf("\nD nam ngoai tam giac ABC");
		}
		else if (Tich < 0) {
			printf("\nD nam trong tam giac ABC");
		}
		else {
			t1 = xD / (xB - xA);
			t2 = yD / (yB - yA);
			t3 = xD / (xC - xA);
			t4 = yD / (xC - xA);
			t5 = xD / (xC - xB);
			t6 = yD / (xC - xB);
			if (t1 == t2) {
				printf("\nD nam tren canh AB cua tam giac ABC");
			}
			else if (t3 == t4) {
				printf("\nD nam tren canh AC cua tam giac ABC");
			}
			else if (t5 == t6) {
				printf("\nD nam tren canh BC cua tam giac ABC");
			}
		}
	}
	printf("\n");
	return 0;
}

Lấy lần lượt từng cặp 2 điểm của tam giác ta có 1 đường thẳng. Thay toạ độ điểm còn lại và điểm cần kiểm tra ta được 2 giá trị y. Nếu tích 2 y âm thì điểm check nằm ngoài tam giác.

ở đây ko ai học computer graphics hết à

chuyển về Barycentric coordinate: P = uA + vB + wC, với u + v + w = 1. Nếu P nằm trong tam giác ABC thì u,v,w >= 0. Bản chất của nó cũng y hệt kiểm tra diện tích PAB PBC PCA cộng lại có bằng diện tích ABC.

ta có 3 phương trình:
uA.x + vB.x + wC.x = P.x
uA.y + vB.y + wC.y = P.y
u + v + w = 1
3 phương trình 3 ẩn, giải ra u,v,w dễ dàng. Có u,v,w rồi thì kiểm tra xem u,v,w >= 0 hết thì P nằm trong ABC.

nhưng mỗi lần giải hệ pt vậy rất là mất công, wiki có giải sẵn:



(sao cái hình bị thu nhỏ lại vậy @_@)

tuy có phép chia nhưng nhìn kĩ thì mẫu của u và v đều giống nhau và ko liên quan tới P.x, P.y, như vậy cho tam giác ABC ta có thể tính trước 1/mẫu này. Lần kiểm tra đầu tiên cần 8 phép nhân, các lần kiểm tra sau đó chỉ cần 6 phép nhân.

SO cũng có câu hỏi này:

How to determine if a point is in a 2D triangle?