Constrained Delaunay Triangulation定義的了解

• Delaunay Triangulation 定義：

  Let S be a set of points in the plane. A triangulation T is a Delaunay triangulation of S if for each edge e of T there exists a circle c with the following properties:

  (1) The endpoints of edge e are on the boundary of c.

  (2) No other vertex of S is in the interior of c.

  If no four points of S are cocircular then the Delaunay triangulation is unique.

  大白話： 設S為源點集，若一個三角剖分T滿足以下條件，則稱其為點集S的一個Delaunay三角剖分：對T中的每一條邊e，都存在一個圓c，1-邊e的兩個端點都在圓c上(感覺這個地方有問題，應該是對于T中的每一個三角形，其外接圓内不包含任何其他頂點)，2-并且S中所有其他的頂點都不在圓内(可以在圓上或者在圓外)。如果所有頂點中，沒有四個或四個以上來自S的頂點在這樣的伴生圓上，那麼這個Delaunay剖分是唯一的。

• Constrained Delaunay Triangulation 定義：

  Let G be a straight-line planar graph. A triangulation T is a constrained Delaunay triangulation (CDT) of G if each edge of G is an edge of T and for each remaining edge e of T there exists a circle c with the following properties:

  (1) The endpoints of edge e are on the boundary of c.

  (2) If any vertex v of G is in the interior of c then it cannot be “seen” from at least one of the endpoints of e (i.e., if you draw the line segments from v to each endpoint of e then at least one of the line segments crosses an edge of G).

  大白話： 若三角剖分滿足以下條件，則稱其為限制性Delaunay三角剖分：若G中的每一條邊(輸入中的限制邊)都在最後生成的三角剖分T的邊中，并且所有新生成的邊都滿足1-新生成的邊e的端點都在對應伴生圓上，2-若圓内有其他頂點(即除組成此三角外的其他頂點)，則此邊e對圓内的頂點v是不可見的。

  我的了解： 如下圖(圖檔來自下方論文，進行了修改)所示，若三角劃分T中的一個三角形t，其外接圓中包含其他頂點(如圖中綠點)，則t中的三條邊對于此綠點來說都是不可見的(即t的任意邊的兩個端點與綠點連線必然會和其他邊相交，如藍色虛線所示，其與源輸入的限制邊相交，可以了解為圖中的粗邊擋住了綠點，使得三角形無法通過光線/直線看到綠點)，滿足這樣條件的三角剖分叫限制性Delaunay三角剖分。若T中所有的三角形t，其外接圓内都不存在其他的點，則這樣的三角剖分就成為了Delaunay三角剖分。

  

• 定義來源 :

  L Paul Chew. 1987. Constrained delaunay triangulations. In Proceedings of the third

  annual symposium on Computational geometry. ACM, 215–222