[📜일지] 통로 제작을 위한 delaunay-triangulation

[밤샘싫어요(2dmschd7)]

방을 만들고 균일하게 퍼트리는 걸 구현했다.

이번엔 방의 통로를 만들기 전에, 연결구조를 만들 것이다.

방의 통로는 너무 길거나, 다른 통로를 크로스하면 안된다.

즉, "좋은 구조"를 가져야 한다. 

= delaunay-triangulation이 적절하다. (사실 찾아본 자료에서 쓰길래 찾아봤는데 괜찮더라.)

들로네 삼각분할을 구현하는 알고리즘은 bowyer-watson algorithm이 있다. 

설명은 걍 저거 그대로 키워드로 써서 검색하면 나보다 200배 잘하는 똑똑이들이 써놓은 글이 있으니 그걸 참고하면 좋을 것 같다. 

참고자료 링크는 이렇고

https://theor.xyz/mapgen/delaunay-triangulation-triangle-storage/

https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm#Description

 

= bowyer-watson 알고리즘

 

https://github.com/sergarrido/random/tree/master/circle3d

 

= 외접원 관련(걍 외심이랑 삼각형의 각 정점간의 거리는 모두 동일하다는 아이디어를 그대로 연립방정식으로 옮긴 거임.)

 

하튼 구현한 건 이렇게 나옴.

= 삼각형이랑 외접구

= 들로네 삼각분할 만든 거.(super-triangle 미제거)

=이건 들로네 삼각분할 구성 과정. 1프레임에 0.25초.

[밤샘싫어요(2dmschd7)]

하이퍼링크 왜 안되는지 모르겠는데, 걍 긁어서 보셈

[익명(119.194)]

'역시 개발자는 달라' 콘

[익명(219.250)]

크큭.. 선이 보인다