에지 목록을 DCEL로 변환하는 방법

Question

다각형의 삼각 측량을 maket하려고합니다. 문제는 가장자리 목록의 형태로 삼각 측량의 표현을 얻지 만 DCEL (이중으로 연결된 가장자리 목록)을 가져와야한다는 것입니다. 가장자리 목록을 DCEL로 변환하는 빠른 알고리즘이 있습니까?

Answer 1

항상 분명한 방법이 있습니다. 모든 목록 항목에 뒤로 링크 추가 : 두 개의 반복자를 사용하여 한 번에 한 번씩 다른 목록 뒤에 한 번 걸어보고 뒤로 링크를 추가하십시오.

---

심지어 더 간단하면 std::list class을 사용하는 것입니다. DCEL이므로 현재 목록을 std::list으로 변환 할 수 있습니다.