Divide-and-Conquer Embedding

摘要

We propose an exact method for embedding a disk-topology triangular mesh onto any convex polygon. The method employs a divide-and-conquer approach, iteratively decomposing the embedding problem into smaller sub-problems that map sub-meshes to convex sub-polygons. The process continues until each triangle in the mesh is naturally embedded into a corresponding 3-sided polygon. The approach is supported by a constructive proof, ensuring its theoretical validity. We translate this proof into a practical algorithm, incorporating various dividing strategies and interpolation weights. Unlike previous methods, our approach preserves the connectivity of the input mesh throughout the embedding process. Extensive experiments demonstrate the efficiency and effectiveness of the proposed method.