Nếu bạn đang tìm kiếm một thuật toán gần đúng, tôi khuyên bạn nên tìm một thuật toán k-mean hoặc một cụm phân cấp, đặc biệt là đường cong quái vật hoặc đường cong lấp đầy khoảng trống. Trước hết, bạn có thể tính một cây bao trùm tối thiểu của biểu đồ, sau đó loại bỏ các cạnh dài nhất và lớn nhất. Sau đó, cây tạo ra nhiều cây nhỏ và bạn có thể sử dụng phương tiện k để tính toán nhóm điểm, tức là các cụm.
"Thuật toán phân cụm k liên kết đơn ... chính xác là thuật toán của Kruskal ... tương đương với việc tìm MST và xóa k-1 cạnh đắt nhất." Xem ví dụ tại đây: https://stats.stackexchange.com/ câu hỏi / 1475 / visualization-software-for-clustering .
Một ví dụ điển hình cho đường cong quái vật là đường cong hilbert. Dạng cơ bản của đường cong này là hình chữ U và bằng cách sao chép nhiều hình dạng của nó lại với nhau và xoay nó, đường cong sẽ lấp đầy không gian euklidian. Đáng ngạc nhiên là một mã màu xám có thể giúp tìm ra hướng của hình chữ U. Bạn có thể tra cứu đường cong quadtree hilbert chỉ số không gian của Nick bài viết trên blog về các chi tiết khác . Thay vào đó, để tính toán chỉ số của đường cong, bạn có thể kết hợp một mã tứ với nhau như trong bản đồ bing. Khóa quad là duy nhất cho mỗi tọa độ và nó có thể được sử dụng với các hoạt động chuỗi thông thường. Mỗi vị trí trong phím là một phần của đường cong hình chữ U và do đó bạn có thể chọn vùng điểm này từ vùng chọn một phần từ trái sang phải từ phím quad.
Trong hình ảnh này, bạn có thể thấy đa giác màu xanh lục được tìm thấy bằng cách sử dụng đường cong hilbert:
Bạn có thể tìm thấy các lớp php của tôi tại đây: http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html
