선 그리기에서 얼굴을 식별하는 방법은 무엇입니까?

Question

선 그리기는 그래프와 비슷하지만 꼭지점은 x, y 위치입니다. 교차점이 없습니다. 예를 들어 a line drawing like this은 13 개의 정점에 0-12라는 번호가 매겨진 선 그림입니다. 얼굴은 내부에있는 경로가없는 사이클입니다. 예제의 얼굴은, 그 내부에있는 (2,3)라는 이름의 경로가 있기 때문에주기 (0,1,3,5,4,2,0)는 얼굴이 아니다

(0,1,3,2,0), (2,3,5,4,2), (4,5,8,7,4), (7,8,12,11,7) and (0,2,4,7,11,10,9,6,0) 

될 것이다. 사이클 (0,1,3,5,8,12,11,10,9,6,0)도 안쪽에 경로 (0,2,4,7,11)가 있기 때문에 얼굴이 아닙니다. 어떤 알고리즘을 사용하여 예제의 얼굴을 식별 할 수 있습니까?

Answer 1

가장자리가 모두 선분이라고 가정합니다. 모든 평면 그래프는 선분 만 사용하여 그릴 수 있습니다. 또한 그래프가 연결되어 있다고 가정합니다. 이제 알고리즘은 매우 간단하다 :

이 정점은 원래의 그래프에서와 동일하도록, 지시 된 그래프를 두 방향 에지마다 원래 에지 각 방향으로 랜덤으로

시작 하나 (거기 아직 사용되지 않은 가장자리입니다. 그 끝에서 다음 나가는 가장자리를 시계 방향으로 선택하십시오 (또는 시계 반대 방향도 마찬가지입니다. 항상 똑같습니다). 어떤 가장자리인지 결정하려면 평면 삽입의 정점 좌표에서 계산해야합니다. 미리 각 꼭지점에 대해이 엣지 순서를 사전 계산하는 것이 좋습니다.

시작 가장자리에 도달 할 때까지 선택한 가장자리의 끝 부분에서 그 작업을 계속하십시오. 그 시점에서 얼굴을 완성했습니다.

사용되지 않은 가장자리가 없습니다

, 당신은 작업의 efficient implementation을 가지고 부스트와 같은 라이브러리를 사용하여 그래프

의 모든면을 발견 또는 한