#227-1. Tail 2004/02/28 (Sat) 처음으로 이 곳에 글을 쓰는데... 프로그래밍은 잘은 모르지만... 수학적으로 판별하는 방법은 대충 이렇지 않을까 싶은데요... 일단 삼각형에 대한 판별의 경우는 간단하지요... 삼각형에서 임의의 두 점을 잇는 직선을 평면에 그리고 남은 한점이 직선에 대해 평면 어느 위치에 있는지 알아내면 임의의 점이 직선에 대해 어느 위치에 있어야 삼각형의 내부에 있는지 판별할 수 있게 됩니다. 이런 방법을 다른 직선에 대해서 2번 더 반복해서 그 값이 전부 True가 나오는지 여부를 통해 삼각형의 내부에 있는지 알아낼 수 있지요. 조금 더 가다듬으면 간단한 알고리즘이 나올 법도 합니다만, 기본적인 원리는 저럴 듯 합니다. 다각형의 경우도 이런 방법을 응용하면 될 듯 싶은데... 다각형의 경우도 결국은 삼각형들의 조합이니까 개개의 삼각형으로 쪼개 어느 한 삼각형에 속해있다면... 이라는 방법으로 처리할 수도 있겠고, 위와 마찬가지로 분할된 평면에 대해 어떤 값을 가지는지를 n번 판별해서 알아낼 수도 있겠네요. 삼차원까지 가면 약간 난감하기는 하군요 -ㅅ-;; 삼차원에서 나올 수 있는 다면체가 워낙에 많아서 단순히 일반화시키기가 애매하지요. 결국은 공간을 평면으로 분할시켜 위치 관계를 알아내는게 주가 되겠지만요. 다만 저는 프로그래밍을 전혀 모르기 때문에 저게 통할지 모르겠습니다. 도움이 되었기를... ;;

#227-2. nvu 2004/02/28 (Sat) 저도 처음으로 적습니다만 -_-; 윈도 게임 코드를 작성하고 계시다면... 알고리즘 같은거는... 필요 없고; 그냥... 윈도API에 딸려있는 Region 관련 함수로 다각형 영역 잡으시고.. 그걸 이용하셔서 안인지 밖인지 체크하면 됩니다. 수학숙제하고 계시던 중이었다면 제 글은 못본걸로 해주세요 ;;;

#227-3. 안영기 2004/02/28 (Sat) 이런 내용은.... 이 게시판에 쓰시면 됩니다. 학술적인 또는 기술적인 이야기는 모두 거기에서 하는 편이 다른 사람이 참고하기가 더 좋습니다. >> 하아. 역시, DirectX 하나도 몰라도 되는... >> 우리나라 교육부의 프로그래머 육성 정책은... >> 대단합니다. 프로그램 중에서 DirectX를 알아야 하는 프로그래머는 굉장히 소수입니다. 그러므로 당연합니다. 그리고 DirectX는 MS에서 만든 MS의 OS전용 라이브러리입니다. 그리고 언제 손바닥 뒤집듯 노선을 바꾸어 버릴 수도 있는 것입니다. 라이브러리에 종속적인 프로그래머라도 밥은 먹고 살 수 있습니다만 기본에 충실한 프로그래머가 더 좋은 밥을 먹습니다. 그리고 위의 질문에 대한 해결책입니다. 그런 알고리즘도 이름이 있는지는 모르겠지만 polygon filling의 winding rule을 적용하면 간단합니다. 그 점을 (xx, yy)라고 할 때, 1. 다각형의 각 선분과 y = yy의 교점을 구합니다. (방정식이 아닌 '비율'로 고속 계산, 교점이 없을 수도 있음) 2. 교점에서의 진행 방향이 위인지 아래인지 구분하여 기입합니다. 3. 모든 교점들을 x축 기준으로 sort 합니다. (보통은 교점을 구하면서 list로 삽입합니다.) 4. xx보다 작은 x 좌표를 가지는 교점들중에서 위방향으로 향하는 것은 1, 아랫방향은 -1을 더합니다. (시작은 0) 5. 그 값이 0이면 다각형 바깥입니다. 그렇지 않으면 안쪽입니다. 이 방식은 어떻게 폴리곤이 얽히더라도 밖과 안을 구분해 냅니다. 말이 어려울 뿐이지 속도도 굉장히 빠릅니다. 숙제 (그림으로 그려보면 쉽게 풀립니다.) 1. 선분 중에 y = yy 인 것이 있다면 어떻게 처리할 것인가? 2. 두 선분의 교점이 공교롭게도 y = yy인 곳에서 1번 이상 교차한다면 어떻게 처리할 것인가?

#227-4. 그네고치기 2004/02/28 (Sat) 음...; Direct X 얘기로 잘못 꺼냈군요;;; 위 교육부 어쩌구... =ㅅ= 내용을... MFC나 다이얼로그 하나도 몰라도 되고 오직 콘솔 어플리케이션 작성에 있어서, 유저 인터페이스따위 다 무시하고 그냥 알고리즘만 코딩으로 구현하면 장땡인 것을 프로그래밍으로 인식시키게 하는 교육부와 정보통신부의 학생 프로그래머 육성 정책 (?) 이 참으로 걱정됩니다... 뭐 하기사... 프로그램 잘 만든다고 학생들 고등학교 대학교 입학시키면 좀 뭐하니까 -ㅅ- 궂이 알고리즘이라는 묘책을 내놓은 것일수도 있겠지만서도... 좀 기분이 그렇군요. =ㅅ= 새로 옮긴 학원에서 즐겨 듣는 소리... 폼따위 생각할 시간에 알고리즘 하나를 더 외워라. ... ... -ㅅ-; MFC 배워봐야 도움 안된다. -ㅅ-;;; PHP같은거 배우지 마라 시간낭비다. -ㅅ-;;;;; 흘...

#227-5. Tail 2004/02/29 (Sun) 저렇게도 되는군요... 안영기님께서 적으신 방법대로 하면 아주 빠르게 구해지는군요. ; 이거 가지고 열심히 생각해보니 왜 그렇게 되는 줄 알긴 하겠지만, 저런 방법을 생각해내지 못한다는 것에 약간 한숨이... ; 한번 저 방법을 삼차원 공간에서도 적용해볼 수 있도록 열심히 공부를 해봐야겠습니다. ; 원래는 이 쪽 게시판에 글 안 쓰고 열심히 눈팅만 하는 옵저버가 되려했는데 글을 쓰게 되었네요... 간혹가다가 한번씩 글을 남기도록 하겠습니다. _ _

#227-6. 안영기 2004/02/29 (Sun) 3차원의 경우에는.. 위 내용에서 차수를 하나씩만 올리면 됩니다. 제가 말씀드린 방법은 편의를 위해서 y = yy와의 교점을 이야기 한 것이지, 실제로는 내부 점에서 출발하는 모든 직선이 다 가능합니다. 마찬가지로 3D에서는 내부 점에서 출발하는 임의의 한 직선(계산하기 가장 쉬운 예로는 x값만 변하는 직선)과 만나는 면을 위처럼 구하되 그 방향성은 normal vector의 방향으로 결정할 수 있습니다. 단 면과 직선의 교점을 구하는 비용이 많이 들므로 고속의 간략화된 방법을 써야 합니다.(진행 방향으로 바라봤을 때 투영되는 2D 좌표계로 변환한 후 그 중에 원점을 포함하는 것만 추려내면 되는데.. 그 개수가 홀수이면 내부, 짝수이면 외부입니다. 단 폴리곤 내에 폴리곤이 감기는 경우가 있다면 아까말한 normal vector의 방향에 따른 +1 또는 -1의 값을 더한 후 위에서 했던 방식으로 해야 합니다.) Tail님 반갑습니다. 이런 내용은 항상 환영입니다.