다각형이 약한 지 테스트하기

Question

약한 간단한 다각형 (즉, 양쪽면은 교차 할 수 있지만 교차하지는 않는 다각형)을 감지하는 알고리즘을 찾을 수 없습니다. 현재 모든면 사이의 교차점을 확인 중입니다. 여기에 인접하지 않은면을 모두 호출하는 함수가 있습니다. 이 방법은 단순한 다각형 만 허용됩니다 (전혀 접촉하지 않음). 다각형은 점의 벡터입니다. 간단 일부 복잡한 다각형을 허용하기 때문에 작동하지 않습니다 s < 1. && s > 0. && t < 1. && t > 0.를 사용

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; 
} 

.

this question의 첫 번째 그림은 몇 가지 예를 보여줍니다. 아래는 프로그램이 다루는 전형적인 약한 폴리곤입니다.

나는 상기 질문 (1)에서 수학 용어부터 의사 나 무서워하고 나는 복잡한 알고리즘을 구현하는 지식을 가지고 생각하지 않습니다를 선호하는 것입니다. 나는 Boost.Polygon을 사용하고 있는데 거기에 뭔가가 있다면 뭔가를 찾지 못했습니다.

편집 :

다음은이 기능의 사용 방법입니다. checkPts는 vector<point>이며 마지막 점에서 첫 번째 점까지 가정합니다.

// 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

이미 해결책이있는 것 같아서 잘 모르겠습니다. 인접하지 않은 모서리의 모든 쌍에 lineIntersects으로 문의하십시오.

두 개의 모서리에 공통점이없는 경우 lineIntersects은 false를 반환합니다.

두 가장자리가 서로 교차하면 lineIntersects이 true를 반환하므로 다각형이 약하게 단순하지 않다는 것을 알게됩니다.

그림과 같이 두 개의 가장자리가 만나는 경우 linesIntersects에서 계산하는 행렬식은 0입니다 (즉 선이 평행합니다). lineIntersects은 false를 반환합니다. 당신이 원하는 것은 무엇입니까 (가장자리를 만질 수 있습니다)

물론 float에 대한 연산이 반올림 오류를 일으키는 까다로운 부분이 있지만, 저에게는 함수의 수학이 정확합니다. (그리고 그림의 예에서 확실히 작동해야 함)

편집 : "수학적"접근 방식. 두 개의 모서리는 공통점이 0 점, 공통점이 1 점 또는 공통점이 무한한 수입니다 ("만지십시오"). 약하게 단순하다는 것은 모든 두 쌍의 모서리에 대해 "공통점 1 점"을 가질 수 없다는 것을 의미합니다. 따라서 공통점이 정확히 1 점일 때 알아내는 함수가 필요합니다. 나의 주장은 lineIntersects가 이미 그것을한다.

편집 2 : 공통점이 1 점이 항상 문제가되는 것은 아니라는 것을 잊어 버렸다. 그러나 두 모서리 사이의 공통점이 두 모서리 중 하나의 끝점에있는 경우에만 가능합니다. 그런 다음 "허용"해야합니다 (false 반환). 그러나 이것은 lineIntersects에서 s < 1. && s > 0. && t < 1. && t > 0.이 아니라 s <= 1. && s >= 0. && t <= 1. && t >= 0.이 아니기 때문에 내 대답을 변경하지 않습니다. 그래서 우리는 이미이 사건을 허용하고 있습니다.