Attention was focused on Delaunay triangulation for its processed result is whole optimization. While according to the study on some Delaunay triangulation algorithms

there is a bug in a common Delaunay triangulation algorithm[1

2]on 2D arbitrary polygon. According to the judge rule of the algorithm

it is possible to make result of Delaunay triangulation wrong with the effect of the“irregular position”vertex of polygon

“irregular position”vertex is the vertex which is in the candidate vertex set during the processing

but would break the“incircle”rule of classical Delaunay triangulation if that vertex is selected for Delaunay triangle in the end. This question was analyzed and discussed in the paper

and then an improvement upon the algorithm is presented

i.e

adjusting the data structure of algorithm or modifying the judge rule to make the resultant triangle set correct and satisfied

the former method is better than the latter

but it costs more to the original algorithm.