💡 Cho một tập hợp các đoạn thẳng nối với nhau để tạo thành một đường gấp khúc liên tục. Tìm một tập hợp các đường cong Bézier khớp với tập hợp các đoạn thẳng này.
Lý do mình tìm đến thuật toán này khá thú vị. Lúc trước, khá lâu cách đây rồi, mình đang viết một con game trên Corona SDK. Gameplay của dòng game này khá nổi lúc ấy. Đại khái, có một cái sân bay với một số đường băng nhất định. Các máy bay sẽ lần lượt bay về sân bay. Mục tiêu của người chơi là phải dùng ngón tay vẽ một đường bay để dẫn dắt những chiếc máy bay hạ cánh vào các đường băng.
Tuy nhiên, mình gặp một khó khăn phải giải quyết đó là khi dùng tay vẽ đường (trên bề mặt điện thoại) thì những đường cong này không mượt mà, ngược lại rất góc cạnh khiến cho những chiếc máy bay đi theo đường vẽ này chuyển hướng rất gấp, không được mượt mà. Vì thế, mình cần một thuật toán để “làm mềm” các đường vẽ này, và mình đã tìm thấy thuật toán của Philip J. Schneider’s “Algorithm for Automatically Fitting Digitized Curves” từ cuốn sách “Graphics Gems 1”.
Mình tìm thấy mấy bài viết của chính mình về vấn đề này (tìm đường cong khớp với tập điểm đã cho) trong 1 blog wordpress khoảng mười mấy năm về trước:
Tuy nhiên hồi đó mình code bằng LUA . Bây giờ mình đã chuyển lại bằng javascript với library P5JS:
Demo ở đây: https://quangnle.github.io/curve_fitting_p5js/
Source github: https://github.com/quangnle/curve_fitting_p5js
Paper tại đây
Tất cả các bài viết về tất cả các kỹ thuật liên quan sẽ được trình bày trong series này.