In this paper, we proposed a novel algorithm of automatic image structure completion. Different from traditional image completion algorithms directly copying patches from the unknown region to the damaged part, our completion approach first reconstructs the geometry structures in the damaged region with edges inferred by Constrained Delaunay Triangulation (CDT), and select correct edges through a logistic regression classifier. After that, we fill in the region with structure propagation on edges and texture synthesis for other unstructured part respectively. Several experimental results and comparisons demonstrate the effectiveness of our structure completion approach, especially for images with large missing regions.