A Robust Divide and Conquer Algorithm for Progressive Medial Axes of Planar Shapes

Area of Science:

• Computational Geometry
• Computer Graphics
• Shape Analysis

Background:

• Medial axis is crucial for shape representation and analysis.
• Progressive medial axis is needed for large, high-resolution shapes.
• Existing methods lack efficiency for large-scale data.

Purpose of the Study:

• To propose a fast and robust geometric algorithm for computing progressive medial axes.
• To enable detailed shape analysis of large-scale planar shapes.
• To introduce a novel approach for merging medial axes.

Main Methods:

• Developed a novel structural analysis for merging medial axes of two planar shapes along a shared boundary.
• Separated topological structure analysis from numerical computation for robustness.
• Implemented a progressive approach starting from low-resolution shapes.

Main Results:

• Achieved a time complexity of O(n lognv) for merging medial axes.
• Demonstrated robustness by decoupling topological and numerical aspects.
• Validated efficiency and effectiveness on large-scale polygonal data.

Conclusions:

• The proposed algorithm offers an efficient and robust solution for progressive medial axis computation.
• This method advances shape analysis capabilities for large-scale datasets.
• The novel merging strategy significantly improves performance compared to state-of-the-art techniques.