Bài này xét trên hệ tọa độ Decarte vuông góc.
*Trong mặt phằng
- Cho tọa độ các đỉnh của một đa giác lồi, cho tọa độ 1 điểm. Tìm giả thuật xác định định điểm đã cho có thuộc miền trong đa giác không ?
- Cho phương trình một đường cong khép kín và tọa độ một điểm, tìm giải thuật xác định điểm đó có thuộc miền trong của đường cong không ?
*Tương tự trong không gian
- Cho tọa độ các đỉnh của 1 đa diện lồi, cho tọa độ 1 điểm. Tìm giải thuật xác định điểm đó có thuộc miền trong của đa diện không ?
- Cho phương trình mặt giới nội (không biết dùng từ có chính xác không ) và tọa độ một điểm, tìm giải thuật xác định điểm đó cỏ nằm trong mặt không ?

Hướng giả quyết của em là chia nhỏ đa giác thành các tam giác, rồi xét dần từng tam giác, nhưng chưa có giải thuật cho tam giác. Tương tụ cho đa diện, chia nhỏ đa diện thành tứ diện. Đối với phương trình đường cong khép kín, thì có phương trình sắn nên không phải chia, mà chia cũng không biết lấy gì làm chuẩn để chia. Có Phương trình thì có thể xác định được có thuộc đường hay mặt không, nhưng chưa xác định được có thuộc miền trong không ?

Mấy bài này nói chung khá đơn giản. Có cuốn sách cơ bản rất tốt cho các loại thuật toán hình học là cuốn Computational Geometry của 4 tác giả người Hà Lan là Marc de Berg, Marc de .., Schwartzkopf. Các bạn có thể tham khảo được.
Mấy bài này có thể qui về dạng tóan gọi là Linear Programming- tức là gỉai xem điểm X đã có thỏa mãn các bất phương trình của mọi nửa mặt phẳng (trường hợp không gian 2 chiều) giao nhau tạo nên đa diện lồi đó hay không.
Bởi vì một đa diện lồi có thể biển diễn như sau:
Xét trong không gian d chiều, số các đỉnh của |P| = n
P = conv(P) = { a_{i}x_{i} R^{d} | a_{i} = 1 , a_{i} 0 i }

hoặc P = { x R^{d} : Ax z, A R^{md}, z R^{m} }

Cách biểu diễn trên gọi là V-Description của một đa diện d chiều (d- Polytop). Cách biểu diễn dưới gọi là H-description. Người ta còn gọi tắt chúng là V-Polytop và H-Polytop.
Các bạn để ý thì cách trên mô tả rằng: nếu một điểm nằm trong một đa diện, thì nó thỏa mãn tổ hợp lồi (khác với tổ hợp tuyến tính) của các đỉnh đa diện. Ví dụ: điểm x = (1/2, 1/2) thỏa mãn tổ hợp lồi của hai điểm x1 =(0,0), x2= (1,1) như sau: 1/2.x1 + 1/2.x2 = x (chu' y': tổng của 1/2 + 1/2 = 1- đây là tính chất quan trọng của tổ hợp lồi:- tổng hệ số các phần tử căng lên đa giác lồi phải bằng 1). Tương tự cho không gian nhiều chiều hơn.
Cách dưới mô tả rằng: một đa giác (khép kín) có thể được biểu diễn bằng những nửa mặt phẳng giao nhau. Ví dụ: hình vuông đơn vị trong không gian 2 chiều có thể biểu diễn bằng 4 bất phương trình: { x 0, y 0, x 1, y 1 }. Vậy nếu điểm x = (1/2, 1/3) nằm trong hình đa giác thì nó phải thỏa mãn tất cả các bất phương trình này. Va tat nhien no nam trong vi no thoa man.
---