약간의 대각선이있는 모든 다각형면 찾기

Question

우리는 다각형을 가지고 있는데, 가장 아래쪽에서 시작하여 반 시계 방향으로 정점 목록으로 제공됩니다 (points). 동일한 다각형의 대각선이 주어지며 (어느 것도 교차하지 않음), 한 쌍의 점 (diagonals)이 주어집니다.

각면의 정점 목록으로 다각형이 절단 된 모든면을 찾아야합니다.

예 : 출력은 다음과 얼굴을 포함 할 것

: 당신이 눈치 챘을 수도로

face1 = [(-68,-36), (-53,-40), (-39,44)] 
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)] 
... 

는 대각선은 x 축에 대한 monotone polygons에 다각형을 잘라. 어쨌든 이것이 도움이 될 수 있다면.

저는 몇 시간 동안이 문제에 봉착했습니다. 나는 그것에 관련된 어떤 문제도 발견하지 못하는 것 같다. 어떤 도움을 주시면 감사하겠습니다.

편집 : 문제는 그래프의 모든 간단한 사이클 (즉, 코드없는 사이클)을 찾는 것으로 줄일 수 있습니다. 나는이 비슷한 질문을 발견 :

Finding polygons within an undirected Graph

Find all chordless cycles in an undirected graph

그러나, 두 번째에서 허용 솔루션이 작동하지 않습니다.

Answer 1

1. 전체 다각형으로 시작하십시오.

2. 첫 번째 대각선을 취하여 다각형을 두 개로 나눕니다. 하나는 대각선의 첫 번째 점까지의 점과 그 다음 모든 점 (대각선의 두 번째 점 포함)을 갖습니다. 다른 하나는 대각선의 첫 번째 점과 모든 점 (대각선의 두 번째 점 포함)을 갖습니다.

3. 나누어 얻을 것이다 다각형 결정 (대각선이 교차하지 않기 때문에 그것은 단지 하나가 될 수 있습니다)하고 모든 대각선 때까지 반복 3. 2.

4. 단계에서 설명한 좋아 분할, 다음 대각선을 가지고 처리됩니다.