주어진 영역 내부의 점 골라내는 프로그램 만들기

굳이 만들어 보자.

목표 : (x, y)의 리스트로 주어진 점 들 중에서, 임의의 다각형 영역의 내부에 있는 점의 좌표를 골라내는 프로그램.

구현할 것 목록

• 다각형 내부/외부 판정
• 좌표로 주어진 다각형이 올바른지 판정 : 변 두개가 꼬였다거나 하는 등의 틀린 정보를 제거

일단 cui로 만들고 gui 구현은 나중에.

1.
다각형 내부/외부 판정에는 조르당의 곡선정리를 사용할 수 있을 것 같은데, 문제는 선분 두개가 몇번 만나는지 세어야 한다는 것. 따라서 다각형의 모든 변을 특정하는 것이 필요함.

2.
모든 다각형은 여러개의 삼각형으로 쪼개지므로, 삼각형 내부/외부 판정만 성공하면 나머지는 가능함. 대신, 주어진 다각형을 삼각형 여러개로 쪼개는 것이 필요함.