Thuật toán để đơn giản hóa đường đi và làm mịn các quỹ đạo 2D

Question

Tôi đang tìm kiếm một thuật toán để đơn giản hóa đường đi và làm mịn cho quỹ đạo 2D. Vì vậy, tôi có một danh sách thứ tự các điểm 2D. Những điểm này nên được đơn giản hóa, ví dụ: bằng thuật toán Ramer – Douglas – Peucker. Nhưng đầu ra phải được mịn, vì vậy đường dẫn kết quả nên được xây dựng từ đường cong Bezier hoặc splines. Có bất kỳ sửa đổi nào của thuật toán Ramer – Douglas – Peucker có thể xử lý điều này không?

Tôi đã tìm thấy thuật toán đơn giản hóa đường dẫn trong thư viện paper.js, thực hiện chính xác những gì tôi đang tìm kiếm: http://paperjs.org/examples/path-simplification/ Nhưng tôi không thể hiểu thuật toán từ mã nguồn javascript chưa được cấp nguồn.

Answer 1

Công việc bạn muốn rơi vào danh mục "lắp đường cong". Có rất nhiều thuật toán khác nhau để phù hợp với đường cong nhưng hầu như tất cả các thuật toán phù hợp với đường cong có thể được chia thành hai loại khác nhau: nội suy và xấp xỉ. Các thuật toán nội suy tạo ra một đường cong đi qua tất cả các điểm dữ liệu chính xác trong khi các thuật toán xấp xỉ tạo ra một đường cong nằm gần các điểm dữ liệu. Tất nhiên, các thuật toán lai cũng tồn tại.

Vì bạn muốn các điểm dữ liệu được làm mịn, bạn nên tìm các thuật toán xấp xỉ. Đối với hai thuật toán bạn đã đề cập: thuật toán RDP và thuật toán Schneider (một trong Paper.js), chúng là cả hai thuật toán xấp xỉ. Vì vậy, về cơ bản bạn có thể sử dụng một trong hai. Đối với RDP, sau khi có được đường dẫn đơn giản, bạn có thể sử dụng tạo một đường cong Catmull Rom spline hoặc Overhauser spline qua các đỉnh của đường được đơn giản hóa để có được một đường cong trơn tru. Tuy nhiên, bạn không có quyền kiểm soát trực tiếp cho độ lệch giữa spline và đỉnh trong đường dẫn ban đầu.

Đối với thuật toán Schneider, nó sẽ bắt đầu bằng cách khớp các điểm dữ liệu bằng một đường cong Bezier khối với các ràng buộc tiếp tuyến kết thúc. Nếu độ lệch cho đường cong kết quả quá lớn, thì nó sẽ chia các điểm dữ liệu thành hai "vùng" và phù hợp với từng vùng dữ liệu với một đường cong Bezier khối với các ràng buộc tiếp tuyến kết thúc. Quá trình này sẽ được lặp lại cho đến khi độ lệch cho tất cả các đường cong Bezier khối là đủ nhỏ.Kết quả là, nó tạo ra một loạt các đường cong Bezier khối kết nối tốt nhất với C1 liên tục (rất có thể nó thực sự là G1 chỉ). Hơn nữa, vì thuật toán này đánh giá các điểm kết thúc từ các điểm dữ liệu gốc, nhiễu trong điểm dữ liệu sẽ ảnh hưởng đến việc đánh giá tiếp tuyến kết thúc và do đó phù hợp Bezier khối.

Nếu bạn có thể dành thời gian trong chủ đề của đường cong phù hợp, bạn nên xem xét ít nhất vuông phù hợp với đường cong B-spline. Điều này sẽ tạo ra một đường cong đầu ra với tính liên tục cao (ví dụ C2 cho đường cong B-spline chẳng hạn). Nếu bạn không có nhiều thời gian để sử dụng, thuật toán của Schneider là một lựa chọn tốt để cân bằng giữa chi phí thực hiện (nếu bạn phải thực hiện lại nó bằng một ngôn ngữ cụ thể) và chất lượng của đường cong.

Answer 2

Những gì bạn đang có lẽ hầu hết sau khi được gọi là Curve Fitting.

Trong khi ramer-Douglas-Peucker thuật toán cơ bản làm mềm 'tiếng ồn' ra khỏi một polyline bằng cách loại bỏ các điểm không cần thiết - một đường cong thuật toán phù hợp sẽ phù hợp với Bút chì đường cong qua những điểm đó.

Here là một ví dụ khá hay trên Youtube và here là giấy gốc mô tả chính thuật toán.

---

Đối với các ví dụ Paper.js:

• This là liên kết Github cho rằng chức năng đặc biệt bạn đề cập và điều này được khá tốt nhận xét. Tài liệu nghiên cứu đã được sử dụng là this.

• Cũng here là một cuộc thảo luận rất ngắn trên mailing list về những gì đã được sử dụng và những gì không (rõ ràng ramer-Douglas-Peucker đã được sử dụng nhưng loại bỏ sau)