JavaScript 분리 Axis Theorem

Question

두 개의 사각형이 충돌하는 것을 감지하기 위해 JavaScript의 축 분리 정리를 사용하여 주위를 감싸려고합니다 (하나는 회전, 하나는 회전하지 않음). 시도만큼 열심히, 나는 자바 스크립트에서 어떻게 보이는지 알 수 없으며 자바 스크립트 예제도 찾을 수 없다. 제발, 일반 숫자 또는 자바 스크립트 코드와 설명이 가장 유용 할 것입니다.

---

업데이트 : 나는 GitHub의의의 repo에서 간단한 SAT 구현을 출시하기로 결정했습니다 기하학과 수학 이론을 많이 연구 한 후. 당신이 당신의 볼록 다각형 (이 경우 사각형)의 모든 지점을 변환해야 https://github.com/ashblue/canvas-sat

Answer 1

변형 다각형

첫째 그래서 그들은 같은 공간에있는 모든 위치 : 현재 자바 스크립트에 SAT의 작업 복사본을 찾을 수 있습니다 , 회전을 적용하여 angle.

스케일링, 변환 등의 향후 지원을 위해 매트릭스 변환을 통해이 작업을 수행하는 것이 좋습니다. 자신 만의 Matrix 클래스를 코딩하거나이 기능이 이미있는 라이브러리를 찾아야합니다 (많은 옵션이있을 것입니다).

그런 다음의 헛된 코드를 사용합니다 : points이 Point 개체 정도의 배열 인

var transform = new Matrix(); 
transform.appendRotation(alpha); 
points = transform.transformPoints(points); 

. 당신이 어떤 충돌 물건에 도착 모든 전에

충돌 알고리즘 개요

는 그래서입니다. 각 다각형 가장자리를 들어

• (모두 다각형 0 다각형 1의 가장자리) :
  충돌 알고리즘에 관해서는, 그것은 시도하는 표준 연습과 별도의 2 볼록 다각형 다음 단계를 사용하여 (귀하의 경우 사각형)입니다
  • 양쪽 polgyons을 "앞에", "스패닝"또는 "뒤"로 분류하십시오.
  • 두 폴리곤이 서로 다른면 (1 인치 전방 및 1 인치 뒤)에 있으면 충돌이 발생하지 않으므로 알고리즘을 중지 할 수 있습니다 (조기 종료).
• 여기에 오면 폴리곤을 분리 할 수있는 가장자리가 없습니다. 다각형이 교차/충돌합니다.

개념적으로 "분리 축"은 다각형을 분류 할 가장자리에 수직 인 축입니다.

이를 위해 가장자리

에 관련하여 다각형을 분류, 우리는 가장자리에 관해서 다각형의 점/정점을 분류 할 수 있습니다. 모든 점이 한면에 있으면 다각형이 그면에 있습니다. 그렇지 않으면 다각형이 가장자리에 걸쳐 있습니다 (부분적으로 한면, 부분적으로 다른면).

하는 점을 분류하기 위해, 우리는 먼저 에지의 정상을 얻을 필요가 :

// this code assumes p0 and p1 are instances of some Vector3D class 

var p0 = edge[0]; // first point of edge 
var p1 = edge[1]; // second point of edge 
var v = p1.subtract(p0); 
var normal = new Vector3D(0, 0, 1).crossProduct(v); 
normal.normalize(); 

위의 코드는 에지 방향 정상을 얻을 수있는 Z-벡터의 크로스 제품을 사용합니다. 물론 각 가장자리에 대해이 값을 미리 계산해야합니다.

참고 : 법선은 SAT에서 분리 축을 나타냅니다.

다음에, 우리는 먼저 (에지 포인트를 감산) 가장자리가 상대하게 정상으로 내적을 이용하여 임의의 점을 분류 할 수

// point is the point to classify as "in front" or "behind" the edge 
var point = point.subtract(p0); 
var distance = point.dotProduct(normal); 
var inFront = distance >= 0; 

이제 inFront는 true이고 포인트가 앞 또는 가장자리에 있으면 false, 그렇지 않은 경우.

폴리곤을 분류하기 위해 루프를 반복하는 경우, 정면이 적어도 1 개이고 뒤에 1 개 이상있는 경우 조기에 종료 할 수 있습니다. 그 이유는 이미 폴리곤이 가장자리에 걸쳐 있다고 판단되기 때문입니다 (앞이나 뒤에 있지 않음).

그럼 알다시피, 아직 코딩 할 일이 많습니다. Matrix과 Vector3D 클래스가있는 js 라이브러리를 찾아 위 코드를 구현하십시오. 충돌 모양 (다각형)을 Point 및 Edge 인스턴스의 시퀀스로 나타냅니다.

바라건대, 이것이 시작됩니다.