굳이 만들어 보자.

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

구현할 것 목록
  • 다각형 내부/외부 판정
  • 좌표로 주어진 다각형이 올바른지 판정 : 변 두개가 꼬였다거나 하는 등의 틀린 정보를 제거
일단 cui로 만들고 gui 구현은 나중에.

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

2.
모든 다각형은 여러개의 삼각형으로 쪼개지므로, 삼각형 내부/외부 판정만 성공하면 나머지는 가능함. 대신, 주어진 다각형을 삼각형 여러개로 쪼개는 것이 필요함.
by snowall 2007. 7. 31. 00:52
  • 그네고치기 2007.07.31 07:26 ADDR EDIT/DEL REPLY

    굳이 만들어 보실만한 프로그램을 하나 추천하자면, "(x,y)의 리스트로 주어지는 두 개의 다각형의 겹치는 영역의 면적을 구하는 프로그램"을 생각해보시는 것도 재미있을겁니다. 여기서 다각형은 오목다각형도 허용한다고 가정하고... (... 네. 사실은 머리 깨집니다. OTZ)

    • snowall 2007.07.31 11:06 신고 EDIT/DEL

      아, 저 프로그램은 제가 연구하다가 굳이 만들어야 할 필요성이 느껴져서 굳이 만드는 겁니다.

  • djinni 2007.07.31 09:12 ADDR EDIT/DEL REPLY

    내/외부 판정 보다는 틀린 정보를 자동으로 제거하거나 수정하는 것이 어렵고,
    내/외부 판정에서는 1번보다 2번이 더 어려울 듯 합니다.

    • snowall 2007.07.31 11:07 신고 EDIT/DEL

      조언 감사합니다. 알고리즘은 여러가지로 연구해 보고 있습니다. ^^ 참고하도록 하겠습니다.

  • ㄹㄹㄹㄹ 2007.07.31 13:03 ADDR EDIT/DEL REPLY

    shooting laser.. 위에서 말씀하신 조르당의 원리를 그대로 사용하고 있고, 기하 알고리즘 소개한 책이면 어디에나 나와 있는 가장 기본적인 알고리즘입니다. 예외적인 상황 몇개만 고려해주면 제대로 풀립니다.

    • snowall 2007.07.31 13:07 신고 EDIT/DEL

      그렇군요. 찾아봐야겠네요. 감사합니다.^^

  • 지현준 2007.07.31 23:27 ADDR EDIT/DEL REPLY

    제일 먼저 떠오르는 건, 일단 한 점을 잡고, polar coordinate 비슷하게 내부적으로 변환시켜서 어떤 특정각의 가장 먼 점들을 연결하는 거군요.