[2166]다각형 면적 구하기(코드+풀이)

다각형 면적을 구하기 위해선 어떻게 해야할 까?

우선 주어진 점들을 판단하여.. 구할수 있겠다.

 

 

제가 그렸어요위의 오각형 그림을 생각해보자. 삼각형 세개로 분할 할 수 있는데 이때의 점의 집합은

1번 삼각형 = {(x0,y0),(x1,y1),(x2,y2)}, 2번삼각형 = {(x0, y0),(x2, y2),(x3, y3)}, 3번삼각형 = {(x0, y0),(x3, y3),(x4, y4)}

이다.

 

그럼 이 삼각형 세개의 넓이를 구한 후, 더해주면 끝이다.. 이걸 N각형까지 확장하면.. 우리가 원하는 N각형의 넓이를 구할 수 있을것이다.

x와 y좌표가 n개씩 주어졌을때, 각 삼각형의 표현은

A =  {(x0,y0),(x1,y1),(x2,y2)}, B = {(x0, y0),(x2, y2),(x3, y3)}, C = {(x0, y0),(x3, y3),(x4, y4)}

D = {(x0,y0),(x4,y4),(x5,y5)}, ... N = {(x0,y0),(xN, yN),(xN+1,yN+1)} 이겠다..

 

이제 우린 각 삼각형의 넓이를 구하면 끝이다.

세 점이 주어졌을 때 삼각형의 넓이는 사선공식, 신발끈 공식등 행렬식을 사용해 풀 수 있다.

하지만 여기서는 CCW개념을 이용하였다. 공식 자체는 같다.

 

CCW는 두 벡터의 방향성을 표현하는 알고리즘이다.

오른손법칙과 같은 개념인데 아래 그림을 보자

http://furthermathematicst.blogspot.com/2011/07/121-3d-vectors.html

 

벡터 a와 b의 방향성을 구하는 알고리즘이다.

Vec)a=(m1, m2, m3) Vec)b=(n1, n2, n3) 일때

a와 b벡터를 외적하면 a X  b = (m2n3−m3n2, m3n1−m1n3, m1n2−m2n1) 이다.

 

하지만 다각형은 어떠한가 이차원에 존재한다 고로 z축 좌표를 0으로 바꿔보자.

(0, 0, m1n2−m2n1) 이다.

 

D = m1n2 - m2n1 이라고하자.

이때

D>0 에서 두 벡터는 반시계방향임을 알 수 있다. 직관적으로는 오른손 법칙을 생각하자.

D<0 이면 시계방향이고

D=0 에서 두 벡터는 평행하다.

이를 알고리즘으로 표현한것은 아래의 글에 정리해놓았다.

 

https://ezerocho.tistory.com/8

CCW 알고리즘

 

우리는 삼각형의 넓이를 구하는데 CCW가 뭔상관인가? 두벡터의 방향성? 무슨 상관일까..

D = m1n2 - m2n1 을 벡터 표현이 아닌 좌표계로 변환시켜보자.

위로 돌아가 1번 삼각형을 보자 1번 삼각형 = {(x0,y0),(x1,y1),(x2,y2)} 이다.

이때 A = (x0,y0,0) B = (x1,y1,0) C = (x2,y2,0) 이라고 해보자.. 평면상이니까 z값은 당연히 0이다.

 

선분AB = {(x1-x0), (y1-y0)}

선분AC = {(x2-x0), (y2-y0)} 

 

일 것이다.

외적해보자

AB X AC = {(x1-x0)(y2-y0) - (x2-x0)(y1-y0)} 이다.

=x0y1+x1y2+x2y0−(y0x1+y1x2+y2x0)

이는 우리가 사선 공식이라고 부르는 행렬식과 유사하다.

2를 나눠주는것 말고 똑같다.

https://medium.com/@joongi1978/algorithm-3-세-점을-알-때-삼각형의-넓이를-구하는-방법-사선-신발끈-공식-232ed0dc94d8

 

자 그럼 CCW공식에 2를 나눠주면 우리가 구하고자 하는 삼각형의 넓이를 알 수 있다.

왜 이렇게 멀리 돌아왔을까? 처음부터 저 공식을 말해주면 되지 않았을까?

 

CCW를 쓰는 이유는 특수한 경우 때문이다.

 

 

 

 

위 그림을 잘 보자 CCW를

코드와 비교하면 서 설명할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Sep_24 {
    public static class Point{
        double x, y;
        Point(double x, double y){ this.x = x; this.y = y;}
    }
    public static double ccw(double x1, double x2, double x3, double y1, double y2, double y3){
        double a = x1 * y2 + x2 * y3 + x3 * y1;
        double b = y1 * x2 + y2 * x3 + y3 * x1;
        return (a-b)/2;
    }

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Point[] p = new Point[N];
        double res = 0;
        double x, y;


        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            x = Double.parseDouble(st.nextToken());
            y = Double.parseDouble(st.nextToken());
            p[i] = new Point(x, y);
        }
        for(int i=1;i<N-1;i++){
            res += ccw(p[0].x,p[i].x, p[i+1].x, p[0].y,p[i].y, p[i+1].y);
        }
        System.out.printf("%.1f", Math.abs(res));
    }
}

 

 

내일 마저쓸게요