{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:33:13Z","timestamp":1762299193159,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Vertex concavity-convexity detection for spatial objects is a basic algorithm of computer graphics, as well as the foundation for the implementation of other graphics algorithms. In recent years, the importance of the vertex concavity-convexity detection algorithm for three-dimensional (3D) spatial objects has been increasingly highlighted, with the development of 3D modeling, artificial intelligence, and other graphics technologies. Nonetheless, the currently available vertex concavity-convexity detection algorithms mostly use two-dimensional (2D) polygons, with limited research on vertex concavity-convexity detection algorithms for 3D polyhedrons. This study investigates the correlation between the outer product and the topology of the spatial object based on the unique characteristic that the outer product operation in the geometric algebra has unified and definitive geometric implications in space, and with varied dimensionality. Moreover, a multi-dimensional unified vertex concavity-convexity detection algorithm framework for spatial objects is proposed, and this framework is capable of detecting vertex concavity-convexity for both 2D simple polygons and 3D simple polyhedrons.<\/jats:p>","DOI":"10.3390\/ijgi9010025","type":"journal-article","created":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T04:43:03Z","timestamp":1578026583000},"page":"25","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Vertex Concavity-Convexity Detection Method for Three-Dimensional Spatial Objects Based on Geometric Algebra"],"prefix":"10.3390","volume":"9","author":[{"given":"Pengcheng","family":"Yin","sequence":"first","affiliation":[{"name":"Natural Resources and Planning Bureau of Xuzhou City, Xuzhou 221006, China"},{"name":"School of Environment Science and Spatial Information, China University of Mining and Technology, Xuzhou 221018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7391-1329","authenticated-orcid":false,"given":"Jiyi","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Geographic Science, Nantong University, Nantong 226019, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiying","family":"Sun","sequence":"additional","affiliation":[{"name":"Geological Exploration Technology Institute of Jiangsu Province, Nanjing 210046, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Hu","sequence":"additional","affiliation":[{"name":"Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifeng","family":"Shi","sequence":"additional","affiliation":[{"name":"Natural Resources and Planning Bureau of Xinyi City, Xuzhou 221400, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengyan","family":"Wu","sequence":"additional","affiliation":[{"name":"Natural Resources and Planning Bureau of Xinyi City, Xuzhou 221400, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhao, J., Gao, M., and Wang, S. (2009, January 25\u201326). Orientation, Convexity-Concavity and Inclusion Test Algorithms for Polygons. Proceedings of the 2009 International Conference on Information Technology & Computer Science, Kiev, Ukraine.","DOI":"10.1109\/ITCS.2009.221"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, W., Ong, E.T., Xu, S., and Hung, T. (2005, January 9\u201312). A Point Inclusion Test Algorithm for Simple Polygons. Proceedings of the Computational Science and Its Applications\u2014ICCSA 2005, International Conference, Singapore. Part I.","DOI":"10.1007\/11424758_79"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/S0097-8493(00)00054-6","article-title":"An algebraic algorithm for point inclusion query","volume":"24","author":"Wu","year":"2000","journal-title":"Comput. Graph."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1016\/j.cag.2007.03.002","article-title":"Point-in-polygon tests by convex decomposition","volume":"31","author":"Li","year":"2007","journal-title":"Comput. Graph."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0925-7721(01)00012-8","article-title":"The point in polygon problem for arbitrary polygons","volume":"20","author":"Hormann","year":"2001","journal-title":"Comput. Geom."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Zhao, J., Cheng, Y., Gao, M., and Wang, S. (2009, January 7\u20138). An Algorithm for Determining the Orientation and Convexity-Concavity of Simple Polygons. Proceedings of the 2009 First International Workshop on Education Technology and Computer Science, Wuhan, China.","DOI":"10.1109\/ETCS.2009.365"},{"key":"ref_7","first-page":"810","article-title":"Determining Convexo-Concave Vertices of Polygon By Topological Mapping","volume":"14","author":"Wu","year":"2002","journal-title":"J. Comput. Aided Des. Comput. Graph."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.cagd.2008.05.003","article-title":"Approximate Convex Decomposition of Polyhedra","volume":"25","author":"Amato","year":"2008","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.comgeo.2005.10.005","article-title":"Approximate convex decomposition of polygons","volume":"35","author":"Lien","year":"2006","journal-title":"Comput. Geom."},{"key":"ref_10","first-page":"276","article-title":"An algorithm for determining convexo-concave vertices of an arbitrary polygon","volume":"6","author":"Zhou","year":"1995","journal-title":"J. Softw."},{"key":"ref_11","first-page":"103","article-title":"An algorithm for rapidly determining the convexity-concavity of the vertices of an arbitrary polygon","volume":"25","author":"Xu","year":"1997","journal-title":"J. Huazhong Univ. Sci. Technol."},{"key":"ref_12","unstructured":"Zhou, P. (2006). Computational Geometry: Algorithm Design and Analysis, Tsinghua University Press."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/0097-8493(95)00037-D","article-title":"Orientation, simplicity, and inclusion test for planar polygons","volume":"19","author":"Feito","year":"1995","journal-title":"Comput. Graph."},{"key":"ref_14","first-page":"66","article-title":"A fast algorithm for determining the convexity-concavity of vertices of simple polygon","volume":"1","author":"Jin","year":"1998","journal-title":"J. Eng. Graph."},{"key":"ref_15","first-page":"71","article-title":"An algorithm for rapidly identifying convexo-concave vertices of simple polygon based on comparing the slopes of two adjacent edge vectors","volume":"3","author":"Pang","year":"2004","journal-title":"J. Eng. Graph."},{"key":"ref_16","first-page":"55","article-title":"Orientation and convexity-concavity identification for polygons using extremity vertices sequence","volume":"1","author":"Zhao","year":"2007","journal-title":"J. Eng. Graph."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"350","DOI":"10.2307\/2369379","article-title":"APPlieations of Grassmann\u2019s extensive algebra","volume":"1","author":"Clifford","year":"1878","journal-title":"Am. J. Math."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Dorst, L., Fontijne, D., and Mann, S. (2007). Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, Morgan Kaufmann Publishers.","DOI":"10.1016\/B978-012369465-2\/50004-9"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s11430-010-4130-9","article-title":"A 3D GIS Spatial Data Model Based on Conformal Geometric AIgebra","volume":"54","author":"Yuan","year":"2011","journal-title":"Sci. China Earth Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Zhang, J.-Y., Yin, P.-C., Li, G., Gu, H.-H., Zhao, H., and Fu, J.-C. (2016). 3D Cadastral Data Model Based on Conformal Geometry Algebra. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5020020"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Li, H.B. (2008). Invariant Algebras and Geometric Reasoning, World Scientific.","DOI":"10.1142\/9789812770110"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, H.B., Hestenes, D., and Rockwood, A. (2001). Generalized Homogeneous Coordinates for Computational Geometry, Geometric Computing with Clifford Algebra, Springer.","DOI":"10.1007\/978-3-662-04621-0_2"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Penvass, C., and Lasenby, J. (2001). A Unified Description of Multiple View Geometry, Geometric Computing with Clifford Algebra, Springer.","DOI":"10.1007\/978-3-662-04621-0_14"},{"key":"ref_24","unstructured":"Cameron, J., and Lasenby, J. (2005, January 19\u201329). Oriented conformal geometric algebra. Proceedings of the 7th International Conference on Clifford Algebras and Their Applications in Mathematical Physics ICCA7, Toulouse, France."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Lasenby, J., Bayro-Corrochano, E., Lasenby, A., and Sommer, G. (1996, January 25\u201329). A new methodology for computing invariants in computer vision. Proceedings of the 13th International Conference on Pattern Recognition, Institute of Electrical and Electronics Engineers (IEEE), ICPR 96, Vienna, Austria.","DOI":"10.1109\/ICPR.1996.546056"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1023\/A:1007901028047","article-title":"New Geometric Methods for Computer Vision: An Application to Structure and Motion Estimation","volume":"26","author":"Lasenby","year":"1998","journal-title":"Int. J. Comput. Vis."},{"key":"ref_27","unstructured":"Penvass, C. (2000). Applications of Geometric Algebra in Computer Vision. [Ph.D. Thesis, Cambridge University]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2435","DOI":"10.1080\/13658816.2014.929136","article-title":"Multidimensional-unified topological relations computation: A hierarchical geometric algebra-based approach","volume":"28","author":"Yuan","year":"2014","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1111\/j.1467-9671.2010.01221.x","article-title":"CAUSTA: Clifford Algebra-based Unified Spatio-Temporal Analysis","volume":"14","author":"Yuan","year":"2010","journal-title":"Trans. GIS"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1109\/TKDE.2014.2330829","article-title":"A Hierarchical Tensor-Based Approach to Compressing, Updating and Querying Geospatial Data","volume":"27","author":"Yuan","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2328","DOI":"10.1080\/13658816.2015.1077963","article-title":"Change detection for 3D vector data: A CGA-based Delaunay\u2013TIN intersection approach","volume":"29","author":"Yu","year":"2015","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1977","DOI":"10.1007\/s00006-016-0697-3","article-title":"A Hierarchical Representation and Computation Scheme of Arbitrary-dimensional Geometrical Primitives Based on CGA","volume":"27","author":"Luo","year":"2017","journal-title":"Adv. Appl. Clifford Algebras"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1080\/13658816.2017.1346796","article-title":"Template-based GIS computation: A geometric algebra approach","volume":"31","author":"Luo","year":"2017","journal-title":"Int. J. Geogr. Inf. Sci."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/1\/25\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:28:31Z","timestamp":1760362111000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/1\/25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["ijgi9010025"],"URL":"https:\/\/doi.org\/10.3390\/ijgi9010025","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}