DEAALUNAY Triangulation ourselves

zhaozj2021-02-08  226

I finally got a simplified Watson algorithm. I have fun. This is the standard 2-dimensional Watson algorithm. In order to introduce the characteristics of this algorithm. And the Delaunay triangle system. For any given point set on the plane, there is a set of points on the plane The only triangularization, satisfying all triangles minimum internal angles and maximum conditions, in order to in other words, the triangles generated by the triangulation will be as close as possible to the equilateral triangles, usually referred to as the delanay triangulation. The Watson algorithm theory basis is based on the air-proof circle characteristics of delaunay triangulation. This method is stepped. Assuming that the delanay triangulation of the first N nodes has been completed, the item (n 1) new point P is introduced, first check each triangle, determine all of the triangles of the new point, these triangles will constitute one The insertion polygon is inserted into all the original delaunay triangles inserted in the plurality of polygons, and the new point is associated with all the boundary points inserted into the polygon, and several new triangles can be formed, and these triangles form a new triangle together with the originally removed triangle. New delaunay triangulation in points. In fact, it is also a simple contour line program. I still have a Fortran version, more than Basic. Two days, please pay attention.

转载请注明原文地址:https://www.9cbs.com/read-1764.html

New Post(0)