[Java로 배우는 자료구조] 제2-2장: 메서드와 생성자 (3/3)

다각형과 점

• 내부/ 외부 검사

package section2;

public class OrthoLine {//수직선
    public MyPoint2 u;  //한 쪽 끝점 (항상 수직선의 경우 위쪽, 수평선의 경우 왼쪽 으로 하기로 한다)
    public MyPoint2 v;  //다른쪽 끝점

    public OrthoLine( MyPoint2 p, MyPoint2 q)
    {
        u = p;
        v = q;
        if(p.x>q.x || p.x==q.x && p.y>q.y) // 수평선일때 x좌표 v가 더 크거나, 수직선일때 y좌표 v가 더 클때
            swap();
    }

    private void swap(){
        MyPoint2 tmp = u;
        u = v;
        v = tmp;
    }

    public OrthoLine( int x1, int y1, int x2, int y2 )
    {
        u = new MyPoint2(x1, y1);
        v = new MyPoint2(x2, y2);
    }

    public boolean isVertical()  // 수직인지 검사
    {
        return u.x == v.x;
    }

    public boolean intersects( OrthoLine other )
    {
        if( isVertical() && !other.isVertical() ){
            return ( other.u.x < u.x && other.v.x  > u.x && u.y < other.u.y && v.y > other.u.y );
        }
        else if ( !isVertical() && other.isVertical() ){
            return ( other.u.y < u.y && other.v.y > u.y && u.x < other.u.x && v.x > other.u.x );
        } 
        else 
            return false;


    }
    
}

package section2;

public class OrthoPolygon { //다각형 객체 생성
    public int n;
    public MyPoint2 [] vertices;

    public OrthoPolygon( int k) { //꼭지점 갯수
        n = 0;
        vertices = new MyPoint2 [k];
    }

    public void addVertex( int x, int y )
    {
        vertices[n++] = new MyPoint2(x, y);
    }

    public int maxX()
    {
        int max = vertices[0].x;
        for(int i=0; i<n; i++){
            if(vertices[i].x > max)
               max = vertices[i].x;
        }
        return max;
    }

    public boolean contains( MyPoint2 p ){
        OrthoLine arrow = new OrthoLine(p, new MyPoint2( maxX()+1, p.y));
        int count = 0;
        for(int i=0; i<n; i++){
            OrthoLine edge = new OrthoLine(vertices[i], vertices[(i+1) % n]);
            if ( arrow.intersects(edge) )
                count++;
        }
        return (count % 2 == 1);
    }
    
}

package section2;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class Code10 {
    public static void main(String [] args){
    
        try {
            Scanner in = new Scanner(new File("data.txt"));
            int n = in.nextInt();
            OrthoPolygon thePolygon = new OrthoPolygon(n);
            for(int i=0; i<n; i++)
                thePolygon.addVertex(in.nextInt(), in.nextInt());
            MyPoint2 thePoint = new MyPoint2(in.nextInt(), in.nextInt());
            in.close();
            if(thePolygon.contains(thePoint))
                System.out.println("yes");
            else    
                System.out.println("no");
        } catch (FileNotFoundException e) {
            System.out.println("No data file.");
            System.exit(1);
          
        }
    }
    
}