Steiner Points and Steiner Triangulation

http://www.iue.tuwien.ac.at/phd/fleischmann/node54.html

Delaunay 또는 다른 최적 Triangulation에서 스타이너 포인트는 PSLG 나 PLC에서 입력된 정점 정보에 추가된 점이라고 언급한다. (정리 :  스타이너 포인트는 기본점에서 추가된 점이다.)

(PSLG : Planar Straight Line Graph - https://www.cs.cmu.edu/~quake/triangle.defs.html)

? 이름이 추가된 점에 대한 특정 위치를 나타내는 것은 아니다. Refinement는 메쉬 생성 제안을 위해 고려된다.

Delaunay 삼각망에서 스타이너 포인트의 추가는 CG : Computational Geometry 에서 매우 강력함 개념이다.

이것은 (스테이너 포인트의 추가) 는 많은 최적 삼각망 알고리즘 증명에 기본이 되는 표준이다. 

그림 5.6 : 원 중심에 스타이너 포인트 삽입하고,  non-Delaunay 요소를 제거한 후 의 결과이다.

형태가 일그러진 요소의 (badly shaped element) 외심에서 스타이너 포인트를 삽입하는 것은 가장 중요한 기술 중 하나이다.

그렇게 일그러진 요소는 외심에 인접한 요소가 있을수 있기 때문에, 자기자신을 (필수적으로) 거르지 않습니다. (Refinement)

ㅎ

후속 단계에서 바람직하지 않은 요소(외접 구가 비어있지 않기때문에)의 파괴를 보장하는 Delaunay 속성이 복원된다.

두 지점 사이의 최단거리는 반비례하게 감소될수 없다. 

Delaunay 요소의 외접 구는 다른 점을 포함하지 않는다. 따라서 삽입된 외심은  다른지점에 임의로 놓일 수 없습니다.

Refinement는 주어진 한계보다 작은 외접구를 위한 외접원의 삽입을 허용하지 않는다.

이 공간이 부족하여 삽입 프로세스는 종료된다. ?

그림 5.7 : 원본 삼각망 94점에 130삼각망, 128 스테이너 포인트에 376 삼각망

이차원에서 scheme은 한 경계 엣지의 길이가 특점 범위 내에있는 30도와 120도 사이의 각도를 보장하기 위해 고안될 수 있다.

그림 5.6은 외심과 Delaunay 속성의 복원을 삽입하여 제거한 둔각 삼각형을 보여준다.

그림 5.7에서는 삼각망을 볼 수 있다. 주요 아이디어는 외심의 스타이너 점은 circumradius 비율의 가장 짧은 엣지에 바로 영향을 미친다. 

그림 5.8 가장 안좋은 case의 예제는 30도 일 때이다.

그림 5.9 

경계 가장자리를 이등분하고, 외심의 삽입을 무한으로 진행하는 일반적인방법이다.

스타이너 포인트의 삽입을 야기하는 작은 각도가 있다. 

그 삼각형의 외접원의 중심에 점을 삽입한다.