Góc học tập
17/03/2012 10:36:53 AM

Vị trí điểm 1 điểm so với tam giác.

 

Những bạn học Lập trình Cơ sở hay FC1 sẽ hay gặp bài toán như sau:

Trong mặt phẳng Oxy cho tam giác ABC và một điểm D. Hãy cho biết vị trí của điểm D so với tam giác ABC.

Đối với bài toán này các bạn nghĩ ngay đến cách dùng diện tích tam giác. Ta lần lượt tính diện tích 4 tam giác ABC, ABD, ACD, BCD. Nếu diện tích ABC bằng tổng 3 diện tích tam giác còn lại thì kết luận là D thuộc tam giác.

Để tính diện tích tam giác ta dùng công thức Heron, với a, b,c là độ dài 3 cạnh của tam giác.

                                            S=sqrt( (a2+ b2 +c2)2 -2*(a4+b4+c4))/4

 

Khoảng cách hai điểm (x1,y1) , (x2,y2) được xác định bằng công thức:

                                           d= sqrt( (x1-x2)2 + (y1-y2)2 )

Để kết luận vị trí của điểm D so với tam giác ABC ta phải thực hiện phép tính căn bặc 2 10 lần, tương ứng với 6 lần tính độ dài cạnh là 4 lần tính diện tích tam giác.

Tuy nhiên các hàm tính căn bậc hai trong các ngôn ngữ lập trình có sai số và kiểu dữ liệu chọn để lưu độ dài cạnh, diện tích tam giác không thể biểu diễn hết các số thập phân của phép tính nên trong một số trường hợp ta nhận được kết quả không đúng.

Một cách khác để giải bài toán này dùng phương pháp xét vị trí điểm D so với 3 cạnh. Điểm D nếu nằm trong tam giác nếu nó thuộc 1 trong ba cạnh hoặc ở trên(hay bên trái) 2 cạnh và dưới (hay bên phải) 1 cạnh hoặc dưới hai cạnh và trên 1 cạnh.

Để xét điểm nằm trên hay dưới đường thẳng qua hai điểm (x1,y1), (x2,y2) ta dùng công thức sau:

Vector v1 = {x2-x1, y2-y1}

Vector v2 = {x2-xA, y2-yA}  
Tính xp = v1.x*v2.y - v1.y*v2.x  // Cross product

Nếuxp > 0  bên trên

Ngược lại Nếu xp<0 bên dưới
          Ngược lại thuộc đường thẳng

 

Các bạn có thể cài đặt để kiểm tra. Chi tiết phần cài đặt, so sánh thời gian thực hiện sẽ bàn trong bài tới.