Triangulation

Triangulation하면 그 dual은 트리이다. 이게 유용한 성질임. N^2알고리즘은 다음과 같다. Simple Polygon에서 Ear Set을 관리하면서, 아무 Ear나 삼각화해서 제거후 그 인접한 두개의 정점에 대해 Ear Test해서 Ear Set Update한다. 반복하면 끝. Ear Test(l,x,r) = convex(l,x,r) and line(l,r) does not intersect with any edge. https://en.wikipedia.org/wiki/Polygon_triangulation 위키 대충본거로는 Ear Clipping Method에 자료구조하면 NlogN도 되는듯?