{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:30:20Z","timestamp":1760146220694,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T00:00:00Z","timestamp":1728086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JNICT","award":["BD-1657\/91_IA"],"award-info":[{"award-number":["BD-1657\/91_IA"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper presents a general analytical solution for the problem of locating points in planar regions with an arbitrary geometry at the boundary. The proposed methodology overcomes the traditional solutions used for polygonal regions. The method originated from the explicit evaluation of the contour integral using the Residue and Cauchy theorems, which then evolved toward a technique very similar to the winding number and, finally, simplified into a variant of ray-crossing approach slightly more informed and more universal than the classic approach, which had been used for decades. The very close relation of both techniques also emerges during the derivation of the solution. The resulting algorithm becomes simpler and potentially faster than the current state of the art for point locations in arbitrary polygons because it uses fewer operations. For polygonal regions, it is also applicable without further processing for special cases of degeneracy, and it is possible to use in fully integer arithmetic; it can also be vectorized for parallel computation. The major novelty, however, is the extension of the technique to virtually any shape or segment delimiting a planar domain, be it linear, a circular arc, or a higher order curve.<\/jats:p>","DOI":"10.3390\/a17100444","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T07:30:18Z","timestamp":1728286218000},"page":"444","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1283-7388","authenticated-orcid":false,"given":"Vitor","family":"Santos","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, Institute for Electronics Engineering and Informatics of Aveiro, University of Aveiro, 3810-193 Aveiro, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2024,10,5]]},"reference":[{"key":"ref_1","unstructured":"Alciatori, D., and Miranda, R. (1995). A Winding Number and Point-in-Polygon Algorithm, Department of Mechanical Engineering, Colorado State University. Technical Report."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1145\/368637.368653","article-title":"Algorithm 112: Position of Point Relative to Polygon","volume":"5","author":"Shimrat","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/355580.369118","article-title":"Certification of Algorithm 112: Position of Point Relative to Polygon","volume":"5","author":"Hacker","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_4","unstructured":"Franklin, W.R. (2024, October 02). PNPOLY-Point Inclusion in Polygon Test. 1994\u20132006. Available online: https:\/\/wrfranklin.org\/Research\/Short_Notes\/pnpoly.html."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Preparata, F.P., and Shamos, M.I. (1985). Computational Geometry: An Introduction, Springer.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"ref_6","unstructured":"Sedgewick, R. (1990). Algorithms in C, Addison-Wesley Longman Publishing Co., Inc."},{"key":"ref_7","unstructured":"Heckbert, P.S. (1994). Point in Polygon Strategies. Graphics Gems IV, Academic Press Professional, Inc."},{"key":"ref_8","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. Theory Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi diagrams\u2014A survey of a fundamental geometric data structure","volume":"23","author":"Aurenhammer","year":"1991","journal-title":"ACM Comput. Surv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1142\/S0129054102001035","article-title":"The Delaunay Hierarchy","volume":"13","author":"Devillers","year":"2002","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/PL00009234","article-title":"A Note on Point Location in Delaunay Triangulations of Random Points","volume":"22","author":"Devroye","year":"1998","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0925-7721(98)00035-2","article-title":"Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations","volume":"12","author":"Saias","year":"1999","journal-title":"Comput. Geom."},{"key":"ref_13","unstructured":"O\u2019Rourke, J. (2024, October 02). How Do I Find If a Point Lies within a Polygon. Available online: http:\/\/www.faqs.org\/faqs\/graphics\/algorithms-faq\/."},{"key":"ref_14","unstructured":"Sunday, D. (2024, October 02). Inclusion of a Point in a Polygon. Available online: https:\/\/geomalgorithms.com\/a03-_inclusion.html."},{"key":"ref_15","unstructured":"Foley, J.D., van Dam, A., Feiner, S.K., and Hughes, J.F. (1990). Computer Graphics: Principles and Practice, Addison-Wesley Longman Publishing Co., Inc.. [2nd ed.]."},{"key":"ref_16","unstructured":"O\u2019Rourke, J. (1998). Computational Geometry in C, Cambridge University Press."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Needham, T. (1998). Visual Complex Analysis, Oxford University Press.","DOI":"10.1093\/oso\/9780198534471.001.0001"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Schirra, S. (2008, January 15\u201317). How Reliable Are Practical Point-In-Polygon Strategies?. Proceedings of the 16th Annual European Symposium on Algorithms (ESA \u201908), Karlsruhe Germany.","DOI":"10.1007\/978-3-540-87744-8_62"},{"key":"ref_19","first-page":"1","article-title":"Efficient Angle Summation Algorithm for Point Inclusion Test and Its Robustness","volume":"19","author":"Gatilov","year":"2013","journal-title":"J. Reliab. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1080\/17513472.2011.634320","article-title":"The Jordan curve theorem is non-trivial","volume":"5","author":"Ross","year":"2011","journal-title":"J. Math. Arts"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(81)90103-1","article-title":"A space-optimal solution of general region location","volume":"16","author":"Edelsbrunner","year":"1981","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","article-title":"Optimal search in planar subdivisions","volume":"12","author":"Kirkpatrick","year":"1983","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Guibas, L., Ramshaw, L., and Stolfi, J. (1983, January 7\u20139). A kinetic framework for computational geometry. Proceedings of the 24th Annual Symposium on Foundations of Computer Science (1983), Washington, DC, USA.","DOI":"10.1109\/SFCS.1983.1"},{"key":"ref_24","unstructured":"Jackowski, B. (2012). Computing the area and winding number for a B\u00e9zier curve. TUGboat, Tex Users Group. Available online: https:\/\/tug.org\/TUGboat\/tb33-1\/tb103jackowski.pdf."},{"key":"ref_25","unstructured":"Santos, V. (1995). Robot Autonomous Navigation: Sensorial Data Interpretation and Local Navigation. [Ph.D. Thesis, Universidade de Aveiro]. Available online: http:\/\/hdl.handle.net\/10773\/17931."},{"key":"ref_26","unstructured":"Wylie, C., and Barrett, L. (1982). Advanced Engineering Mathematics, McGraw-Hill."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kanwal, R. (1996). Linear Integral Equations, Birkh\u00e4user Boston.","DOI":"10.1007\/978-1-4612-0765-8"},{"key":"ref_28","unstructured":"OGC (1999). OpenGIS Simple Features Specification for SQL, Revision 1.1, Open Geospatial Consortium, Inc.. Technical Report."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/10\/444\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:11:16Z","timestamp":1760112676000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/10\/444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,5]]},"references-count":28,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,10]]}},"alternative-id":["a17100444"],"URL":"https:\/\/doi.org\/10.3390\/a17100444","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,10,5]]}}}