Pitkäkangas Ville
Centria University of Applied Sciences, Vierimaantie 7, 84100, Ylivieska, Finland.
Heliyon. 2024 Aug 8;10(16):e35956. doi: 10.1016/j.heliyon.2024.e35956. eCollection 2024 Aug 30.
Partitioning two- or multidimensional polygons into rectangular and rectilinear components is a fundamental problem in computational geometry. Rectangular and rectilinear decomposition have multiple applications in various fields of arts as well as sciences, especially when dissecting information into smaller chunks for efficient analysis, manipulation, identification, storage, and retrieval is essential. This article presents three simple yet elegant solutions for splitting geometric shapes (particularly non-diagonal ones) into non-overlapping and rectangular sub-objects. Experimental results suggest that each proposed method can successfully divide n-dimensional rectilinear shapes, including those with holes, into rectangular components containing no background elements. The proposed methods underwent testing on a dataset of 13 binary images, each with 1 … 4 dimensions, and the most extensive image contained 4096 elements. The test session consisted of 5 runs where starting points for decomposition were randomized where applicable. In the worst case, two of the three methods could complete the task in under 40 ms, while this value for the third method was around 11 s. The success rate for all the algorithms was 100 %.
将二维或多维多边形划分为矩形和直线形组件是计算几何中的一个基本问题。矩形和直线形分解在艺术和科学的各个领域都有多种应用，特别是在将信息分解为更小的块以便进行高效分析、操作、识别、存储和检索至关重要的情况下。本文提出了三种简单而优雅的解决方案，用于将几何形状（特别是非对角线形状）拆分为不重叠的矩形子对象。实验结果表明，每种提出的方法都可以成功地将n维直线形形状（包括有孔的形状）划分为不包含背景元素的矩形组件。所提出的方法在一个包含13个二值图像的数据集上进行了测试，每个图像具有1…4维，最复杂的图像包含4096个元素。测试环节包括5次运行，在适用的情况下，分解的起始点是随机的。在最坏的情况下，三种方法中的两种可以在40毫秒内完成任务，而第三种方法的这个值约为11秒。所有算法的成功率均为100%。
