모서리의 고정 길이가 최대 인 평면 그래프

Question

2D 공간에서 무작위 점을 생성하고 싶습니다.이 점은 평면 그래프의 노드가됩니다 (Gabriel graph 알고리즘 또는 RNG를 사용하여 작성).

이 작업을 수행하기 위해 자바 코드를 작성했지만 해결해야 할 두 가지 어려운 문제가 있습니다.

1) 나는 그래프의 모든 모서리 내가 그래프의 얼굴을 알고 싶어 한 후 지정된 임계 값

2)보다 더 긴 것을 필요, 얼굴 가장자리에 의해 연결된 노드의 모음입니다. 얼굴에는 다른 노드가 포함되어 있지 않습니다. 아래 이미지의 라벨은 라벨 (F1, F2 ...)에 의해 서명됩니다.

어떻게이 두 가지를 할 수 있습니까? 일부 알고리즘? 이미 알려진 몇 가지 방법이 있습니까?

이 다음은 점의 수에 약간의 변화를 견딜 수있는 경우

http://imageshack.us/photo/my-images/688/immagineps.png/

Answer 1

1. 을 만들 내가해야 그래프의 예 거기, 당신은 당신의 가브리엘 그래프 알고리즘을 수정할 수 있습니다 증분 (대부분의 노력은 Delaunay 알고리즘을 증분으로 만들 것입니다.) 그리고 나서 가장자리가 너무 길 때마다 그 가장자리를 지닌 원 안에 임의의 점을 직경으로 삽입하십시오.

2. 평면 그래프의 가장 편리한 데이터 구조는 가장자리 중심입니다 (예 : doubly-connected edge list 및 quad-edge 표현). Delaunay 단계에서이 유형의 데이터 구조를 아직 사용하고 있지 않다면 왜 그런지는 상상할 수 없습니다. 각 꼭지점의 나가는 연결을 각도별로 정렬 할 수 있습니다. 거기에서 반쪽 가장자리를 취하고 같은면의 다음 반쪽 가장자리를 반 시계 방향으로 반환하는 함수를 구현하는 것은 쉽습니다. 이제 모든 반쪽 가장자리를 반복하고, 아직 방문하지 않은 각 반쪽 가장자리가 시작한 곳으로 돌아올 때까지 얼굴 주위를 반복합니다. 내부 반복의 모든 반쪽 가장자리에 하나의면으로 레이블을 지정합니다.