計算幾何之平面的非點群三角剖分

來自專欄我的圖形學之路1 人贊了文章

一.什麼是三角剖分

假設V是二維實數域上的有限點集，邊e是由點集中的點作為端點構成的封閉線段, E為e的集合。那麼該點集V的一個三角剖分T=(V,E)是一個平面圖G，該平面圖滿足條件：

1.除了端點，平面圖中的邊不包含點集中的任何點。

2.沒有相交邊.

3.平面圖中所有的面都是三角面，且所有三角面的合集是散點集V的凸包。

[注]：多變形的三角割分是計算幾何中的基本問題。

二.什麼是平面三角剖分

平面三角剖分就是指，對於平面圖形，將平面多邊形劃分成一系列不相重疊的三角形且不產生新的頂點。

三.三角剖分的優化準則

四.非點群三角剖分演算法總結

這裡我們主要涉及的是非點群的三角剖分。即，擁有輪廓信息。

根據不同的適用範圍，我們對其進行一個簡單的總結

1.對於普通凸多邊形，沒什麼好說的

2.對於普通凹多邊形

3.對於帶空洞的多邊形：poly2tri庫，和TRIANGLE庫

GTP演算法（General Triangulation of Polygons）

Delaunay

https://blog.csdn.net/npu2017302288/article/details/80460552

https://blog.csdn.net/qq_35776579/article/details/54836612