Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Kiểm tra điểm trong đa diện với việc xử lý trực tiếp các trường hợp suy biến
Tóm tắt
Vấn đề Kiểm tra Điểm Trong Đa Diện là xác định xem một điểm có nằm trong hay ngoài một đa diện cho trước hay không. Khi phát hiện một trường hợp suy biến, các thuật toán truyền thống dựa trên tia cắt thường né tránh trường hợp này bằng cách chọn một tia khác hoặc xóa trường hợp bằng cách làm biến đổi dữ liệu đầu vào. Bài báo này giới thiệu một thuật toán Cắt Tia Dựa Trên Ngưỡng (Threshold-Based Ray-Crossing - TBRC) để giải quyết vấn đề Kiểm tra Điểm Trong Đa Diện. Thuật toán TBRC xử lý trực tiếp các trường hợp suy biến bằng cách kiểm tra xem có nên đếm mặt cắt với tia hay không. Đáng chú ý, thuật toán TBRC có thể xử lý tất cả các trường hợp suy biến mà không cần tính toán và lưu trữ thêm. Hơn nữa, chúng tôi phân tích thuật toán cơ bản và kiểm tra cách để tăng tốc độ của nó. Kết quả thực nghiệm cho thấy thuật toán TBRC có độ hiệu quả cao và độ tin cậy tốt cho vấn đề Kiểm tra Điểm Trong Đa Diện, so với một thuật toán truyền thống dựa trên tứ diện mà không cần xử lý trước.
Từ khóa
#Kiểm tra điểm trong đa diện; Thuật toán cắt tia; Suy biến; Tối ưu hóa thuật toán; Hiệu suất.Tài liệu tham khảo
Zhang S Q, Zhang J Y (2010) Theoretical analytics of stereographic projection on 3D-objects’ intersection predicate[J]. International Journal of Geographical Information Sciences, 24(1): 25–46
Shiode N (2001) 3D urban models: recent developments in the digital modeling of urban environments in three-dimensions [J]. GeoJournal, 52(3):263–269
Coors V (2003) 3D-GIS in networking environments[J]. Computers, Environment and Urban Systems, 27(4): 345–357
Kwan M P, Lee J (2004) Geovisualization of human activity patterns using 3D GIS: a timegeographical approach[ M]//Goodchild M F, Janelle D G (Eds.). Spatially integrated social science. New York: Oxford University Press
Lee J, Kwan M P (2005) A combinatorial data model for representing topological relations among 3D geographical features in micro-spatial environments[J]. International Journal of Geographical Information Science, 19(10): 1039–1056
Stoter J E (2002) 3D cadastres, state of the art: from 2D parcels to 3D registrations[J]. GIM International, the World Magazine for Geomatics, 16(2)
Zlatanova S (2002) Advances in 3D GIS[J]. Quarterly Review of Disegno Digitale e Design, 1(4): 24–29
Zlatanova S, Bandrova T (1998) User requirements for the third dimensionality[C]. E-mail Seminar of Cartography 1998: Maps of the Future, Sofia, Bulgaria
Lee J (2008) Spatial data analysis in 3D GIS[M]// Oosterom P,. Zlatanova S, Penninga F, et al.(Eds.). Advances in 3D Geoinformation System: Lecture Notes in Geoinformation and Cartography. New York: Springer
Guo W, Zhan P, Chen J (1998) Topological data model for 3D GIS[J]. IAPRS, 32(4): 657–661
Ramos F (2002) Amulti-level approach for 3D modelling in geographical information systems[J]. International Archives of Photogrammetry and Remote Sensing, 34(4): 43–47
Segura R, Feito F R, Ruiz de Miras J (2005) An efficient point classification algorithm for triangle meshes [J]. Journal of Graphics, GPU, & Game Tools, 10(3):27–35
Wang W C, Li J, Sun H Q, et al.(2008) Layer-based representation of polyhedrons for point containment tests[J]. IEEE Trans. Vis. Comput. Graph, 14(1): 73–83
Verbree E (2005) Towards a 3D feature overlay through a tetrahedral mesh data structure[J]. Cartography and Geographic Information Science, 32(4): 303–314
Jiménez P, Thomas F, Torras C (2001) 3D collision detection: a survey[J]. Computers & Graphics, 25(2): 269–285
Ogayar C J, Segura R J, Feito F R (2005) Point in solid strategies[J]. Computers and Graphics, 29(4): 616–624
Meagher D (1982) Geometric modelling using octree encoding[ J]. Computer Graphics and Image Processing, 19(2): 129–147
Feito F R, Torres J C (1997) Inclusion test for general polyhedra[J]. Computers and Graphics, 21(1): 23–30
Carvaiho P C P, Cavalcanti P R (1995) Point in polyhedron testing using spherical polygons[M]// Paeth A W(Eds.). Graphics Gems V. New York: Academic Press
Möller T, Haines E (2002) Real-time rendering (2nd Edition)[M]. Boca Raton: A K Peters/ CRC Press
O’Rourke J (1998) Computational Geometry in C (2 edition) [M]. Cambridge: Academic Press
Emiris I, Canny J (1992) An efficient approach to removing geometric degeneracies[C]. Proceedings of the 8th Annual symposium on Computational geometry, Berlin, Germany
Edelsbrunner H, Mücke E P (1990) Simulation of simplicity: a technique to cope with degeneracies in geometric algorithms[J]. ACM Transactions on Graphics, 9(1): 66–104
Stewart J A (1994) Local robustness and its application to polyhedral intersection[J]. International Journal of Computational Geometry & Applications, 4(1): 87–118
Thomas F, Torras C (2002) A projectively invariant intersection test for polyhedra[J]. The Visual Computer, 18(7): 405–414
Canny J (1987) The complexity of robot motion planning[ M]. Cambridge MA: MIT Press