Tôi đang cố gắng triển khai thuật toán tìm diện tích tương ứng cho từng cạnh riêng lẻ của đa giác bên ngoài được cho bởi hình dạng sau. Tức là diện tích tương ứng của các cạnh 1,2 là [1,6,7,8,2], diện tích các cạnh 2,3 là [2,8,3], v.v. CCW hay CW không phải là vấn đề ở đây . Để chi tiết hơn một chút ở đây, đường đậm màu đen là đa giác bên ngoài và đường đứt nét màu xanh bên trong là khung thẳng cho đa giác bên ngoài, tôi không kiểm soát được sơ đồ đánh số nút bên trong ở đây có nghĩa là các nút từ trái sang phải có thể là 8, 7,6 hoặc 6,8,7 hoặc 7,6,8, v.v...

Sau vài ngày tìm kiếm trên Google, tôi phát hiện ra rằng sự kết hợp giữa cơ sở chu trình tối thiểu với thuật toán của Floyd Warshall được đặt tên là kỹ thuật này và có thể được sử dụng để trích xuất biểu đồ chu trình tối thiểu cần thiết, tôi nghĩ ít nhất tôi đang đi đúng hướng, vui lòng xác nhận ?

Tôi đã làm theo hướng dẫn được đưa ra trong danh pháp được đưa ra trong "Phát hiện đa giác của một tập hợp các đường Alfredo của Ferreira Manuel J. Fonseca Joaquim A. Jorge".

Mã giả để trích xuất đường chu trình tối thiểu được đưa ra dưới đây,

***CƠ SỞ CHU KỲ TỐI THIỂU(G)***
1 Γ ← tập trống
2 Π ← TẤT CẢ CÁC CẶP-ĐƯỜNG NGẮN NHẤT(G)
3 cho mỗi v trong VERTICES(G)
4 cách làm cho mỗi (x, y) trong EDGES(G)
5 làm nếu Π x,v ∩ Π v,y = {v}
6 thì C ← Π x,v ∪ Π v,y ∪ (x, y)
7 thêm C vào Γ
8 ĐẶT HÀNG THEO ĐỘ DÀI(Γ)
9 trả về SELECT-CYCLES(Γ)

• Ở dòng 2 **Π ← ALL-PAIRS-SHORTEST-PATHS(G)** là thuật toán của Floyd Warshall, thuật toán này sẽ diễn giải Π với tất cả các đường đi ngắn nhất. Nhưng một số đường dẫn không cần phải tính toán, ví dụ như tôi thì không và có mối quan hệ trực tiếp nào giữa các đỉnh như 2,4-7,5-1,7, v.v. không?
• Kiểm tra có điều kiện của người khởi tạo ở dòng 5 và 6 có nghĩa là gì? AFAIU từ đoạn mã giả đã cho, cấu trúc nội dung của Π phải là mảng 2D giữ khoảng cách ngắn nhất cho một khoảng cách nhất định, ví dụ: Π [2,7] = length_of_vertices( 2,7). Vậy việc có hoành độ và đỉnh trong Π_x,v có nghĩa là gì?

Cảm ơn

câu trả lời hay nhất

Tôi đề nghị một cách tiếp cận đơn giản hơn. Bắt đầu từ bất kỳ cạnh ngoài nào, ví dụ P1->P2. Sau đó kiểm tra từng nút PX được kết nối với P2 và chọn nút có giá trị dương nhỏ nhất cho góc (P1,P2,PX). Nút PX là nút tiếp theo trong đa giác. Sau đó tiếp tục tìm nút PY nối với PX, trong đó góc (P2, PX, PY) có giá trị dương nhỏ nhất.
Có một số cách có thể để tính góc. Một là:

c = tích trong( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # cosin của góc
s = cross_product( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # sin của góc
góc = atan2( s, c ) # cung tiếp tuyến đúng dấu

与:

def cross_product( a, b ):
    trả về ax*by - ay * bx

def bên trong_product( a, b ):
    trả về ax*bx + ay*bởi

Lưu ý dấu hiệu, nó phụ thuộc vào CW so với CCW. Tất nhiên, bạn có thể bỏ qua thuật ngữ chuẩn hóa (cơ bụng...) vì chúng triệt tiêu lẫn nhau.
Nếu cho phép đa giác lõm, kết quả của arctang phải được chuẩn hóa lại để đảm bảo góc luôn dương:

def atan2_normalized( y, x ):
    góc = atan2( y, x )
    nếu góc < 0:
        góc quay lại + 2 * Pi
    khác:
        góc quay lại

Về thuật toán - Cơ sở hình trụ tối thiểu được trích xuất từ ​​khung thẳng, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/21363323/