제한된 delaunay 삼각 측량에서 제한 삽입

Question

제한된 delaunay 삼각 측량에 제약 조건을 삽입하는 단계 중 하나는 제약 조건에 의해 교차 된 삼각형을 제거하여 왼쪽 cavity를 retriangating하는 것입니다.

다음 이미지에서 구속 조건 u (A-F)가 삼각 측량에 삽입되고 삼각형이 파란색으로 교차합니다. 따라서 파란색 영역은 후방 영역으로 바뀝니다.

즉, 파란색 삼각형이 삼각형 분할에서 제거되고 새 삼각형이 추가되어 삼각형을 제거 할 때 남겨진 구멍을 채 웁니다. 만 이러한 새로운 삼각형없이 (삼각 측량은 (다른 제약 가장자리 제외) U를 제약 조건을 삽입하기 전에 들로네 것을 가정

(제약 U 인), 녹색의 삼각형 자신 들로네 것을 가장자리 AF를해야합니다 녹색 다각형의 정점이 다른 녹색 삼각형의 원 안에있는 경우), 녹색 삼각형을 빨간색 삼각형에 연결하는 가장자리에서 가장자리 뒤집기를 검사/수행해야합니까? 아니면 가장자리 뒤집기가 발생하지 않도록하는 일종의 타당성이 있습니까?

즉, 캐비티 외부의 정점이 새 삼각형의 원 가운데 하나가 될 가능성이 있습니까? (이전에 delaunay 였기 때문에 그러한 꼭지점이 이전에 다른 원 안에 없었던 점에 유의하십시오.

간단히 말해서, 후방 제거 후 캐비티 가장자리에서 가장자리를 뒤집어 확인/수행해야합니까? CDT에 사용

참조 용지 : https://infoscience.epfl.ch/record/100269/files/Kallmann_and_al_Geometric_Modeling_03

는 이미지가 손이었다 있습니다이 그림에서 삼각형은 들로네 보이지 않을 수 있음을 의미한다 GeoGebra의 아닌 실제 삼각 코드를 사용했다. 또한 그림은 시각적 목적을 위해 삼각 측량의 일부만 보여줍니다.

Answer 1

나는 그렇게 생각하지 않는다. 에지 플립은 정렬 된 점 cw 또는 ccw에만 의존합니다.

Answer 2

일부 테스트를 실행 한 후 삼각 측량이 해당 작업 이후에 지연 될 수있는 것처럼 보이므로 가장자리를 대칭 이동해야합니다.

나는 어떤 논문에서 이것을 읽지도 않았고, 어떤 코드에서도 그것을 보지 못했다. 그래서 나는 여전히 틀릴 수도있다.