Làm thế nào để đại diện cho một đa giác với lỗ (s)?

Question

Nó thường phổ biến để làm việc với đa giác với các đỉnh được sắp xếp CW hoặc CCW trong vectơ (ma trận 2 * 1 hoặc 1 * 2). Tuy nhiên, làm thế nào để nhà nước đa giác với lỗ hổng trong vectơ?

Tôi sẽ áp dụng nhiều quy trình khác nhau trên các đa giác này, vì vậy tôi muốn có cách biểu diễn mà tôi có thể làm việc một cách dễ dàng hoặc hiệu quả (tức là cách nêu loại đa giác đó trong chương trình của tôi để giảm bớt các thuật toán của tôi ?)

đa giác là 2D và tôi đang lập trình trong MATLAB.

CHỈNH SỬA 1: Tôi sẽ tính visibility graph các đa giác này (có hoặc không có lỗ).

Answer 1

Như những người khác đã đề cập, một đa giác có lỗ có thể được biểu diễn như một ranh giới bên ngoài, cộng với không hoặc nhiều ranh giới bên trong, tất cả đều là nonoverlapping *. bên trong/bên ngoài, hãy chắc chắn để xác định interio của bạn r ranh giới theo hướng ngược lại như các ranh giới bên ngoài (ngược chiều kim đồng hồ cho bên ngoài và chiều kim đồng hồ cho nội thất, hoặc ngược lại) sao cho các tích phân đường bao bằng không bên trong các lỗ.

FYI, loại định nghĩa/đại diện đã được chính thức hóa trong Đặc điểm tính năng đơn giản OpenGIS (PDF).

Theo như đại diện:

tôi có lẽ muốn có một mảng di động của ma trận K NX2, nơi mà các phần tử đầu tiên trong mảng di động là ranh giới bên ngoài, và các yếu tố còn lại (nếu có) trong tế bào mảng là ranh giới bên trong. Tôi sẽ sử dụng một mảng ô vì có thể không có cùng số điểm trên mỗi ranh giới.

* nonoverlapping = ngoại trừ các điểm riêng lẻ, ví dụ: một viên kim cương bên trong một hình vuông:

Answer 2

Đa giác cùng với danh sách lỗ đa giác. Chỉ cần chắc chắn rằng các đa giác khác nhau không giao nhau.

Bạn định làm gì với điều này?

Answer 3

Có vẻ như mỗi lỗ chỉ là một đa giác bên trong chính hình đa giác. Có lẽ bạn có thể lưu trữ một vector giống như bạn mô tả cho đa giác bên ngoài, sau đó là một vectơ của các vectơ đa giác hơn cho các lỗ.

Answer 4

Chính xác bạn có ý nghĩa gì dưới "biểu đồ hiển thị"?

Hai poligon "đầy đủ", hai trạng thái có thể là +1 hoặc -1.

Nếu bạn đại diện cho một lỗ, bạn đã có một lỗ với trạng thái +1 và một với trạng thái -1, biểu thị lỗ, dẫn đến trạng thái 0.
Nếu bạn có đa giác chồng chéo, bạn ' sẽ kết thúc với trạng thái kết quả> 1. Sau đó, bạn có thể tính toán đường viền của đa giác mới.
Nếu bạn có hai đa giác có lỗ giao cắt, thì trước tiên hãy tính trạng thái của đa giác mới bao gồm đường viền ngoài của hai đường cũ, sau đó xử lý các lỗ.

Dù sao thì ... Tôi nghĩ bạn sẽ có nguyên tắc chung.

Không có ý tưởng làm thế nào để làm điều đó trong MATLAB, tôi sử dụng nó chỉ nhẹ cho đến nay, và thậm chí là cho những điều rất đơn giản.

Answer 5

Bạn có thể phá vỡ một đa giác với một lỗ trong đó thành hai hình dạng không có lỗ. Khi bạn đang thực hiện tích hợp đường viền trong một mặt phẳng phức tạp, bạn có thể tạo một "vết cắt" từ một cạnh của đa giác mang đến cho bạn mép của lỗ; tích hợp xung quanh một bên của lỗ và lưng; sau đó đi ngang qua phía bên kia của đa giác thứ hai. Bạn kết thúc với hai đường tích phân dọc theo mỗi lần cắt bỏ nhau.

"biểu đồ hiển thị" - đây có phải là tính toán hệ số xem bức xạ với bóng không? Hoặc thuật toán đồ họa theo dõi tia?

Answer 6

Có lẽ bạn sẽ muốn có cấu trúc cây nếu bạn muốn nó càng chung càng tốt (nghĩa là đa giác có lỗ đa giác có đa giác bên trong chúng có lỗ bên trong, ...). Matlab không thực sự tuyệt vời khi đại diện cho cấu trúc cây một cách hiệu quả, nhưng đây là một ý tưởng ...

Có một mảng cấu trúc đa giác.

Mỗi đa giác là một cấu trúc có hai trường, 'góc' và 'trẻ em'.

Trường 'góc' chứa ma trận tọa độ (x, y) của các góc, được truy cập dưới dạng "dữ liệu {polyIdx} .corners (:, cornerIdx)".

Trường 'trẻ em' là một mảng cấu trúc của đa giác.

Dưới đây là một ví dụ về một số mã để tạo ra một tam giác với trẻ em không có thật mà là lỗ (họ không thực sự có giá trị mặc dù bởi vì họ có khả năng sẽ chồng chéo lên nhau:

polygon = struct; 
npoints = 3; 
polygon.corners = rand(2,npoints); 
polygon.children = struct; 
nchildren = 5; 
for c=1:nchildren 
    polygon.children(c).corners = rand(2,npoints); 
    polygon.children(c).children = struct; 
end 

Bạn có thể tiếp tục đệ quy định nghĩa trẻ em luân phiên giữa các lỗ hổng và điền chúng