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

[tntxtnt]

ở đâ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?

top answer cũng chỉ cần 6 phép nhân mà còn bị chê đòi xài Barycentric coord

[Khanh_Ha_23 (Khánh Hà)]

em có thử làm theo cách là viết ptrinh đường thẳng đi qua 3 cạnh của tam giác, điểm bất kì có nằm trong phần giao giữa 3 ptrinh là điểm nằm trong tam giác

à mà em code cũng tính những trường hợp là nếu điểm trùng vs 3 đỉnh a,b,c hoặc nằm trên 1 trong 3 cạnh thì bài toán cũng true (TRUE sẽ in kết quả là 1, còn FALSE thì in 0)

em mới học code nên bài làm chưa được tối ưu, mọi người xem giúp em với ạ

input : 4 dòng tách biệt là tọa độ 4 điểm A,B,C,D
output: ‘0’ hoặc ‘1’

inp:
0 1
3 0
-1 -2
0 0
out:
1

file=open('TAMGIAC.INP')
file2=open('TAMGIAC.OUT', 'w')
a=[int(e) for e in file.readline().split()]
b=[int(e) for e in file.readline().split()]
c=[int(e) for e in file.readline().split()]
d=[int(e) for e in file.readline().split()]
dem=0
def dt(x,y,z):
    f=(y[1]-x[1])*z[0]+(x[0]-y[0])*z[1]+(y[0]*x[1]-x[0]*y[1])
    return f
if d==a, d==b, or d==c:
    file2.write('1')
else:
    if dt(a,b,c)==0:
        file2.write('0')
    else:
        if dt(a,b,c)<=0 and dt(a,b,d)<=0\
            or dt(a,b,c)>=0 and dt(a,b,d)>=0:
            dem+=1
        if dt(a,c,b)<=0 and dt(a,c,d)<=0\
            or dt(a,c,b)>=0 and dt(a,c,d)>=0:
            dem+=1
        if dt(b,c,a)<=0 and dt(b,c,d)<=0\
            or dt(b,c,a)>=0 and dt(b,c,d)>=0:
            dem+=1
if dem==3:file2.write('1')
if 0<dem<3:file2.write('0')
file.close()
file2.close()

em gửi code copy ở đây nhưng mà em không biết chỉnh lề