Làm thế nào tôi có thể kiểm tra nếu một điểm nằm trong một hình dạng 3d với bề mặt của nó được xác định bởi một đám mây điểm?

Question

Tôi có một tập hợp các điểm mô tả bề mặt của một hình dạng nên có hình cầu gần và tôi cần một phương pháp để xác định xem có điểm nào khác nằm trong hình dạng này không. Trước đây tôi đã xấp xỉ hình dạng như một quả cầu chính xác, nhưng điều này đã chứng minh là không chính xác và tôi cần một phương pháp chính xác hơn. Đơn giản và tốc độ là thuận lợi hơn độ chính xác hoàn thành, một xấp xỉ tốt sẽ đủ.

Tôi đã bắt gặp các kỹ thuật chuyển đổi đám mây điểm thành lưới 3D, nhưng hầu hết những thứ tôi đã tìm thấy đều rất phức tạp và tôi đang tìm kiếm một thứ đơn giản nhất có thể.

Bất kỳ ý tưởng nào?

Answer 1

Điều gì sẽ xảy ra nếu bạn tính toán trọng tâm của đám mây và chuyển đổi tọa độ của nó thành một hệ cực có nguồn gốc là trọng tâm.

Sau đó, chuyển đổi điểm bạn muốn kiểm tra sang cùng một hệ tọa độ.

Giả sử bề mặt có thể biểu diễn bằng hình tam giác Delaunay, xác định ba điểm có chênh lệch nhỏ nhất về góc từ điểm bạn đang kiểm tra.

Dự án điểm bạn đang kiểm tra vào tam giác được xác định bởi ba điểm đó và xem khoảng cách của điểm chiếu từ trọng tâm có lớn hơn khoảng cách của điểm thực tế hay không.

Về cơ bản, bạn đang xây dựng một lưới hình tam giác của thân lồi, nhưng khi cần một tam giác tại một thời điểm. Nếu tốc độ thực thi thực sự quan trọng, bạn có thể lưu lại các tam giác kết quả khi bạn đi.

Steven Sudit cũng đã đề xuất a useful optimization mà tôi khuyên bạn nên nếu bạn đi xuống con đường này.

Answer 2

Tôi nghĩ phương pháp của Bill Carey đang đi đúng hướng, nhưng tôi muốn đề xuất tối ưu hóa có thể.

Vì hình dạng gần hình cầu, bạn có thể tính trước bán kính của quả cầu bị ràng buộc bởi bán kính và hình cầu bao quanh nó. Bằng cách này, nếu khoảng cách của điểm nằm trong quả cầu nhỏ hơn, đó là một đòn xác định và nếu nó ở bên ngoài quả cầu bên ngoài, đó là một lỗi nhất định.

Điều này nên để bạn giải quyết các trường hợp dễ dàng rất nhanh chóng. Đối với những người khó hơn, phương pháp của Carey đã kết thúc.

Answer 3

Sử dụng cây kd.

http://en.wikipedia.org/wiki/Kd-tree

Bài viết cung cấp giải thích tốt.

Tôi có thể xóa thêm bất kỳ hiểu lầm nào.