모눈종이에 꼭짓점을 격자점으로 찍어 겹치지 않는 다각형을 그렸다고 하겠습니다. 내부 격자점 수 I와 경계 위 격자점 수 B만 세면 넓이는 A=I+B/2−1입니다. 좌표를 따라 밑변과 높이를 나누거나 신발끈 공식을 계산하지 않아도 점의 개수로 정확한 넓이를 얻습니다. 이것이 1899년 게오르크 픽이 발표한 픽의 정리입니다.
정리가 적용되는 조건
- 모든 꼭짓점의 x,y 좌표가 정수인 격자다각형이어야 합니다.
- 변은 직선 선분이고 경계가 자기 자신과 교차하지 않는 단순다각형이어야 합니다.
- 기본식은 구멍이 없는 연결 영역에 적용합니다.
- I는 내부의 격자점, B는 꼭짓점을 포함한 전체 경계 격자점 수입니다.
A = I + B/2 - 1
직사각형으로 바로 확인
가로 4, 세로 3인 축 정렬 직사각형을 보겠습니다. 내부 격자점은 (4-1)(3-1)=6개입니다. 경계점은 2×4+2×3=14개입니다. 픽의 식은 A=6+14/2-1=12를 주며 가로×세로 4×3=12와 같습니다.
경계점은 gcd로 세기
두 격자점 (x₁,y₁),(x₂,y₂)를 잇는 선분에서 시작점을 포함하고 끝점을 제외해 세는 격자 간격 수는 gcd(|Δx|,|Δy|)입니다. 다각형의 모든 변에서 이 값을 더하면 꼭짓점을 중복하지 않고 B를 구할 수 있습니다.
B = Σ gcd(|xᵢ₊₁-xᵢ|, |yᵢ₊₁-yᵢ|)
예를 들어 (0,0)에서 (6,4)까지 Δx=6,Δy=4이고 gcd는 2입니다. 선분 위 격자점은 양 끝을 포함해 3개, 즉 (0,0),(3,2),(6,4)입니다. 다각형 전체 공식에서는 각 변의 gcd만 더해 각 꼭짓점이 다음 변의 시작점으로 한 번씩 세어지게 합니다.
삼각형 예제
꼭짓점 (0,0),(4,0),(0,3)인 직각삼각형을 보겠습니다. 세 변의 gcd는 4,1,3이므로 B=8입니다. 내부 격자점은 (1,1),(2,1),(1,2) 세 개여서 I=3입니다. 픽의 식은 A=3+8/2-1=6이며 밑변×높이/2=4×3/2=6과 일치합니다.
| 변 | |Δx| | |Δy| | gcd |
|---|---|---|---|
| (0,0)→(4,0) | 4 | 0 | 4 |
| (4,0)→(0,3) | 4 | 3 | 1 |
| (0,3)→(0,0) | 0 | 3 | 3 |
| 합계 | - | - | B=8 |
기울어진 사각형을 계산하는 예제
꼭짓점을 반시계방향으로 (0,0),(5,0),(6,3),(2,5)라고 놓겠습니다. 네 변의 좌표 차는 (5,0),(1,3),(−4,2),(−2,−5)입니다. 각 변의 gcd는 5,1,2,1이므로 경계 격자점 수 B는 9입니다. 첫 변에는 중간 격자점이 많고, 좌표 차가 서로소인 둘째와 넷째 변에는 양 끝 이외의 격자점이 없습니다.
이 다각형의 내부 격자점을 세면 I=16입니다. 픽의 정리를 적용하면 A=16+9/2−1=19.5입니다. 신발끈 공식으로도 (0×0+5×3+6×5+2×0)−(0×5+0×6+3×2+5×0)=45−6=39이고 절댓값의 절반은 19.5입니다. 축에 나란하지 않은 오목하지 않은 다각형에서도 두 공식이 같은 결과를 냅니다.
| 계산 항목 | 값 |
|---|---|
| 경계점 수 B | 5+1+2+1=9 |
| 내부점 수 I | 16 |
| 픽의 정리 | 16+9/2−1=19.5 |
| 신발끈 공식 | |45−6|/2=19.5 |
왜 −1이 들어가나
픽의 식은 오일러 표수와 삼각분할로 설명할 수 있습니다. 다각형 내부와 경계의 모든 격자점을 꼭짓점으로 삼아 작은 삼각형들로 나눕니다. 기본 격자삼각형의 넓이는 1/2이고, 꼭짓점·모서리·면의 관계 V−E+F=1을 사용해 내부 모서리와 경계 모서리를 정리하면 삼각형 수/2=I+B/2−1이 나옵니다. 상수 1은 원판과 같은 단순 영역의 오일러 표수에서 옵니다.
조금 더 구체적으로 기본 격자삼각형 수를 T, 내부 모서리 수를 Eᵢ라고 하겠습니다. 각 삼각형의 세 변을 모두 세면 내부 모서리는 두 번, 경계 모서리는 한 번 세므로 3T=2Eᵢ+B입니다. 꼭짓점 수는 I+B이고 전체 모서리는 Eᵢ+B입니다. 영역 바깥 면을 제외한 형태의 오일러 관계 (I+B)−(Eᵢ+B)+T=1에 앞의 식을 대입하면 T=2I+B−2가 나옵니다.
기본 격자삼각형은 내부와 경계에 다른 격자점이 없는 삼각형이며 넓이가 1/2입니다. 따라서 전체 넓이는 T/2=I+B/2−1입니다. 일반 격자다각형을 이런 기본 삼각형으로 나눌 수 있다는 사실이 증명의 또 다른 부분입니다. 이 설명은 공식의 −1이 임의로 보정한 숫자가 아니라 영역의 연결 구조를 나타내는 오일러 관계에서 나온다는 점을 보여 줍니다.
도형을 붙여도 식이 더해집니다
두 격자다각형을 공통 경계선으로 붙이면 실제 넓이는 더해집니다. 픽 식에서도 공통 경계의 내부 격자점들이 새 도형에서는 내부점으로 바뀌고, 양 끝 처리와 −1 항이 정확히 상쇄되어 값이 더해집니다. 그래서 기본 삼각형에서 성립하는 식을 삼각분할된 일반 다각형으로 확장할 수 있습니다.
구멍이 있으면 공식이 달라집니다
다각형 영역에 h개의 구멍이 있으면 오일러 표수가 달라져 A=I+B/2−1+h가 됩니다. 여기서 B에는 바깥 경계와 모든 구멍 경계의 격자점이 포함됩니다. 기본식의 −1을 그대로 쓰면 구멍 하나마다 넓이를 1만큼 작게 계산합니다.
구멍 h개인 격자 영역: A=I+B/2−1+h
신발끈 공식과 교차 검산
꼭짓점 좌표를 순서대로 알면 신발끈 공식 A=|Σ(xᵢyᵢ₊₁−yᵢxᵢ₊₁)|/2로 넓이를 구할 수 있습니다. 픽의 정리와 신발끈 공식은 입력 정보가 다릅니다. 픽은 내부점까지 세고, 신발끈은 꼭짓점만 사용합니다. 둘을 함께 계산하면 격자점 수나 꼭짓점 순서의 실수를 찾는 검산이 됩니다.
좌표만 있을 때 내부점 수를 역산하기
꼭짓점 좌표만 주어졌다면 먼저 신발끈 공식으로 A를 구하고, 각 변의 gcd 합으로 B를 구한 다음 I=A−B/2+1로 내부점 수를 역산할 수 있습니다. 내부점을 하나씩 화면에서 세지 않아도 되므로 좌표 범위가 큰 문제에 유용합니다. 결과 I는 0 이상의 정수여야 합니다. 음수나 소수가 나오면 꼭짓점 순서, 자기 교차 여부, gcd 합 또는 넓이 계산을 다시 확인해야 합니다.
- 꼭짓점을 경계를 따라 시계 또는 반시계 방향으로 정렬합니다.
- 신발끈 공식으로 부호 있는 넓이 합을 구한 뒤 절댓값을 2로 나눕니다.
- 마지막 꼭짓점에서 첫 꼭짓점으로 돌아가는 변까지 포함해 gcd 합 B를 구합니다.
- I=A−B/2+1을 계산하고 0 이상의 정수인지 확인합니다.
정수 좌표에서는 신발끈 합이 정수이므로 2A는 정수입니다. 픽의 식을 두 배 하면 2A=2I+B−2이므로 2A와 B의 홀짝은 같습니다. 예를 들어 B가 홀수면 넓이는 정수+1/2이고, B가 짝수면 넓이는 정수입니다. 이 짝홀 관계도 빠른 오류 점검에 쓸 수 있습니다.
넓이는 항상 반정수입니다
I와 B는 정수이므로 A=I+B/2−1은 정수 또는 정수+1/2입니다. 따라서 격자다각형의 넓이는 항상 1/2의 정수배입니다. 좌표가 정수인 단순다각형을 계산했는데 넓이가 2.3처럼 나오면 좌표나 계산을 다시 확인해야 합니다.
공식이 적용되지 않는 경우
- 원이거나 곡선 경계를 가진 영역에는 직접 적용하지 않습니다.
- 꼭짓점이 정수 격자점이 아니면 표준식이 성립하지 않습니다.
- 자기 교차 다각형은 내부의 정의와 감김수가 필요해 기본식을 그대로 쓸 수 없습니다.
- 3차원 격자 다면체의 부피는 I와 B만으로 같은 형태로 정해지지 않습니다.
- 경계점 B를 꼭짓점 수로만 세면 변 중간의 격자점을 빠뜨립니다.
픽의 정리 핵심 정리
꼭짓점이 정수 좌표에 놓인 구멍 없는 단순 격자다각형의 넓이는 A=I+B/2−1입니다. 경계점은 각 변의 좌표 차 최대공약수를 더해 효율적으로 구합니다. 내부점과 경계점을 정확히 구분하면 오목다각형에도 적용됩니다.
구멍이 h개면 A=I+B/2−1+h로 오일러 표수 항이 바뀝니다. 픽의 정리는 곡선이나 일반 좌표 다각형의 만능 넓이 공식이 아니며, 조건을 벗어나면 좌표 기반 신발끈 공식이나 적분을 사용해야 합니다.