보로 노이 다이어그램을 구성하기 위해 Fortunes algorithm을 구현해야합니다.Fortunes 알고리즘 - Beach Line 데이터 구조
알고리즘의 중요한 부분은 "해변 선 데이터 구조"라는 데이터 구조입니다.
AVL과 비슷하지만 데이터가 리프에만 저장되는 방식으로 다른 이진 밸런싱 트리입니다 (다른 차이점이 있지만 질문에는 중요하지 않음).
어떻게 구현해야할지 모르겠습니다. 분명히 AVL을 "있는 그대로"사용하면 AVL 트리 노드가 내부 노드가 될 수 있고 그 반대로도 균형을 유지할 수 있기 때문에 작동하지 않습니다.
위키피디아의 다른 알려진 데이터 구조를 살펴 보았으나 아무도 필요에 맞지 않았습니다. 링크드리스트로 이것을 수행하는 몇 가지 구현을 보았습니다.하지만 링크드리스트 검색이 O (n)이고 알고리즘이 효율적이기 위해서는 O (log n)이어야하므로 좋지 않습니다.
잎은 사실 (단일) 점과 이벤트 구조의 내부 노드 ("해변 선 나무")는 포물선/호가 서로 나란히 놓인 점의 정렬 된 튜플을 저장합니다. P 형태를 가리키는 포물선 P B (이들 두 포물선의 교차), 내부 노드 저장 명령 튜플 (P , P 형성 포물선의 왼쪽에 놓여 있다면 b).
분명히 AVL을 사용하면 AVL 트리 노드가 내부 노드가되거나 내부 노드가 될 수 있기 때문에 "현재 상태 그대로"는 작동하지 않습니다.
AVL 트리에 다른 유형의 개체를 저장하는 것에 대해 걱정이된다면 간단한 계획은 나뭇잎을 튜플로 저장하는 것입니다. 그래서 점 P J 잎으로 저장하지 않지만, 대신 튜플 (P J, P J)를 저장합니다. P J 만약 잎이 이벤트 트리 (해변 라인)에서 사라지고, 그 부모 (P J P 내가)한, 단순히 (P J로 부모를 변경, P J)는 물론 그 부모는 필요로한다 는 (P J? P )행 (P I 012에서 변경 될, P ?) 등등. 일반 AVL 트리와 마찬가지로 나무를 걷고 변경 및/또는 균형을 조정해야하는 내부 노드를 수정합니다.
알고리즘의 올바른 구현은 SO 응답에 쉽게 기록 할 수 없다는 점에 유의하십시오.알고리즘에 사용 된 데이터 구조에 대한 설명을 포함하여 전체 알고리즘에 대한 적절한 설명은 Computational geometry: algorithms and applications by Mark de Berg et al.을 참조하십시오. 7 장은 보로 노이 다이어그램에만 적용됩니다.