Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons
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 polyg...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-10-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2073-8994/10/10/477 |
| _version_ | 1811184689013063680 |
|---|---|
| author | Jianqiang Hao Jianzhi Sun Yi Chen Qiang Cai Li Tan |
| author_facet | Jianqiang Hao Jianzhi Sun Yi Chen Qiang Cai Li Tan |
| author_sort | Jianqiang Hao |
| collection | DOAJ |
| description | 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 − y i + 1 ) ( x p − x i ) − ( y i − y p ) ( x i + 1 − 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. |
| first_indexed | 2024-04-11T13:16:39Z |
| format | Article |
| id | doaj.art-0dde8e6068684aa8ae566230d14b7dd6 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-11T13:16:39Z |
| publishDate | 2018-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-0dde8e6068684aa8ae566230d14b7dd62022-12-22T04:22:22ZengMDPI AGSymmetry2073-89942018-10-01101047710.3390/sym10100477sym10100477Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on PolygonsJianqiang Hao0Jianzhi Sun1Yi Chen2Qiang Cai3Li Tan4Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, ChinaBeijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, ChinaBeijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, ChinaBeijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, ChinaBeijing Key Laboratory of Big Data Technology for Food Safety, Beijing Technology and Business University, Beijing 100048, ChinaThis 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 − y i + 1 ) ( x p − x i ) − ( y i − y p ) ( x i + 1 − 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.http://www.mdpi.com/2073-8994/10/10/4773D printingpoint-in-polygonboolean operationscodeprobabilityparallel |
| spellingShingle | Jianqiang Hao Jianzhi Sun Yi Chen Qiang Cai Li Tan Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons Symmetry 3D printing point-in-polygon boolean operations code probability parallel |
| title | Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons |
| title_full | Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons |
| title_fullStr | Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons |
| title_full_unstemmed | Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons |
| title_short | Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons |
| title_sort | optimal reliable point in polygon test and differential coding boolean operations on polygons |
| topic | 3D printing point-in-polygon boolean operations code probability parallel |
| url | http://www.mdpi.com/2073-8994/10/10/477 |
| work_keys_str_mv | AT jianqianghao optimalreliablepointinpolygontestanddifferentialcodingbooleanoperationsonpolygons AT jianzhisun optimalreliablepointinpolygontestanddifferentialcodingbooleanoperationsonpolygons AT yichen optimalreliablepointinpolygontestanddifferentialcodingbooleanoperationsonpolygons AT qiangcai optimalreliablepointinpolygontestanddifferentialcodingbooleanoperationsonpolygons AT litan optimalreliablepointinpolygontestanddifferentialcodingbooleanoperationsonpolygons |