한 꼭짓점에서 나누기
볼록 다각형의 기준 꼭짓점 p₀에서 나머지 꼭짓점으로 선분을 그으면 내부를 삼각형들로 나눌 수 있다. 반시계 경계 순서에서는 이 선분 방향들도 순서대로 놓인다. 질의점이 들어갈 가능성이 있는 삼각형 구간을 방향 판정으로 찾는 것이 기본 아이디어다.
먼저 확인할 범위
기준점에 맞닿는 두 경계 변이 만드는 각도 범위를 벗어난 점은 내부일 수 없다. 같은 직선 위에 있다고 해도 선분의 연장선 위일 수 있으므로 경계의 좌표 범위를 확인해야 한다. 기준점 자체와 경계 위의 점을 어떻게 분류할지도 정해 둔다.
이진 탐색 이후
정렬된 방향들 사이에서 질의점이 놓이는 구간을 이진 탐색한 뒤 해당 삼각형 안에 있는지 다시 검사한다. 방향 구간에 들어온다는 사실만으로 다각형 안에 있는 것은 아니다. 기준점에서 너무 멀리 떨어진 점도 같은 방향을 가질 수 있기 때문이다.
전처리와 적용 조건
경계 순서가 주어진 n개 꼭짓점을 준비하는 비용과 한 점을 검사하는 비용을 구분해야 한다. 볼록하지 않은 다각형에서는 같은 부채꼴의 방향 순서와 내부 분할을 그대로 가정할 수 없다. 중복점이나 불필요한 공선 꼭짓점의 처리, 정수 곱의 범위와 부동소수점 오차도 구현 조건에 맞게 살펴야 한다.