Kiểm tra xem đa giác đơn giản có yếu kém không

Question

Tôi không thể tìm ra thuật toán để phát hiện đa giác yếu đơn giản (tức là đa giác nơi các cạnh được phép chạm nhưng không được gạch chéo). Hiện tại tôi chỉ đang kiểm tra các giao lộ giữa mọi phía - đây là hàm tôi gọi cho tất cả các bên không liền nhau. Bằng cách này, chỉ có các đa giác đơn giản được phép (không hề đụng chạm gì cả). Đa giác là vectơ của các điểm.

bool linesIntersect(const point &a1, const point &a2, const point &b1, const point &b2) { 
    // Solve intersection of parametric lines using inverse matrix 
    // The equation of the parametric lines are line1 = (a2 - a1)*s + a1 
    // and line2 = (b2 - b1)*t + b1, where a1, a2, etc. are vectors. 
    // Two equations can be produced from the two components, and these 
    // this system of two equations can be solved for s and t 
    // If the parameters s and t are between 0 and 1, it means that the lines intersect 
    float x21 = a2.x - a1.x, x43 = b2.x - b1.x, x31 = b1.x - a1.x, 
     y21 = a2.y - a1.y, y43 = b2.y - b1.y, y31 = b1.y - a1.y; 
    float determinant = x43*y21 - x21*y43; 
    if(determinant == 0.) return false; 

    float s = float(x43*y31 - x31*y43)/determinant; 
    float t = float(x21*y31 - x31*y21)/determinant; 

    if(s <= 1. && s >= 0. && t <= 1. && t >= 0.) return true; // lines intersect 
    return false; 
} 

Sử dụng s < 1. && s > 0. && t < 1. && t > 0. không hoạt động vì nó chấp nhận một số đa giác phức tạp đơn giản.

Hình đầu tiên trong this question hiển thị một vài ví dụ. Dưới đây là một đa giác đơn giản điển hình mà chương trình sẽ xử lý.

tôi muốn giả kể từ khi thuật ngữ toán học trong câu hỏi nêu trên (1) làm tôi sợ và tôi không nghĩ rằng tôi có kiến ​​thức để thực hiện bất kỳ thuật toán phức tạp. Tôi đang sử dụng Boost.Polygon cho một cái gì đó khác nếu có cái gì đó trong đó, nhưng tôi đã không tìm thấy bất cứ điều gì.

EDIT:

Đây là cách tôi sử dụng hàm. checkPts là một vector<point> với một mặt được giả định từ điểm cuối cùng đến điểm đầu tiên.

// Check for self-intersecting polygons 
for(int i = 0; i < checkPts.size() - 2; ++i) { 
    for(int j = i + 2; j < checkPts.size() - 2; ++j) { 
     if(linesIntersect(checkPts[i], checkPts[i+1], checkPts[j], checkPts[j+1])) error("self-intersecting polygon"); 
    } 
} 

Answer 1

Tôi không chắc chắn tôi nhận được nó, bởi vì bạn dường như đã có một giải pháp. Chỉ cần gọi lineIntersects trên mỗi cặp cạnh không liền kề.

Nếu hai cạnh không có điểm chung, thì lineIntersects trả về false, được mong đợi.

Nếu hai cạnh cắt nhau, lineIntersects trả về true và do đó, bạn biết rằng đa giác không đơn giản yếu.

Nếu hai cạnh chạm vào, như trong hình, thì yếu tố quyết định mà bạn tính toán trong dòngSố liệu là 0 (tức là: các đường thẳng song song). lineIntersects trả về false. Đó là những gì bạn muốn (bạn cho phép các cạnh chạm)

Tất nhiên, luôn luôn có phần khó khăn khi hoạt động trên phao dẫn đến lỗi làm tròn, nhưng đối với tôi, toán trong hàm của bạn là chính xác. (và chắc chắn nên làm việc trên ví dụ trong hình)

Chỉnh sửa: Cách tiếp cận "toán học" hơn. Hai cạnh có 0 điểm chung, 1 điểm chung hoặc một số điểm chung chung (chúng "chạm"). Là đơn giản yếu ớt chỉ có nghĩa là đối với bất kỳ hai cặp cạnh, bạn không được phép có trường hợp "1 điểm chung". Vì vậy, bạn cần một hàm tìm ra khi bạn có chính xác 1 điểm. Khiếu nại của tôi là lineIntersects đã làm điều đó

Chỉnh sửa 2: Tôi quên giải thích rằng có 1 điểm chung không phải lúc nào cũng là vấn đề. Nhưng chỉ khi điểm chung giữa hai cạnh là điểm cuối của một trong hai cạnh. Sau đó chúng ta nên "cho phép" nó (trả về false). Nhưng điều này không thay đổi câu trả lời của tôi vì trong lineIntersects, chúng tôi tính s < 1. && s > 0. && t < 1. && t > 0. và không phải s <= 1. && s >= 0. && t <= 1. && t >= 0.. Vì vậy, chúng tôi đã "cho phép" trường hợp này.