Rectangular partition for n-dimensional images with arbitrarily shaped rectilinear objects

Area of Science:

• Computational Geometry
• Computer Science

Background:

• Polygon partitioning is essential for efficient data handling in diverse scientific and artistic fields.
• Decomposition into rectangular components aids analysis, manipulation, and retrieval.

Purpose of the Study:

• To present novel, simple algorithms for decomposing n-dimensional rectilinear shapes into non-overlapping rectangular sub-objects.
• To evaluate the efficiency and success rate of these decomposition methods.

Main Methods:

• Developed three distinct algorithms for rectilinear shape decomposition.
• Tested algorithms on 13 binary images across 1-4 dimensions, including shapes with holes.
• Randomized starting points for decomposition and conducted 5 test runs per image.

Main Results:

• All three proposed methods achieved a 100% success rate in decomposing rectilinear shapes.
• Two methods completed decomposition in under 40 milliseconds, while the third took approximately 11 seconds.
• Successfully divided n-dimensional rectilinear shapes, including those with holes, into rectangular components.

Conclusions:

• The presented algorithms effectively partition n-dimensional rectilinear shapes into rectangular components.
• The methods are robust, handling complex shapes and achieving high efficiency, particularly for two of the algorithms.