MATHEMATICAL MODEL FOR DETERMINING OVERLAPPING ZONES OF POLYGONS WITH DIFFERENT INFORMATION PRIORITIES IN ECDIS
https://doi.org/10.33815/2313-4763.2025.2.31.156-165
Abstract
This paper introduces Intersection Polygon Contour Analysis (IPCA), an analytical method for detecting and accurately reconstructing the intersection contours of two-dimensional polygons with different information priorities in Electronic Chart Display and Information Systems (ECDIS). As the volume of navigational data from diverse sources such as NavTex and Admiralty Information Overlay (AIO) grows, ship navigators increasingly face overlapping hazard polygons that may differ in priority. For safe voyage planning, it is not enough to know that polygons overlap—the exact geometry of their shared boundaries must also be defined. The proposed IPCA approach is grounded in analytical geometry and delivers precise coordinates for every intersection vertex. Each polygon is first represented as a set of closed contours: external boundaries oriented counter-clockwise and internal holes oriented clockwise. Polygon edges are parameterized, and systems of linear equations are solved to find all intersection points. These points are inserted into the original contours, subdividing edges into ordered segments. Using an oriented-graph framework, valid segments are assembled into closed cycles that capture every intersection contour, including nested holes. Orientation tests then distinguish exterior boundaries from interior voids, thereby preserving full topological accuracy. Unlike many existing methods that rely on rasterization, convexity assumptions, or GPU-based approximations, IPCA provides exact vector geometry and maintains complete nesting relationships, enabling accurate hazard-priority assessment in ECDIS. A prototype Python implementation demonstrates the method’s effectiveness on representative navigation scenarios, where execution speed is sufficient for static pre-voyage planning. IPCA thus offers a robust solution whenever high analytical precision and faithful topological reconstruction are essential. Beyond maritime navigation, it can be applied to geographic information systems, computer-aided design, and other domains that require accurate, detailed intersection contours for complex polygonal data.
References
2. Scala, V. (2024). A new fully projective O(log N) point-in-convex polygon algorithm: a new strategy. The Visual Computer. Vol. 41, No. 7. P. 4839–4850. https://doi.org/10.1007/s00371-024-03693-9.
3. Gao, Y., Wu, B., Luo, J., Qiu, H. (2017). GPU-based Arbitrary Polygon Intersection Area Algorithm. DEStech Transactions on Engineering and Technology Research. https://doi.org/10.12783/dtetr/ismii2017/16652.
4. Foster, E. L., Hormann, K., Popa, R. T. (2019). Clipping simple polygons with degenerate intersections. Computers & Graphics: X. Vol. 2. 100007.
https://doi.org/10.1016/j.cagx.2019.100007.
5. Dimri, S. C., Tiwari, U. K., Ram, M. (2022). An efficient algorithm to clip a 2D-polygon against a rectangular clip window. Applied Mathematics. Vol. 37. P. 147–158. https://doi.org/10.1007/s11766-022-4556-0.
6. Ji, R., Niu, Z., Chen, L. (2025). GPU-Accelerated Algorithm for Polygon Reconstruction. Applied Sciences. 2025. Vol. 15, No. 3. 1111. https://doi.org/10.3390/app15031111.
7. Xu, X., Zhu, S. (2018). Symmetric Sweeping Algorithms for Overlaps of Quadrilateral Meshes of the Same Connectivity. In: Computational Science – ICCS. P. 61–75. https://doi.org/10.1007/978-3-319-93713-7_5.
8. Molano, R., Sancho, J. C., Ávila, M. M., Rodríguez, P. G., Caro, A. (2024). Obtaining the user-defined polygons inside a closed contour with holes. The Visual Computer. 2024. Vol. 40. P. 6369–6387. https://doi.org/10.1007/s00371-023-03170-9.
9. Zhou, C., Li, M. (2019). Performance evaluation of spatial indexing to identify polygon intersection. Geocarto International. 2019. Vol. 35. P. 1–18. https://doi.org/10.1080/10106049.2019.1624987.
10. Gavrilov T. (2017). Programming of the search algorithm for point belonging to the polygon and the mutual non-intersection of the figures. Technology Audit and Production Reserves. 3(3(35)). P. 29–32. https://doi.org/10.15587/2312-8372.2017.105505.
11. Petrovskyi, A. V. (2025). Avtorske svidotstvo №134311 Kompʹyuterna programa «WeatherCheckRoute». 12.03.2025.
12. Petrovskyi, A. V. (2025). Avtorske svidotstvo №133972 Kompʹyuterna programa «S57ViewerVisualCatzocPointEnc». 03.03.2025.
13. Petrovskyi, A. V. (2025). Avtorske svidotstvo №135551 Kompʹyuterna programa «WaveCheckAnalyze». 29.04.2025.
14. Petrovskyi, A. V. (2025). Avtorske svidotstvo №135550 Kompʹyuterna programa «SimulationBridgeMasterE». 29.04.2025.
15. Magalhães, S. V. G., Franklin, W. R., Andrade, M. V. A. (2019). An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters. Computer-Aided Design. 2019. Vol. 111. 102801. https://doi.org/10.1016/j.cad.2019.102801.
16. Cherchi, G., Pellacini, F., Attene, M., Livesu, M. (2022). Interactive and Robust Mesh Booleans. ACM Transactions on Graphics. 2022. https://doi.org/10.1145/3550454.3555460.
17. Gao, Y., Luo, J. et al. (2017). A GPU-Based Rasterization Algorithm for Boolean Operations on Polygons. IEICE Transactions on Information and Systems. https://doi.org/10.1587/transinf.2017EDL8119.
18. Bartels, T., Fisikopoulos, V., Weiser, M. (2023). Fast floating-point filters for robust predicates. Bit Numer Math. Vol. 63. P. 31. https://doi.org/10.1007/s10543-023-00975-x.
