가능한 가장 작은 다각형에 가장자리를 할당하는 알고리즘?

Question

저는 절차 적 도시 생성기를 설계하고 있으며, 생성 과정의 첫 번째 단계는 도시 거리 생성입니다. 이 거리는 직선에서 한 점으로 뻗어 나간 다음, 같은 방향으로 분기, 회전 또는 계속할 수 있습니다. 거리가 다른 거리를 공격하는 경우 성장을 멈추거나 가장 가까운 교차점에 연결할 수 있습니다.

저는 접합점을 정점으로, 거리를 가장자리로 생각해 왔습니다. 이것으로 네트워크를 가능한 가장 작은 폴리곤 (예 : 모든면에 거리로 둘러싸인 공간)의 컬렉션으로 분해 할 수 있어야합니다.

사각 거리는 다각형에 침투 할 수 있지만 거리에 양쪽에 2 개의 교차점이있는 경우이를 다각형의 가장자리로 갖고 싶습니다. 처리하기 전에 고려 대상에서 "데드 엔드"(하나의 가장자리 만 붙이는 버텍스) 거리를 쉽게 제거 할 수 있으므로 문제가되지 않습니다.

그래서 정점과 가장자리의 컬렉션이 주어지면 작은 폴리곤으로 분할하는 좋은 방법은 무엇입니까? 폴리곤이 볼록 또는 오목면 중요하지 않습니다. 주로 도시의 비트를로드하고로드되거나 언로드 된 영역을 표시하고 시뮬레이션을 위해 도시의 비트를 선택적으로 선택하는 방법으로 사용됩니다.

Answer 1

가장자리가 정렬되어 있는지 확인하십시오. 예 : 정점 A가 정점 B에 연결되면 두 가장자리 AB와 BA가 있습니다.

1) 임의의 정점을 선택하고 현재의 정점이되도록 A. A와

2) 이동을 호출합니다.

3) 현재의 정점에 연결된 오른쪽 정점을 선택하고 B는 현재 정점 그래서)

4 B.

호출이 함께 여행한다.

5) 가장자리 AB를 제거하여 다시 이동할 수 없도록합니다.

6) 우리가하지 다시 시작 정점의 경우는 우리가 다시 시작 정점에서 우리는 작은 다각형을 발견 한 경우) 3.

7 단계로 이동합니다.

8) 아직 가장자리가있는 상태에서 1 단계로 돌아 가기