Cho điểm n trên mặt phẳng 2-D, điểm nào để khoảng cách từ tất cả các điểm được thu nhỏ? Điểm này không cần phải từ tập hợp các điểm được đưa ra. Nó là trung tâm hay cái gì khác?Tìm điểm gần nhất từ một tập hợp các điểm trên mặt phẳng
Làm cách nào để tìm tất cả các điểm như vậy (nếu có nhiều điểm) bằng thuật toán?
Điều này được gọi là "Trung tâm khoảng cách" và khác với trung tâm.
Trước tiên, bạn phải xác định thước đo khoảng cách bạn đang sử dụng. Nếu chúng tôi giả sử bạn đang sử dụng số liệu chuẩn của d = sqrt ((x1-x2)^2 + (y1-y2)^2) thì nó không phải là duy nhất và vấn đề là giảm thiểu số tiền này.
Ví dụ dễ nhất để hiển thị câu trả lời này không phải là duy nhất là ví dụ đường thẳng. Bất kỳ điểm nào ở giữa hai điểm đều có tổng khoảng cách bằng nhau từ tất cả các điểm.
Trong 1D, câu trả lời đúng sẽ là bất kỳ câu trả lời nào có cùng số điểm ở bên phải và bên trái. Miễn là điều này là đúng, thì bất kỳ di chuyển sang trái và phải sẽ tăng và giảm các cạnh bên trái và bên phải bằng cùng một lượng, và vì vậy để khoảng cách giống nhau. Điều này cũng chứng minh rằng centroid không nhất thiết là câu trả lời đúng.
Nếu chúng tôi mở rộng sang 2D, điều này không còn là trường hợp - vì sqrt làm cho vấn đề được cân nhắc. Đáng ngạc nhiên với tôi có vẻ như không phải là một thuật toán chuẩn! Trang here dường như sử dụng phương pháp bạo lực. Tôi không bao giờ biết rằng!
Nếu tôi muốn sử dụng thuật toán, tôi sẽ tìm điểm trung bình trong X và Y làm điểm bắt đầu, sau đó sử dụng gradient descent algorithm - điều này sẽ nhận được câu trả lời khá nhanh. Toàn bộ phương trình kết thúc như là một bậc hai, do đó, nó cảm thấy như có phải là một giải pháp chính xác.
Thuật toán brute force trong liên kết đầu tiên của bạn có làm cho điểm trên quả cầu không? –
Không, tôi đã nói độ dốc của các điểm n. Viết chức năng chấm điểm của bạn để nó tính toán tổng khoảng cách đến tất cả các điểm n, sau đó để chức năng gốc của bạn giảm thiểu giá trị này. Tôi sẽ không thêm mã trong trường hợp nó là bài tập về nhà, nó sẽ dễ dàng để viết. –
@Matthijs, khá có thể, tôi không quá khó. Cảm ơn bạn đã chỉ ra. Đó là một câu hỏi thú vị phải không. –
Có thể có nhiều hơn một điểm. Hãy xem xét một chiếc máy bay chỉ có hai điểm trên đó. Những điểm đó mô tả một đoạn thẳng. Bất kỳ điểm nào trên đoạn đường đó sẽ có cùng khoảng cách từ hai điểm cuối.
Vì vậy, làm thế nào để tìm tất cả các điểm như vậy với một thuật toán? – nowonder
Trong thực tế, câu trả lời sẽ là một đa giác đơn giản. Lý do là tổng hàm lồi (như hàm khoảng cách) cũng lồi lõm. Bạn có thể tìm thấy tọa độ chính xác của nó bằng cách bắt đầu từ một hình tam giác và thêm điểm. Tuy nhiên làm nó ngây thơ sẽ là 'n^2'. –
Một bản ngã vũ phu. có thể cung cấp cho bạn kết quả tốt nhất. Thứ nhất, xác định vị trí một hình chữ nhật/bất kỳ tứ giác bao quanh các điểm đầu vào. Cuối cùng, đối với mỗi điểm bên trong hình chữ nhật, tính khoảng cách từ các điểm khác. Tổng hợp khoảng cách của điểm từ tập hợp đầu vào. Nói đây là 'chi phí' của vấn đề. Lặp lại cho mỗi điểm và chọn điểm bằng min. Giá cả.
Thông minh cũng có thể được thêm vào bản ngã. nó có thể loại bỏ các khu vực dựa trên chi phí trung bình, v.v ...
Thats cách tôi sẽ tiếp cận vấn đề ít nhất ... hy vọng nó sẽ giúp ích.
Nhưng nó có độ phức tạp rất cao. Kiểm tra từng điểm bên trong hình chữ nhật, làm thế nào để làm điều đó, các tọa độ điểm có thể là bất kỳ số dấu phẩy động nào. – nowonder
rõ ràng là bạn cần một số kích thước bước, khoảng cách tối thiểu giữa hai điểm liên tiếp, ví dụ đơn giản sử dụng C có thể là: cho (int row = minR; hàng
này được thảo luận chi tiết ở đây http://www.ddj.com/architect/184405252?pgno=1
Điều này thật thú vị nhưng giải quyết được một vấn đề khác. Người hỏi hỏi điểm giảm thiểu khoảng cách đến tất cả các điểm. Bài báo DDJ tìm thấy hai điểm gần nhau nhất. –
Đừng đóng này, các thuật toán hình học là hoàn toàn trong phạm vi stack overflow –
Có bài tập về nhà? Ngoài ra, trong ngôn ngữ nào bạn đang cố gắng thực hiện điều này? – Piskvor
Không có bài tập về nhà. Tôi đang nghiên cứu các thuật toán trên hình học tính toán. Vì vậy, có một nghi ngờ.Tôi đang làm nó trong C. – nowonder