Tìm tất cả các điểm có tọa độ nguyên bên trong tứ diện

Question

Tôi đang cố gắng tìm tất cả các điểm có tọa độ nguyên nằm bên trong một tứ diện (tôi muốn bằng cách nào đó có thể lặp qua chúng). Tôi biết tọa độ của bốn điểm (A, B, C, D) xác định tứ diện.

Điều tôi đang làm là tìm hộp giới hạn của tứ diện (các tọa độ x, y, z tối thiểu và lớn nhất của A, B, C, D) và sau đó thực hiện vòng lặp qua tất cả các điểm bên trong hộp giới hạn. Đối với mỗi điểm như vậy, tôi tính toán tọa độ barycentric (sử dụng the equations from Wikipedia) và kiểm tra xem điểm có nằm trong tứ diện (nếu bất kỳ tọa độ barycentric nào là âm hay lớn hơn 1, điểm không nằm trong).

Có cách nào tốt hơn để thực hiện việc này không? Hiện nay có khoảng 1/6 cơ hội mà điểm tôi đang thử nghiệm (từ hộp giới hạn) thực sự nằm bên trong tứ diện, vì vậy tôi nghĩ rằng tôi đang làm quá nhiều tính toán không cần thiết.

Tôi đang làm việc với danh sách tứ diện mà tôi tạo ra bằng cách triangulating một khối lượng lớn hơn (tôi đang mở rộng khối lượng và muốn nội suy các giá trị bị thiếu bằng cách sử dụng nội suy tứ diện). Tôi không sử dụng bất kỳ thư viện bên ngoài nào.

Answer 1

Một ý tưởng để cải thiện:

kiểm tra nếu một "cây gậy" song song với trục z (ví dụ: x = 4, y = 6) chạy qua tứ diện. Nếu không, không có giá trị nào với (x = 4, y = 5, z) có thể ở bên trong.

Khác, tìm vị trí của thanh cắt cạnh của tứ diện (bằng cách tìm ra nơi các mặt phẳng tạo nên cạnh của tứ diện cắt nhau).

Giả sử các mặt phẳng cắt nhau tại z = 1.3 và z = 10.04. Sau đó, bạn biết tất cả các điểm (4,5, 2) đến (4,5,10) là bên trong.

Lặp lại tất cả các giá trị của x và y.

Điều này sẽ nhanh hơn trong thực tế, bởi vì nó sẽ giúp bạn tiết kiệm 1 vòng lặp.

Answer 2

Cách tiếp cận của bạn là chính xác. Có một số tối ưu có thể, có thể đáng giá hay không tùy theo yêu cầu. Ví dụ:

Có một cách dễ dàng hơn để kiểm tra xem một điểm nhất định có nằm trong hay ngoài tứ diện. Số tiền để kiểm tra khoảng cách giữa hai mặt của tứ diện của tứ diện:

Mỗi bên được xác định bằng 3 điểm (giả sử A, B, C). Sau đó, mặt phẳng bình thường là (C-A) x (B-A) (đó là sản phẩm chéo của vectơ trong mặt phẳng). Nếu tọa độ này là (a, b, c), thì phương trình phẳng là F(x,y,z) = ax+by+cz = 0. Đối với một điểm đã cho (x0, y0, z0), dấu của F (x0, y0, z0) xác định mặt phẳng nào thuộc về một nửa mặt phẳng. Điểm số là bạn có thể tính toán trước các mặt phẳng cho mỗi mặt của tứ diện cũng như ký hiệu tương ứng với 'bên ngoài', sau đó kiểm tra một điểm cho trước để thực hiện tối đa 4 lần đánh giá (một cho mỗi bên).), mỗi lần lấy 3 phép nhân và 2 lần bổ sung.