굳이 만들어 보자.
목표 : (x, y)의 리스트로 주어진 점 들 중에서, 임의의 다각형 영역의 내부에 있는 점의 좌표를 골라내는 프로그램.
구현할 것 목록
- 다각형 내부/외부 판정
- 좌표로 주어진 다각형이 올바른지 판정 : 변 두개가 꼬였다거나 하는 등의 틀린 정보를 제거
일단 cui로 만들고 gui 구현은 나중에.
1.
다각형 내부/외부 판정에는 조르당의 곡선정리를 사용할 수 있을 것 같은데, 문제는 선분 두개가 몇번 만나는지 세어야 한다는 것. 따라서 다각형의 모든 변을 특정하는 것이 필요함.
2.
모든 다각형은 여러개의 삼각형으로 쪼개지므로, 삼각형 내부/외부 판정만 성공하면 나머지는 가능함. 대신, 주어진 다각형을 삼각형 여러개로 쪼개는 것이 필요함.
잘 이해가 안된다.
제일 먼저 떠오르는 건, 일단 한 점을 잡고, polar coordinate 비슷하게 내부적으로 변환시켜서 어떤 특정각의 가장 먼 점들을 연결하는 거군요.
그렇군요. 찾아봐야겠네요. 감사합니다.^^
shooting laser.. 위에서 말씀하신 조르당의 원리를 그대로 사용하고 있고, 기하 알고리즘 소개한 책이면 어디에나 나와 있는 가장 기본적인 알고리즘입니다. 예외적인 상황 몇개만 고려해주면 제대로 풀립니다.
조언 감사합니다. 알고리즘은 여러가지로 연구해 보고 있습니다. ^^ 참고하도록 하겠습니다.
아, 저 프로그램은 제가 연구하다가 굳이 만들어야 할 필요성이 느껴져서 굳이 만드는 겁니다.
내/외부 판정 보다는 틀린 정보를 자동으로 제거하거나 수정하는 것이 어렵고,
내/외부 판정에서는 1번보다 2번이 더 어려울 듯 합니다.
굳이 만들어 보실만한 프로그램을 하나 추천하자면, “(x,y)의 리스트로 주어지는 두 개의 다각형의 겹치는 영역의 면적을 구하는 프로그램”을 생각해보시는 것도 재미있을겁니다. 여기서 다각형은 오목다각형도 허용한다고 가정하고… (… 네. 사실은 머리 깨집니다. OTZ)