그리드에서 회전 한 후 다각형이 차지하는 위치를 계산하십시오.

Question

비슷한 질문을했지만, 아무도 내 문제와 관련이 없다고 생각합니다.

저는 10x10의 그리드 셀에서 간단한 폴리곤 (예 : 직사각형, L 모양과 같은 다각형)의 이동과 회전을 C++로 코딩하고 있습니다.

너비 = 1 셀 및 높이 = 3 셀의 사각형이 있다고 가정 해 보겠습니다. 8 방향으로 쉽게 번역 할 수 있습니다. 그러나이 폴리곤을 45º 회전시키려는 경우 얻을 수는 있지만 사각형이 현재 차지하고 있거나 부분적으로 차지하고있는 셀을 계산하고 싶습니다.

나는 사각형의 질량 중심 즉, 그 셀을 가지고있다. 크기에 따라 회전하기 전에 직사각형이 차지하는 위치를 계산할 수 있습니다. 그러나 회전 후에는 직사각형이 차지하는 셀 위치를 계산하는 방법을 찾을 수 없습니다.

대단히 감사합니다!

Answer 1

당신은 확실히 경계 상자의 문제처럼이 처리 할 수 ​​있습니다 -

y를 그들이 점유 세포 수 인이 코너의 좌표 X와 사각형의 네 모서리를 타고 -에 대한 예를 들어, 및 의 중심은 o(2,2)에 집중되어 있으며 모서리 (x, y) 형식으로 표시된이 네 모서리는 - a(1.5,3.5) b(2.5,3.5) c(2.5,0.5) d(1.5,0.5)이됩니다. 이 명확한 경우

, 난 당신이 이미으로 이해 수도 나머지 절차는 여기처럼 여러 번 이전에 설명 된 생각 -

Calculate Bounding box coordinates from a rotated rectangle

이 요약 2D에 대한 표준 매트릭스를 적용하려면 이 4 개의 모서리로 회전하고 예를 들어 새로운 모서리를 얻으십시오.

a'.x = o.x + (a.x - o.x) * cos(t) + (a.y - o.y) * sin(t) 
a'.y = o.y - (a.x - o.x) * sin(t) + (a.y - o.y) * cos(t) 

및 다른 점에 대해서도 마찬가지이다. 그런 다음 max and min x and y을 찾으면 사각형이 차지하는 셀을 나타냅니다. 다른 볼록 다각형에 대해서도 비슷한 작업을 수행 할 수 있습니다.

업데이트 : 회전 된 다각형이 차지하는 정확한 셀 수를 얻으려면 Fang이 언급했듯이 경계 상자 내의 모든 사각형 셀에 대해 다각형 교차 검사를 수행해야합니다. 이것 좀 봐 -

여기

How to check intersection between 2 rotated rectangles?

Answer 2

내가 할 것 인 것이다 :

1) 원래 다각형의 정점을 가져옵니다. 다각형은 연결된 그리드 셀로 구성되어 있으므로이 정점의 좌표는 모두 정수라고 가정합니다.

2) 다각형 정점을 회전합니다. 다각형을 회전하는 방법을 알면서이 작업을 수행하는 방법을 알고 있다고 가정했습니다.

3) 지정된 셀이 회전 된 다각형에 여전히 사용되고 있는지 여부를 확인하려면 셀에 회전 된 다각형과 교차가 있는지 확인하십시오. 그래서, 이것은 기본적으로 square-to-polygon 교차 검사입니다. 교차점이 전혀 없거나 교차점이 모서리 또는 정점이면이 셀이 회전 된 다각형에 의해 점유되지 않았다고 결론 내릴 수 있습니다.

4) 모든 셀에 대해 3 단계를 수행하십시오.

4 단계에서 모든 셀을 루핑하는 대신 실제로 회전 된 다각형의 경계 상자를 사용하여 사각형 - 다각형 교차 검사에서 일부 셀을 쉽게 제외 할 수 있습니다. 그러나 10x10 셀만 있으면 성능 차이를 보지 않고도 빠져 나갈 수 있습니다.