{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T07:15:12Z","timestamp":1782544512019,"version":"3.54.5"},"reference-count":33,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,11]],"date-time":"2018-10-11T00:00:00Z","timestamp":1539216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>This paper provides a full theoretical and experimental analysis of a serial algorithm for the point-in-polygon test, which requires less running time than previous algorithms and can handle all degenerate cases. The serial algorithm can quickly determine whether a point is inside or outside a polygon and accurately determine the contours of input polygon. It describes all degenerate cases and simultaneously provides a corresponding solution to each degenerate case to ensure the stability and reliability. This also creates the prerequisites and basis for our novel boolean operations algorithm that inherits all the benefits of the serial algorithm. Using geometric probability and straight-line equation     F  ( P )  =  (  y i  \u2212  y  i + 1   )   (  x p  \u2212  x i  )  \u2212  (  y i  \u2212  y p  )   (  x  i + 1   \u2212  x i  )     , it optimizes our two algorithms that avoid the division operation and do not need to compute any intersection points. Our algorithms are applicable to any polygon that may be self-intersecting or with holes nested to any level of depth. They do not have to sort the vertices clockwise or counterclockwise beforehand. Consequently, they process all edges one by one in any order for input polygons. This allows a parallel implementation of each algorithm to be made very easily. We also prove several theorems guaranteeing the correctness of algorithms. To speed up the operations, we assign each vector a number code and derive two iterative formulas using differential calculus. However, the experimental results as well as the theoretical proof show that our serial algorithm for the point-in-polygon test is optimal and the time complexities of all algorithms are linear. Our methods can be extended to three-dimensional space, in particular, they can be applied to 3D printing to improve its performance.<\/jats:p>","DOI":"10.3390\/sym10100477","type":"journal-article","created":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T02:58:04Z","timestamp":1539313084000},"page":"477","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6103-0137","authenticated-orcid":false,"given":"Jianqiang","family":"Hao","sequence":"first","affiliation":[{"name":"Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianzhi","family":"Sun","sequence":"additional","affiliation":[{"name":"Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Chen","sequence":"additional","affiliation":[{"name":"Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qiang","family":"Cai","sequence":"additional","affiliation":[{"name":"Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Tan","sequence":"additional","affiliation":[{"name":"Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2264","DOI":"10.1111\/j.1467-8659.2009.01481.x","article-title":"Robust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processing","volume":"28","author":"Feito","year":"2009","journal-title":"Comput. Graph. Forum"},{"key":"ref_2","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_3","unstructured":"DonaldHearn (1997). Computer Graphics C Version, Prentice Hall."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/B978-0-12-336156-1.50013-6","article-title":"Point in polygon strategies","volume":"994","author":"Haines","year":"1994","journal-title":"Graph. Gems IV"},{"key":"ref_5","unstructured":"Haines, E. (2018, August 07). Graphics Gems Repository. Available online: http:\/\/tog.acm.org\/resources\/GraphicsGems\/."},{"key":"ref_6","unstructured":"Galacticomm (2018, August 07). A Point about Polygons (Article in 3\/97 Linux Journal). Available online: http:\/\/www.visibone.com\/inpoly\/."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/965105.807462","article-title":"Polygon comparison using a graph representation","volume":"14","author":"Weiler","year":"1980","journal-title":"SIGGRAPH Comput. Graph."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1080\/02763869.2013.749139","article-title":"3D Printing: Making Things at the Library","volume":"32","author":"Hoy","year":"2013","journal-title":"Med. Ref. Serv. Q."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1145\/358656.358681","article-title":"Plane-sweep algorithms for intersecting geometric figures","volume":"25","author":"Nievergelt","year":"1982","journal-title":"Commun. ACM"},{"key":"ref_10","unstructured":"Galetzka, M., and Glauner, P.O. (arXiv, 2012). A correct even-odd algorithm for the point-in-polygon (PIP) problem for complex polygons, arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.cag.2005.03.001","article-title":"2D point-in-polygon test by classifying edges into layers","volume":"29","author":"Wang","year":"2005","journal-title":"Comput. Graph."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/0010-4485(90)90039-F","article-title":"Curve intersection using B\u00e9zier clipping","volume":"22","author":"Sederberg","year":"1990","journal-title":"Comput. Aided Des."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.cagd.2007.01.003","article-title":"Computing roots of polynomials by quadratic clipping","volume":"24","year":"2007","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.cagd.2011.07.002","article-title":"Global solutions of well-constrained transcendental systems using expression trees and a single solution test","volume":"29","author":"Aizenshtein","year":"2012","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.cad.2017.05.023","article-title":"Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver","volume":"90","author":"Elber","year":"2017","journal-title":"Comput. Aided Des."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1016\/j.cageo.2005.03.009","article-title":"Point-in-polygon tests for geometric buffers","volume":"31","year":"2005","journal-title":"Comput. Geosci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.cageo.2009.06.008","article-title":"A point-in-polygon method based on a quasi-closest point","volume":"36","author":"Yang","year":"2010","journal-title":"Comput. Geosci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0097-8493(01)00180-7","article-title":"A fast trapezoidation technique for planar polygons","volume":"26","author":"Lorenzetto","year":"2002","journal-title":"Comput. Graph."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.cag.2006.08.015","article-title":"The multi-L-REP decomposition and its application to a point-in-polygon inclusion test","volume":"30","author":"Rueda","year":"2006","journal-title":"Comput. Graph."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1109\/TVCG.2010.246","article-title":"EL-REP: A New 2D Geometric Decomposition Scheme and Its Applications","volume":"17","author":"Rueda","year":"2011","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1111\/j.1467-8659.1989.tb00484.x","article-title":"Algorithm for Clpping Arbitrary Polygons","volume":"8","author":"Andreev","year":"1989","journal-title":"Comput. Graph. Forum"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01994114","article-title":"An efficient algorithm for line and polygon clipping","volume":"7","author":"Rappoport","year":"1991","journal-title":"Vis. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/274363.274364","article-title":"Efficient clipping of arbitrary polygons","volume":"17","author":"Greiner","year":"1998","journal-title":"ACM Trans. Graph."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/965141.563896","article-title":"Hidden surface removal using polygon area sorting","volume":"11","author":"Weiler","year":"1977","journal-title":"SIGGRAPH Comput. Graph."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/129902.129906","article-title":"A generic solution to polygon clipping","volume":"35","author":"Vatti","year":"1992","journal-title":"Commun. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1016\/j.cageo.2008.08.009","article-title":"A new algorithm for computing Boolean operations on polygons","volume":"35","author":"Rueda","year":"2009","journal-title":"Comput. Geosci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1016\/S0097-8493(98)00067-3","article-title":"Geometric modelling based on simplicial chains","volume":"22","author":"Feito","year":"1998","journal-title":"Comput. Graph."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1016\/S0097-8493(00)00090-X","article-title":"Boolean operations on general planar polygons","volume":"24","author":"Rivero","year":"2000","journal-title":"Comput. Graph."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.cag.2004.11.001","article-title":"A new algorithm for Boolean operations on general polygons","volume":"29","author":"Peng","year":"2005","journal-title":"Comput. Graph."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1108\/02644409710188600","article-title":"Automated procedures for Boolean operations on finite element meshes","volume":"14","author":"Graysmith","year":"1997","journal-title":"Eng. Comput."},{"key":"ref_31","unstructured":"CGAL4.2 (2018, August 07). CGAL\u2014Computational Geometry Algorithms Library. Available online: http:\/\/www.cgal.org\/."},{"key":"ref_32","unstructured":"GPC, A.M. (2018, August 07). GPC General Polygon Clipper Library from The University of Manchester. Available online: http:\/\/www.cs.man.ac.uk\/toby\/alan\/software\/."},{"key":"ref_33","unstructured":"Clipper4.6.3 (2018, August 07). Clipper\u2014An Open Source Freeware Polygon Clipping Library. Available online: http:\/\/www.angusj.com\/delphi\/clipper.php."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/10\/477\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:24:55Z","timestamp":1760196295000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/10\/477"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,11]]},"references-count":33,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["sym10100477"],"URL":"https:\/\/doi.org\/10.3390\/sym10100477","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,11]]}}}