다각형의 넓이

http://1nsunym.github.io/ko/online/01-09-2016/algorithm-polygon-area

다각형 넓이

볼록다각형의 경우

삼각형의 면적은 삼각형을 이루는 두 벡터의 외적의 절대값의 절반입니다. a⃗ $\overrightarrow{a}$와 b⃗ $\overrightarrow{b}$가 이루는 삼각형의 면적인 T$T$는 다음과 같습니다.

a⃗ =(x2−x1,y2−y1,0)$$\overrightarrow{a}=(x_2-x_1,y_2-y_1,0)$$

b⃗ =(x3−x1,y3−y1,0)$$\overrightarrow{b}=(x_3-x_1,y_3-y_1,0)$$

T=∣∣∣a⃗ ×b⃗ 2∣∣∣$$T=\left|\frac{\overrightarrow{a}\times \overrightarrow{b}}{2}\right|$$

T=∣∣∣(x3−x1)(y2−y1)−(x2−x1)(y3−y1)2∣∣∣$$T=\left|\frac{(x_3-x_1)(y_2-y_1)-(x_2-x_1)(y_3-y_1)}{2}\right|$$

삼각형을 전부 더하면 됩니다.

오목다각형

P1(x1,y1)$P_1(x_1,y_1)$을 오목다각형의 꼭지점 중 내각이 π$\pi$ 이상인 점으로 잡습니다.

외적 연산 시 두 벡터가 주어진 순서대로 반시계방향(CCW)을 이룰 때 외적의 결과 값은 음수를 가지고, 시계방향(CW)을 이룰 때 외적의 결과 값은 양수이다.

위 성질 때문에 위 오목다각형에서 P1P3P4$P_1{P}_3{P}_4$의 면적에서 ΔP1P2P3$\mathrm{\Delta }{P}_1{P}_2{P}_3$의 면적이 아래 수식에서 cancel out 됩니다. S$S$는 다각형의 면적입니다.

S=∣∣∣∑P1Pi→×P1Pi+1→∣∣∣$$S=|\sum \overrightarrow{P_1{P}_i}\times \overrightarrow{P_1{P}_{i+1}}|$$

S=∣∣∣∑(xi−x1)(yi−1−y1)−(xi−1−x1)(yi−y1)2∣∣∣

위와 같이 어려운 공식 말고 쉬운 방법 

otherwise

다각형 면적  = | CCW( a, b, c, d, e .... ) / 2 |

끝... 

 

CCW 공식 구하는 법... 재확인

 < CCW ( a, b, c) >

Result = (플러스)

Xa  Xb  Xc  Xa      ↘  ↘  ↘   Ya  Yb  Yc  Ya

( Xa*Yb + Xb*Yc + Xc*Ya )

- ( 마이너스 )

Xa  Xb  Xc  Xa      ↙   ↙   ↙   Ya  Yb  Yc  Ya

- ( Xb*Ya + Xc*Yb + Xa*Yc )

코드화 로 정리하면 다음과 같다.

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { // (x1,y1) 에서 -> (x2,y2)를 볼 때, (x3,y3)의 위치 int temp = x1*y2+x2*y3+x3*y1; temp = temp - y1*x2-y2*x3-y3*x1; if (temp > 0) { return 1; // CCW 방향에 존재 } else if (temp < 0) { return -1; // CW 방향에 존재 } else { return 0; // 직선상위에 존재 }  }

위 코드 외울것..!!!

[실제 Function Code]

int j =0;  long ans = 0;  for (int i = 1; i < N+1; i++) { j = i % N +1; ans += X[i]*Y[j] - X[j]*Y[i];  }  ans = Math.abs(ans);

이코드를 생각했다면, 당신은 천재..

 j = i % N +1;