cách kiểm tra bộ sưu tập hình chữ nhật cho lỗ và giao lộ?

Question

Tôi đang tìm cách kiểm tra một bộ sưu tập (Java TreeSet) của hình chữ nhật - được thực hiện bởi một lớp Java "có thể so sánh" bằng cách sử dụng phạm vi google cho phạm vi x và y - cho giao lộ và lỗ. tôi biết rằng một tùy chọn có thể là sử dụng kd-tree, nhưng tôi không biết cách xây dựng một cây kd như thế nào (đối với hình chữ nhật nó phải là 4d, phải không?) Và cách giải quyết vấn đề (giao lộ) , lỗ).

sắp xếp ưu tiên trục x trên trục y.

EDIT: (cố gắng giải quyết vấn đề): trường hợp sử dụng là tạo các bảng tùy ý (bao gồm 2 hoặc 3 khối hình chữ nhật "tiêu đề", "cột trước", "dữ liệu"). tôi phải đảm bảo rằng không có nút giao và lỗ (tức là được cung cấp bởi html không hợp lệ hoặc các nguồn dữ liệu bảng khác) trong mỗi khối (ngoài khối này phải phù hợp với nhau). Hiện tại (chỉ có một ý tưởng) tôi cố gắng lưu trong một mảng 2d mà các vị trí (x, y) bị chiếm đóng. ở cuối tất cả các vị trí phải được chiếm chính xác một lần.

Answer 1

Có một số cách tiếp cận để giải quyết loại vấn đề này, mỗi vấn đề có ưu và nhược điểm khác nhau. Dưới đây là một số trong số họ:

Rectangle Pair Intersection + Diện tích Sum

Nhìn vào mỗi cặp hình chữ nhật - nếu hai hình chữ nhật giao nhau, có sự trùng lặp. Thêm các vùng hình chữ nhật và kiểm tra xem tổng có khớp với vùng vải không - nếu các vùng không khớp, có một khoảng trống.

Tranh

Đây là phương pháp mà bạn đề cập: tạo ra một mảng 2D có kích thước của canvas của bạn. Sau đó, lặp qua các hình chữ nhật và "vẽ" chúng vào mảng.

Một tối ưu hóa cho phương pháp này là phối hợp nén. Giả sử bạn có hình chữ nhật [(10,20), (15,25)] và [(7,3), (15, 25)]. Bạn có thể xem các tọa độ x riêng biệt (7, 10, 15) và remap chúng thành (0, 1, 2) và các tọa độ y riêng biệt (3, 20, 25) và remap chúng thành (0, 1, 2). Sau đó, bạn còn lại với các hình chữ nhật [(1, 1), (2, 2)] và [(0,0), (2,2)], do đó bạn chỉ cần một mảng 3x3 cho bức tranh, thay vì một 26x26 mảng.

Sweep Dòng Algorithm

Sweep một đường từ trái sang phải, dừng lại tại các điểm 'thú vị', và theo dõi các khu vực đang chiếm đóng.

2D Phạm vi Trees

Một cấu trúc dữ liệu mà hiệu quả có thể thực hiện truy vấn trên phạm vi hình chữ nhật.

Chọn thứ nhất để chọn?

Nó phụ thuộc vào số lượng hình chữ nhật mà bạn có, cách thức chúng được phân phối trong khu vực, nhanh như thế nào thuật toán của bạn phải là, bao nhiêu phức tạp bạn sẵn sàng gánh vác vv Hai thuật toán đầu tiên mà tôi đã đề cập là đơn giản hơn nhiều so với hai thứ hai, vì vậy tôi khuyên bạn nên bắt đầu từ đó.

More Info

Nếu bạn muốn tìm hiểu thêm về các thuật toán, hãy thử tìm kiếm "hình chữ nhật công đoàn" trên mạng. Giải pháp hiệu quả nhất là thuật toán dòng quét.

Dưới đây là một vài tài liệu tham khảo về các thuật toán dòng quét:

1. What is an Efficient algorithm to find Area of Overlapping Rectangles
2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
3. J. L. Bentley, thuật toán cho các vấn đề hình chữ nhật Klee của. Ghi chú chưa xuất bản, Khoa Khoa học Máy tính, Đại học Carnegie Mellon, 1977

Tham chiếu 3. thường được coi là nguồn gốc của thuật toán quét đường cho liên kết hình chữ nhật, nhưng tôi phải thừa nhận rằng tôi không thực sự tìm thấy giấy trực tuyến, có lẽ vì nó là "Chưa xuất bản" ...