Nhận đa giác đơn giản

Question

Tôi có một đa giác C như sau:

C = 10  0 
    2  0 
    2  2 
    0  2 
    2  0 
    0  0 
    0 10 
    10 10 

nơi cột đầu tiên đại diện cho x của phối hợp và cột thứ hai tương ứng với y của phối hợp của đa giác C. Như bạn có thể thấy trong hình trên, đây không phải là đa giác đơn giản (đa giác này chứa một lỗ được chỉ định bởi màu trắng), vì vậy tôi muốn lấy tất cả các đa giác con đơn giản từ C không chứa một lỗ. Trong trường hợp sản lượng này sẽ như sau:

C1 = 0  2 
      2  0 
      0  0 

    C2 = 2  0 
      2  2 
      0  2 
      0 10 
     10 10 
     10  0 

đâu C1 và C2 được tương ứng với tam giác nhỏ màu đỏ và đa giác lớn màu đỏ tương ứng.

Sự cố là cách tôi có thể tạo các đa giác phụ này?

Bất kỳ ý tưởng nào cũng sẽ được đánh giá cao.

Answer 1

Đầu tiên chúng ta có thể giả định rằng tất cả các điểm giao nhau đều có mặt? Nó rất dễ dàng để đến với đa giác giao nhau trong những cách thú vị. Tuy nhiên, sử dụng một cái gì đó như http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm bạn sẽ có thể tìm và thêm vào tất cả các giao lộ.

Tiếp theo, tôi sẽ làm cho giả định đơn giản hóa rằng chúng tôi không bao giờ xem xét lại một đoạn đường. (Bạn có thể đối phó với trường hợp bệnh lý đó theo nhiều cách khác nhau.)

Với chi tiết đó, chúng ta cần xác định tất cả các đa giác tối thiểu có thể được xác định bởi các điểm đó, cho dù chúng có được tính là bên trong hoặc bên ngoài. (Để thuận tiện, chúng ta sẽ thêm một "điểm" ở vô cực và đếm bên ngoài như một đa giác.) Để làm điều đó chúng ta đầu tiên lấy từng điểm, và liệt kê các điểm nó kết nối trực tiếp theo thứ tự ngược chiều kim đồng hồ. (Đi song song với trục x là 0 độ, với trục y là 90 độ, trục x âm là 180 độ, và sau đó chúng ta quấn quanh khi bạn đi xa hơn.) Vì vậy, ví dụ của bạn, chúng tôi sẽ có được một cái gì đó như thế này:

(0, 0): (2, 0), (0, 2) 
(2, 0): (10, 0), (2, 2), (0, 2), (0, 0) 
(10, 0): (10,10), (2, 0) 
(0, 2): (0, 0), (2, 0), (2, 2), (0,10) 
(2, 2): (2, 0), (0, 2) 
(0, 10): (0, 2), (10,10) 
(10, 10): (10, 0), (0,10) 

Bây giờ mỗi đa giác đơn giản sẽ đánh mỗi điểm giữa hai trong số những điểm, và ngược lại chúng ta có thể lấy một trong những lỗ hổng (bao gồm bọc xung quanh) và dễ dàng tạo ra các đa giác có liên quan, tại mỗi góc làm cho vòng quay ngược chiều kim đồng hồ nhỏ nhất có thể (nghĩa là từ điểm chúng ta đã đi đến cái sau, có thể là gói). Đối với mỗi đoạn đường, đa giác sẽ nằm ở phía bên tay phải. Chúng ta biết chúng ta có tất cả chúng khi chúng ta có mọi điểm và khoảng trống. Vì vậy, trong trường hợp trên, chúng tôi muốn bắt đầu với một điểm như (0, 0) và sau điểm (2, 0), sau đó chúng ta nhìn vào (2, 0) và thấy rằng (0, 0) Tiếp theo là (10, 0), đi đến (10, 0) và thấy rằng (2, 0) Tiếp theo là (10,10) và tiến hành theo cách này để theo dõi ra:

(0, 0), (2, 0), (10, 0), (10,10), (0,10), (0, 2), (0, 0) 

(. Lưu ý, vì khuynh hướng này bắt nguồn từ khu vực bên ngoài )

Bây giờ chúng ta bắt đầu với (0, 0) và điểm khởi đầu thay thế (0, 2) và thực hiện thao tác tương tự để nhận được:

(0, 0), (0, 2), (2, 0), (0, 0) 

(Đây là hình tam giác nhỏ bên trong.)

Đối với (2, 0) chúng tôi chưa chuyển đến (2, 2). Vì vậy, hãy làm điều đó.

(2, 0), (2, 2), (0, 2), (0,10), (10,10), (10,0), (2, 0) 

(Đây là đa giác bất thường lớn.)

Đối (2, 0) chúng ta chưa đi đến (0, 2) vì vậy hãy làm điều đó: (. Đây là hình tam giác nhỏ màu trắng)

(2, 0), (0, 2), (2, 2), (2, 0) 

Và sau đó liệt kê tất cả các đoạn đường có thể được hướng dẫn mà chúng tôi có thể muốn đi du lịch sẽ thấy rằng chúng tôi đã đề cập đến tất cả. Đây là những đa giác của chúng ta. Bây giờ chúng ta còn lại để tìm ra những gì bên trong và bên ngoài là gì. Có một mẹo đơn giản cho điều đó. Tìm một điểm có giá trị thấp nhất có thể của y (nếu có một tie, bất kỳ sẽ làm). Ví dụ giả sử chúng tôi chọn (2, 0). Các điểm kết nối, được sắp xếp ngược chiều kim đồng hồ, là (10, 0), (2, 2), (0, 2), (0, 0). Chúng tương ứng bên ngoài, bên trong, bên ngoài, bên trong ... và hơn nữa một khi một cạnh của một đa giác nhất định được đánh dấu là ở bên ngoài hoặc bên trong, tất cả các cạnh của nó đều giống nhau. Do đó chúng tôi dễ dàng nhận được:

outside: 
    - (10, 0), (2, 2), (0, 2), (0, 0) 
    - (2, 0), (0, 2), (2, 2), (2, 0) 

inside: 
    - (2, 0), (2, 2), (0, 2), (0,10), (10,10), (10, 0), (2, 0) 
    - (0, 0), (0, 2), (2, 0), (0, 0) 

Và câu trả lời của bạn sẽ chỉ là các đa giác bên trong.

(Tối ưu hóa nhỏ, chúng ta không cần vẽ các đa giác bên ngoài. Chúng ta có thể lấy đoạn đầu tiên có định hướng mà chúng ta khám phá, theo dõi một bên, sau đó đi đến một trong các góc của nó, xác định hướng các đoạn thẳng chạm vào góc đó và bắt đầu vẽ các đa giác bên trong khác. Nếu chúng ta theo dõi đúng cách, cuối cùng chúng ta sẽ có được tất cả chúng.)