https://github.com/liliilli/blog_voronoi



보로노이 다이어그램을 생성하는 알고리즘에는 여러가지가 있는데


대개 들로네 삼각분할로 점들 가지고 삼각형 만들어서, 

각 삼각형의 외접원의 중심을 연결하는 방식으로 보로노이 안쪽 선분을 만들거나 (이게 가장 간단함)

아님 분할 정복으로 만드는 방법도 있는데


내가 짠 거는 Fortune's Algorithm 이라고 하는 라인 스위핑 기법으로 

점들로부터 점진적으로 보로노이 선분을 만드는 방식이 있는데, 이걸 한번 Rust로 짜봤음


알고리즘 이론 자체는 간단한데, 제대로 만들기가 졸라게 어려운 알고리즘이라

알고리즘 논문 자체로만 코드 짜기는 어려웠고 거의 30년 전의 C++ 코드 구현체를 보면서 이식하는 방식으로 짰음 


지금까지는 보로노이 선분만 딱 만들어서 보로노이의 각 영역이 되는 점이 가지게 하는 것 까지만 짜가지고

보로노이 다이어그램의 경계점을 쭉 둘러서 선분으로 취급한다던지 

최적화 해서 진짜 O(nlgn) 안에 처리하게 하는 건 지금부터 구현해야 함  


일단 되는 데까지 다 만들면, 이거 가지고 내비게이션 메쉬 만들어볼까 싶음