segmentIntersect 코드 참고(선분 교차 여부 판별)
// edges의 점들로 이루어진 다각형에 점 p가 포함되어있는가?
// p가 꼭짓점들이 이루는 변에 포함되는 경우는 고려하지 않음
// 외부거나 내부인 경우만 고려함, 변 위에있는 경우는 undefined
bool isInside(const vector<Vector2>& edges, Vector2 p)
{
int cnt = 0;
// p와 x축으로 무한히 오른쪽에있는 q를 연결한 선분과 교점 확인
// i ~i+1번 꼭짓점이 이루는 변과 교차하는가?
for (int i = 0; i < edges.size(); ++i) {
int j = (i + 1) % (int)edges.size();
// 2번 케이스(선분이 아에 겹치는 경우) -> 처리됨
// 1번 케이스
if ((edges[i].y > p.y) == (edges[j].y > p.y))
continue;
// 선분의 일부가 겹치거나, 끝점에서 교차하는 경우 전부 배제했다.
// 문제에 조건에 맞추어, 충분히 오른쪽에 있는 점을 잡자.
// 문제의 특성에 따라, 특정 값을 명시하기 어렵다면
// segmentIntersect를 사용하기 보단, 직접 교점을 찾아서 판단해야 한다.
Vector2 q(1000000001LL, p.y);
if (segmentIntersects(edges[i], edges[j], p, q))
cnt++;
}
return cnt % 2;
}기본 아이디어는, 외부의 한점 q와 p를 이은 선분이 다각형의 변과 교차하는 횟수가 홀수인지 짝수인지에 따라 내부 외부가 결정된다는 것이다. 외부의 점은 잡기 나름이다. 문제의 조건에 따라 다양하게 결정할 수 있지만, 보편적인 케이스를 설명하기 위해 p에서 x축과 수평하게 오른쪽으로 무한히 떨어져있는 점을 q라고 하고 q와 p를 연결하자. 하지만 신경써야할 부분이 몇가지 있다.
외부의 점 q와 p를 연결한 선분을 a라고 해보자. a는 x축과 수평한 선분이다.
1. a가 변 '끝점'(꼭짓점)과 교차하는 경우
우선, 꼭짓점과 교차한다는 것은 총 두번 카운팅 된다는 것을 의미한다. 한 꼭짓점은 두 변이 공유하기 때문이다. 그럼 두번 카운팅 (혹은 0번)할까 아니면 한번 카운팅할까?
- 카운팅 하면 안되는 경우(두번카운팅 해야하는 경우) : 그 점을 통과해도 여전히 다각형의 내부, 혹은 외부. 즉 상태가 변하지 않는 경우다.
- 카운팅 해야하는 경우(한번 카운팅 해야하는 경우) : 그 점을 통과하면 다각형의 내부 외부가 변화하는, 즉 의미있는 꼭짓점을 의미한다.
위 두 케이스에 해당하는 경우를 각각 그림으로 한번씩만 그려보기를 권한다. 그럼 쉽게 이해할 수 있다.
우리는 편의상 외부의 한점과 p를 연결하는 선분을 x축에 평행하고 오른쪽으로 뻗어나가는 반직선으로 정의했었다. 카운팅 해야하는 경우는, 교차하는 꼭짓점을 공유하는 두변이 위 아래에 있다. 반면, 카운팅을 하면 안되는 경우는 꼭짓점을 공유하는 두 변이 둘다 위에있거나, 아래에 있다.
그러면, 우리는
if (edges[i].y > p.y == edges[i+1].y > p.y)
continue;카운팅 전에 위 조건을 추가해주면 된다.
꼭짓점을 기준으로 위에 있는 변만 교차한걸로 처리하게 되는데, 둘다 위에있으면 두번 처리돼고, 둘다 아래있으면 0번 처리되므로 카운팅하지 않은 것과 같다. 그리고 위 아래에 나뉘어 있으면 1번처리된다.
2. a가 변과 겹치는 경우
쉽게 생각해보면, 교차횟수에 포함시키면 안된다는 것을 알 수 있다. 다행히 처리가 어렵지 않다. x축과 평행한 선분과 교차여부를 판별하므로, 두 꼭짓점의 y좌표가 p의 y좌표와 같다면 카운팅하지 않으면 된다.
if (edges[i].y == p.y && edges[i+1].y == p.y) coninue;참고로 이조건은 1번 케이스를 위한 조건에 포함되므로, 따로 추가하지 않아도 된다.
