Sắp xếp các điểm của đa giác

Question

Tôi có một đa giác lồi ABCDE ... (nó có thể có bất kỳ số điểm nào). Tôi cần phải sắp xếp tất cả các đỉnh của nó sao cho không có cạnh nào cắt nhau.
dụ:

A _____ B 
    \ /
    \/
    X 
/\ 
    /___\ 
C  D 

Đó đa giác theo thứ tự ABCD đã giao nhau cạnh. tuy nhiên theo thứ tự ABDC:

A _____ B 
    | | 
    | | 
    | | 
    | | 
    |___| 
C  D 

Không có cạnh nào cắt nhau nên ABDC là đầu ra mong đợi.

Tôi làm cách nào để thực hiện việc này?

Answer 1

Giả sử điểm của bạn là tất cả trên thân tàu lồi của đa giác của bạn, bạn có thể sử dụng như sau:

1. Chọn hai điểm cực với giá trị min và max X, (gọi họ là X _phút và X _max) và vẽ đường thẳng giữa chúng. Trong trường hợp bạn có nhiều điểm với cùng một giá trị X ở mức cực đại, hãy chọn X _phút với giá trị Y tối thiểu và X _{tối đa} với giá trị Y tối đa.
2. Chia danh sách các điểm thành hai danh sách phụ nơi tất cả các điểm bên dưới đường kết nối X _phút và X _{tối đa} nằm trong một danh sách và tất cả các điểm trên nằm trong một danh sách khác. Bao gồm X _phút trong danh sách đầu tiên và X _{tối đa} trong danh sách thứ hai.
3. Sắp xếp danh sách đầu tiên theo thứ tự tăng dần của giá trị X. Nếu bạn có nhiều điểm với cùng một giá trị X, hãy sắp xếp chúng theo giá trị Y tăng dần. Điều này chỉ xảy ra cho các điểm có cùng thành phần X là X _{tối đa} vì đa giác lồi.
4. Sắp xếp danh sách thứ hai theo thứ tự giảm dần của giá trị X. Một lần nữa, sắp xếp theo giá trị Y giảm dần trong trường hợp có nhiều điểm với cùng giá trị X (chỉ xảy ra đối với các điểm có thành phần X X _phút. .)

Answer 2

chọn hai điểm trên đa giác. điểm giữa của đường thẳng sẽ được chứa trong đa giác đó. Hãy để điểm đó là M.

Sau đó, sắp xếp các điểm dựa trên góc dựa trên M (dọc theo trục X), phá vỡ sự thoái hóa dựa trên khoảng cách từ M. Iterating theo thứ tự đó đảm bảo không có hai cạnh nào cắt nhau.