메서드와 생성자 3

다각형과 점

 

입력으로 하나의 직교 다각형(모든 변이 x축 혹은 y축과 평행한 다각형)의 또 하나의 점 p가 주어질 때 그 점이 다각형의 내부에 있는지

외부에 있는지 판단하는 프로그램을 작성하라

 

입력 형식의 예 시계방향으로 꼭지점의 좌표가 주어짐

8 // 꼭지점의 개수

0 0 //첫번째 꼭지점 x,y 좌표

16 0

16 18

10 18

10 6

6 6

6  12

0 12 //마지막 꼭지점의 x,y 좌표

7 7 //테스트할 점 p의 좌표

---

내부 / 외부 검사

 

점에서 시작하여 한 방향으로 무한히 뻗어가는 아무 직선이나 하나 그어서

그것이 다각형의 변과 짝수 번 교차하면 외부, 홀수번 교차하면 내부에 있다.

 

문제는 그은 직선이 겹치게된다면 ???

꼭지점의 좌표값은 모두 짝수, 검사할 점 좌표값은 홀수로 가정한다.

 

package section2;

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

public class code10 {

	public static void main(String[] args) {
		
		try {
			Scanner in = new Scanner(new File("data.txt"));
			int n = in.nextInt();
			OrthPolygon thePolygon = new OrthPolygon(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 exists");
			System.exit(1);
		}

	}

}

 

메인 함수 클래스!

 

package section2;

public class OrthLine {
	public Mypoint2 u;
	public Mypoint2 v;
	
	public OrthLine(Mypoint2 p, Mypoint2 q){
		u =p;
		v= q;
		if(p.x>q.x || p.x==q.x && p.y>q.y)
			swap();
	}
	
	private void swap() {
		Mypoint2 tmp = u;
		u =v;
		v=tmp;
	}
	
	public OrthLine(int x, int y, int x1, int y1){
		u =new Mypoint2(x,y);
		v = new Mypoint2(x1,y1);
	}
	
	public boolean isVertical() {
		return (u.x == v.x);
	}
	
	public boolean intersects(OrthLine 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 OrthPolygon {
	public int n;
	public Mypoint2 [] vertices;
	
	public OrthPolygon(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) {
		OrthLine arrow = new OrthLine(p, new Mypoint2(maxX()+1,p.y));
		int count =0;
		for(int i =0;i<n;i++) {
			OrthLine edge = new OrthLine(vertices[i], vertices[(i+1)%n]);
			if(arrow.intersects(edge))
				count++;
		}
		return (count % 2 == 1);
	}
}

직교 다각형 클래스 

 

기하학 적인 프로젝트를 할때마다 뭔가 어렵지만 종이에 그려가며

하니 조금 수월 하였다 이부분에대해서는 아직 이해가 덜되어 

계속 읽어보며 이해를 더 해야할 것같다!!