Cấu trúc dữ liệu tốt nhất để lưu trữ các đa giác tiếp giáp?

Question

Tôi xin lỗi, tôi gặp rất nhiều rắc rối khi diễn đạt câu hỏi này.

Tôi bị kẹt trên cấu trúc dữ liệu (hoặc kết hợp cấu trúc dữ liệu) tôi nên sử dụng để lưu trữ sắp xếp các đa giác giáp nhau (giống như bất kỳ bản đồ thế giới thực nào).

Tôi nên làm rõ: ý tôi muốn làm là di chuyển một điểm với tốc độ cố định thông qua bản đồ (phong cảnh) của các đa giác này. Toàn bộ cảnh quan được bao phủ trong các đa giác - không có không gian nào được phân loại; mỗi điểm trong bản đồ thuộc về một số đa giác. Điều này có nghĩa là tất cả các đường viền đa giác, ở tất cả các cạnh, hoặc đa giác khác hoặc cạnh của bản đồ. Bản đồ được giới hạn, nhưng lý tưởng, không quan trọng bản đồ là bao nhiêu hoặc có bao nhiêu đa giác được biểu diễn. Mỗi đa giác có một tên (điều này là quan trọng, vì mỗi điểm bây giờ thuộc về ít nhất hai đa giác được đặt tên). Điểm di chuyển qua bản đồ phải luôn luôn biết tên của đa giác mà nó nằm ở đó, và điểm cũng cần được thông báo bất cứ khi nào nó đi qua một đường biên từ một đa giác này sang một đa giác khác. (nếu cần thêm bất kỳ giải thích nào khác, vui lòng nhận xét.)

Có cách nào được chấp nhận để thực hiện việc này không?

--EDIT--

Đa giác được cố định. Tất cả các điểm và cạnh sẽ cần phải được mã hóa cứng trước. Các điểm và cạnh sẽ không bao giờ thay đổi không thể đoán trước hoặc ngẫu nhiên (nếu chúng thay đổi, nó sẽ được đáp ứng với một sự kiện cố định không thường xuyên).

Answer 1

Xây dựng a 2D segment tree trong đó mỗi khoảng thời gian 2D tương ứng với hộp giới hạn của đa giác và loại giá trị tương ứng với chính đa giác đó (danh sách các cạnh của nó).

Sau khi tác nhân chuyển từ p1 sang p2, chạy truy vấn cửa sổ đối với cây phân khúc: tìm kiếm tất cả các khoảng 2D (các hộp giới hạn) giao nhau với/chứa trong hình chữ nhật được xác định bởi p1 và p2.

Đối với mỗi đa giác trong các hộp giới hạn này, hãy kiểm tra xem nó có chứa p2 hay không.

Answer 2

Thuật ngữ kỹ thuật mô tả đây là planar straight-line graph, trong đó đại diện phù hợp là doubly connected edge list (DCEL).

Một trong các yêu cầu của cấu trúc dữ liệu của bạn có vẻ là khả năng thực hiện các truy vấn vị trí điểm (nhanh). (Đối với những gì đa giác hiện điểm này thuộc về?) Có những giải pháp cổ điển, trong đó người ta có thể giới thiệu các trapezoidal decomposition.

Tôi không biết giải pháp phù hợp cho các truy vấn "biên giới", tức là tìm các giao lộ với quỹ đạo tuyến tính (có lẽ). Bạn có thể thích nghi từ vấn đề vị trí điểm, nhưng điều này hứa hẹn sẽ phức tạp.

Dù sao, nếu đa giác của bạn có số đỉnh hợp lý, không phải là vấn đề lớn khi tìm tất cả các giao lộ với một đường thẳng nhất định bằng cách thử tất cả các cạnh lần lượt. Sử dụng biểu diễn DCEL, khi bạn rời khỏi đa giác, bạn biết bạn đang nhập đa giác nào.

Nếu tôi là bạn, tôi sẽ bắt đầu với một cấu trúc DCEL, một thuật toán point-in-polygon và thuật toán giao cắt đường-đa giác (về cơ bản là giống nhau).