[알고리즘] 단순 다각형 그리기

 

단순 다각형은 연속한 두 변 이외에는 어느 두 변도 교차하지 않는 다각형이다.
여러 개의 점을 입력받은 다음 단순 다각형을 만들어서 출력하는 프로그램을 구현해보자.

 

단순 다각형

단순 다각형을 그리는 방법은 여러가지가 있겠지만 여기서는 다음 방법을 이용하여 다각형을 구성하려고 한다.

        1. 가장 낮은 Y좌표를 가지는 기준점을 잡는다 (C) Y 좌표가 동일한 경우 X좌표까지 계산한다.
        2. 기준점에서 출발하는 X축 반 직선을 그린다.
        3. 기준선과 각 점들의 각도 θ를 계산한다.
        4. 낮은 각도부터 순서대로 연결한다.

 

각도 계산

위 이미지를 기준으로 C -> G -> H -> E -> D -> B -> A -> F -> C 가 된다.

입력은 점의 총 갯수 N과 각 점의 좌표 X, Y를 파일로 받아온다.
출력은 화면에 직접 하는 것으로 구현했다.

input.txt	output
8	4 -1
2 8	7 1
3 5	10 6
4 -1	6 7
5 10	5 10
6 7	3 5
-1 2	2 8
7 1	-1 2
10 6	4 -1

 

먼저 점을 나타내기 위한 Point Class를 정의한다.
X, Y 값과 각도를 저장할 인자를 정의하고 좌표를 설정하기 위한 메소드가 필요하다.

Point class

 

Point를 ArrayList에 저장하기 위하여 메인 Class 최상단에 Point에 대한 ArrayList를 정의했다.

ArrayList 선언

 

main 함수에서는 먼저 파일 입출력을 위한 작업들을 수행한 뒤  첫번째 입력인 점의 총 갯수를 number에 받아준다. 
그 후 number의 갯수만큼 ArrayList에 담아주었다.

input 입력 받기

Y축 좌표가 가장 낮은 값, Y축의 값이 동일한 경우 X축 좌표가 가장 낮은 값을 기준점으로 하기 때문에
기준점을 찾기 위해 각 좌표들을 확인하며 최소값을 찾았다. minX, minY의 초기 값은 편의상 999로 설정했다.

기준 좌표, Index 찾기

 

기준이 되는 좌표를 찾았기 때문에 이제 기준선에 대한 각 점들의 각도를 계산해야한다.
각도를 구하는 가장 쉬운 방법은 tangent를 이용하는 것이다.

tan

하지만 여기서는 각도의 정확한 값은 알 필요가 없고 어떤 점의 크기가 더 큰지만 알면 되기 때문에
상대 각도를 이용해서 계산할 예정이다.

 

상대 각도

위 식을 코드로 구현하면 아래처럼 된다.

 

정확한 각도는 계산하지 않지만 dx , dy의 부호를 이용하여
어느 사분면에 위치해 있고 상대적으로 누가 더 큰지는 알 수 있다.
(tangent를 이용하여 각도를 계산해도 상관없음)

 

구현한 함수를 이용하여 각 점들의 각도를 계산한다.
여기서 number은 처음 입력받은 점의 갯수이다.

상대 각도를 계산한 후 각 점들을 크기에 맞게 정렬하는데 이때 구현되어 있는 sort를 사용하기 위해서는 
처음 정의했던 Point class를 조금 수정해야한다.

수정된 Point

각도를 비교하여 sorting할 수 있게 Comparable을 상속 받아서
CompareTo 메소드를 Override해서 수정해준다.

 

마지막으로 정렬된 리스트를 순서대로 출력하면 다각형이 완성된다.
다각형이기 때문에 처음 시작점을 마지막에 한번 더 출력해야한다.

 

 

전체 코드

주의 - 공부하면서 작성한 코드이기 때문에 미흡할 수 있습니다..-

import java.io.*;
import java.util.*;

class Point implements Comparable<Point>{
    int x;
    int y;
    float tangent = 0;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point p){
        if(this.tangent < p.tangent)
            return -1;
        else if(this.tangent > p.tangent)
            return 1;
        return 0;
    }
}

public class polygon {

    static ArrayList<Point> pointList;

    public static float ComputeAngle(int px1, int py1, int px2, int py2){
        float dx = px2 - px1;
        float dy = py2 - py1;

        float angle;

        if ((dx >= 0)&&(dy == 0))
            angle = 0;
        else {
            angle = Math.abs(dy)/(Math.abs(dx) + Math.abs(dy));
            if((dx < 0) && (dy >= 0)) angle = 2 - angle;
            else if((dx <= 0) && (dy < 0)) angle = 2 + angle;
            else if((dx > 0) && (dy < 0)) angle = 4 - angle;
        }
        return angle*90 ;
    }

    public static void main(String[] args) throws FileNotFoundException {

        File input = new File("input.txt");
        Scanner scan = new Scanner(input);

        int number = scan.nextInt();

        pointList = new ArrayList<Point>();

        
        int x, y;
        for(int i =0; i < number; i++)
        {
            x = scan.nextInt();
            y = scan.nextInt();

            pointList.add(new Point(x,y));
        }

        //시작 index 찾기
        int minX = 999 , minY = 999 , minIndex = 0;
        for (int i = 0; i < number; i++){
            x = pointList.get(i).x;
            y = pointList.get(i).y;
            if((minY > y)||(minY == y && minX > x)){
                minIndex = i;
                minX = x;
                minY = y;
            }
        }

        for (int i = 0; i < number; i ++){
            pointList.get(i).tangent = ComputeAngle(pointList.get(minIndex).x,pointList.get(minIndex).y,pointList.get(i).x,pointList.get(i).y);
        }

        Collections.sort(pointList);



        for (int i = 0; i < number; i ++){
            System.out.print(pointList.get(i).x+" ");
            System.out.println(pointList.get(i).y+" ");
        }
        System.out.print(pointList.get(0).x+" ");
        System.out.println(pointList.get(0).y+" ");


    }


}