Đường cong lắp các điểm chưa được phân loại trên mặt phẳng

Question

Câu hỏi: Làm thế nào để bạn vừa với đường cong để trỏ trên mặt phẳng nếu chúng không có giá trị đơn?

Đối với ví dụ được hiển thị, cách một mẫu khớp với đường cong (như đường màu đen) cho dữ liệu màu xanh ồn ào? Nó tương tự như làm mịn spline, nhưng tôi không biết thứ tự của dữ liệu.

Matlab sẽ được ưa thích, nhưng giả là tốt. Hoặc một con trỏ đến những thuật ngữ chính xác cho vấn đề này sẽ là tuyệt vời.

Cảm ơn

Answer 1

Kiểm tra bài viết này: Shape-preserving least-squares approximation by polynomial parametric spline curves, dường như hiện tại giải pháp. Ngoài ra, hãy xem thư mục ở cuối.

Answer 2

Bạn sẽ phải thực hiện nhiều phụ kiện nối tiếp hoặc splines. Đừng mong đợi bất kỳ thuật toán để có thể làm tất cả của nó trong một đi. Có thể có ít nhất ba đường cong: đường cong đầu tiên đến nút giao, đường vòng và sau đó quay trở lại từ giao lộ về phía trước.

Answer 3

Chỉnh sửa: nvm đã giải thích sai câu hỏi. Tôi sẽ để lại câu trả lời này anyway.

Có thể thử tìm convex hull trong những điểm đầu tiên sau đó phù hợp với thân lồi trên đồng bằng

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html < hình ảnh động --includes java thực hiện http://en.wikipedia.org/wiki/Convex_hull_algorithms

Nếu bạn không muốn hiệu quả có một số triển khai rất đơn giản như phiên bản gói quà tặng là O (n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Phiên bản phân chia và chinh phục là O (nlogn)

Answer 4

Dữ liệu của bạn trông giống như một chiều hai chiều parametric plot của (x,y) làm chức năng của một số thông số cơ bản t. Do đó, bạn có thể thực hiện least-squares vừa với x(t) và y(t) nếu bạn có thể đưa ra mô hình hợp lý cho chúng. Dữ liệu của bạn xuất hiện để mô tả một số limacon.

Answer 5

Vấn đề này là thực sự khó nếu bạn không có đơn đặt hàng. Làm một ô vuông nhỏ nhất trên một số (x (t), y (t)) thật dễ dàng - giả sử bạn biết thứ tự của t.

Có thể bạn sẽ cần một số thuật toán tìm kiếm loại. Một thuật toán di truyền có thể là ok.

Answer 6

bạn có thể thử suy ra thứ tự của các điểm, sau đó áp dụng thủ tục spline. có một sự mơ hồ nơi mà đường cong đi qua chính nó, tất nhiên.

có lẽ cách tiếp cận ngây thơ nhất là tính toán Triangulation Delaunay (thời gian nlogn), từ đó gần đúng Chu kỳ Hamilton khoảng cách tối thiểu Euclidian thông qua các điểm. Bạn vẫn sẽ phải tìm ra nơi 'kết thúc' là. Từ thứ tự bạn có thể áp dụng các kỹ thuật spline.Đối với một tài liệu tham khảo, xem Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete, hoặc giấy Reinelt về chẩn đoán TSP, 1992, hoặc EMST tại Wikipedia

hth,

Answer 7

Đối với xấp xỉ piecewise sử dụng B-splines bạn có thể sử dụng this Matlab gói. Nó hoạt động trên các chế độ tự động và nửa tay.