제 전공 분야가 아니라서 정확히는 모르겠지만 예전에 언뜻 들었던 기억이 있습니다. collision detection이란, 예를 들면 FPS 게임에 등장하는 물체들이 서로 닿았는지 닿지 않았는지를 계산하는 것인데, 이를 위한 중간 과정 중에 각 물체를 감싸는 최소 면적 (혹은 체적)의 바운딩 박스를 만들어내는 알고리즘이 있었습니다. 아마 bugiii 님께서 답해주신 내용도 이와 비슷한게 아닐까 싶고, 혹은 (그 알고리즘의 이름은 잊어먹었지만) 점진적으로 점점 작은 박스로 깎아나아가는(?) 방식도 있었습니다.
-- 자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!
O(n log n)이라는데, point의 개수가 아주 많은 게 아니라면 첫 번째 댓글에 달린 방법만 써도 (비록 O(n^2)이긴 하지만) 계산량이 상당히 줄지 않을까 싶습니다. 외접사각형 계산을 360번 대신 최대 n번만 하면 될 테니까요. 상당히 들쭉날쭉한 이미지라면 먼저 convex hull을 구하고 계산을 해서 계산량을 더 줄일 수도 있을 테구요.
Quote:
I have got an idea for you:
This is based on the fact that (at least) one of the edges in your polygon will be parallel to an edge in the rectangle...
For each vertex n in your polygon.
Create a copy of your polygon and do a simple 2d rotation so that the edge from n to (n+1) is aligned to an axis.
Calculate the bounding axis- aligned rectangle.
Take the smallest of your n bounding rectangles, and rotate it back to fit the original polygon.
다각형의 모든 꼭지점 x, y 중 가장 작은 x, y 와 가장 큰 x,
다각형의 모든 꼭지점 x, y 중 가장 작은 x, y 와 가장 큰 x, y 가 그 다각형의 바운딩 박스의 왼쪽 위와 오른쪽 아래 좌표가 됩니다.
일단, 각 꼭지점의 x, y 를 원하는 만큼 변경 (회전, 스케일, 비틀기 등) 한다음 최소, 최대를 구하시면 됩니다. 꼭지점 변환은 3D 그래픽스 관련 주제에서 많이 다루고 있습니다.
1도씩 돌린 다음에 전체를 다 검사하지 말고사각형과 내적했던 점 부근
1도씩 돌린 다음에 전체를 다 검사하지 말고
사각형과 내적했던 점 부근에서만 검사하면
금방 끝날겁니다.
collision detection이라는 키워드로 한 번 찾아보셔요.
collision detection이라는 키워드로 한 번 찾아보셔요.
제 전공 분야가 아니라서 정확히는 모르겠지만 예전에 언뜻 들었던 기억이 있습니다. collision detection이란, 예를 들면 FPS 게임에 등장하는 물체들이 서로 닿았는지 닿지 않았는지를 계산하는 것인데, 이를 위한 중간 과정 중에 각 물체를 감싸는 최소 면적 (혹은 체적)의 바운딩 박스를 만들어내는 알고리즘이 있었습니다. 아마 bugiii 님께서 답해주신 내용도 이와 비슷한게 아닐까 싶고, 혹은 (그 알고리즘의 이름은 잊어먹었지만) 점진적으로 점점 작은 박스로 깎아나아가는(?) 방식도 있었습니다.
--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!
[url=http://forum.java.sun.com/thread.js
요 글에서 링크를 걸어둔 요런 거를 찾으시는 걸까요? Java 버전이긴 합니다만;;;
O(n log n)이라는데, point의 개수가 아주 많은 게 아니라면 첫 번째 댓글에 달린 방법만 써도 (비록 O(n^2)이긴 하지만) 계산량이 상당히 줄지 않을까 싶습니다. 외접사각형 계산을 360번 대신 최대 n번만 하면 될 테니까요. 상당히 들쭉날쭉한 이미지라면 먼저 convex hull을 구하고 계산을 해서 계산량을 더 줄일 수도 있을 테구요.
$PWD `date`
댓글 달기