polygon triangulation reflex vertex

Question

안녕하세요, 나는 polygon 삼각 측량을 수행하려고합니다. 간단한 다각형 (Concave or Convex)의 귀 클립핑 방법을 이해했습니다. 나는 꼭지점이 반사적인지 여부를 알아 내는데 막혔다. 내가 여러 장소에서 읽은 것은 내가 이해할 수없는 시계 방향과 반 시계 방향에 관한 것입니다. 간단히 말해서 그 방향을 참조하고 정점이 반사인지 아닌지를 확인하는 것에 대한 힌트를주세요. 여기 here is the link of an article i am following:

와 그들이 사용한 공식은 :

내가 이해할 수없는 생각 요점이 뭐죠 여기

// Input 
    VECTOR a, b, c; // the parts of our triangle. 
    // if (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0 
    // we are counter-clockwise 

.

Answer 1

대부분의 경우 입력 폴리곤은 연속적인 정점 목록이며 시계 반대 방향으로 폴리곤을 나타냅니다. 즉, 다각형의 경계를 따라 걷는 경우 (구멍이없는 경우) 내부가 가로 지르는 모든 가장자리의 왼쪽에 있어야합니다. 하나의 꼭지점이 볼록 또는 반사인지 (볼록한 의미의 내부 각이 180 °보다 작거나, 반사가 없다는 것을 알고 싶다면) 몇 가지 방법이 있습니다. 가장 보편적으로 사용되는 것은 결정적 요소를 적용하는 것입니다. 확정 값은 정점이 좌회전을 형성하면 결과가 더 큰 값을 갖습니다. 이는 세 개의 연속 된 정점 a, b 및 c가 b에서 볼록 각도를 형성 함을 의미합니다. 그렇지 않으면 0보다 작습니다. 이제 수식 : (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0 정확히 그 않습니다. 3 개의 꼭지점을 두 방향 벡터로 변환합니다 : b-a 및 c-b 그러면 이것에 대한 확정 값은 이미 주어진 수식이며 b에서 왼쪽 또는 오른쪽 회전이 발생했는지 알려줍니다. 때문에 주석의 질문에

편집 :

우리가 선택하자 = (2 1), B = (5 4), 및 C = (3 ~ 6). 따라서 오른쪽 그림과 같은 방향은 s = b-a = (3 3) 및 t = c-b = (- 2 2)로 표시됩니다. 지금 det(s t)는 우리에게 s.x*t.y - t.x*s.y = 3*2 - (-2)*3 = 12 > 0를줍니다. 그러므로 우리가 a 지점에 서서 b 지점으로 걸어 가면 c 지점으로 가려면 왼쪽으로 돌아 가야합니다.