AbstractWe propose a novel image triangulation method to reduce the complexity of image triangulation under the color error‐bounded constraint and the triangle quality constraint. Meanwhile, we realize a variety of visual effects by supporting different types of triangles (e.g., linear or curved) and color approximation functions (e.g., constant, linear, or quadratic). To adapt to these discontinuous and combinatorial objectives and constraints, we formulate it as a constrained optimization problem that is solved by a series of tailored local remeshing operations. The feasibility and practicability of our method are demonstrated over various types of images, such as organisms, landscapes, portraits and cartoons. Compared to state‐of‐the‐art methods, our method generates far fewer triangles for the same color error or much smaller color errors using the same number of triangles.