회전 캘리퍼스를 사용하여 XNA에서 볼록한 선체의 지향 경계 상자 찾기

Question

아마도 프로그래밍 문제보다 수학 문제가 더 많을 지 모르지만 저는 XNA에서 회전 캘리퍼 알고리즘을 구현하려고했습니다.

필자는 wikipedia에서 설명한 모노톤 체인을 사용하여 내 포인트 집합에서 볼록 선체를 추론했습니다. 이제

하나가 여기 후 나는 OBB를 찾을 수 내 알고리즘을 모델링하기 위해 노력하고있어 : 그러나 http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

, 나는 그것이 마지막 페이지에 가지 설명 DOTPR 및 CROSSPR 방법이되어있는 것을 이해하지 않는다 돌려 주다.

두 점의 교차점 제품과 두 점의 교차점 제품을 얻는 방법을 알고 있지만 두 함수가 두 가장자리/선분의 점과 교차점을 반환한다고 가정합니다. 수학의 내 지식은 인정 하듯이 제한하지만이에 대한 나의 추측이다 어떤 내 코드의이 부분에서 지시 한대로 내가 그 방법을 사용하면 알고리즘이 ... 그러나

public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float crossProduct1 = CrossProduct(segmentA1, segmentB1); 
     return crossProduct1; 
    } 

    public static float CrossProduct(Vector2 v1, Vector2 v2) 
    { 
     return (v1.X * v2.Y - v1.Y * v2.X); 
    } 

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float dotProduct = Vector2.Dot(segmentA1, segmentB1); 
     return dotProduct; 
    } 

을 찾고

  while (PolygonDot(polygon, i, j) > 0) 
      { 
       j = NextIndex(j, polygon); 
      } 

      if (i == 0) 
      { 
       k = j; 
      } 
      while (PolygonCross(polygon, i, k) > 0) 
      { 
       k = NextIndex(k, polygon); 
      } 

      if (i == 0) 
      { 
       m = k; 
      } 
      while (PolygonDot(polygon, i, m) < 0) 
      { 
       m = NextIndex(m, polygon); 
      } 

내가 polygon.Reverse이 공업으로 반 시계 방향으로 순서 이러한 점을 배치 부르는,

List<Vector2> polygon = new List<Vector2>() 
     { 
      new Vector2(0, 138), 
      new Vector2(1, 138), 
      new Vector2(150, 110), 
      new Vector2(199, 68), 
      new Vector2(204, 63), 
      new Vector2(131, 0), 
      new Vector2(129, 0), 
      new Vector2(115, 14), 
      new Vector2(0, 138), 
     }; 

주 : J에 대해 동일한 인덱스를 반환 가깝지만

, 나는 그것을 포인트의 테스트 세트를 줄 때 케이 perdue.edu의 기술 문서에 나와 있습니다. 점 집합의 convex-hull을 찾는 알고리즘은 반 시계 방향으로 점 목록을 생성하지만 y 0보다 큰 경우 y을 0으로 가정하면 화면 0,0으로 그리는 것이 왼쪽 상단에 있기 때문에 . 목록을 반대로하는 것으로 충분합니다. 마지막에 중복 지점도 제거합니다.

이 처리 후, 데이터가된다 :

• Vector2 (115, 14)
• Vector2 (129, 0)
• Vector2 (131, 0)
• Vector2 (204 63)
• Vector2 (199, 68)
• Vector2 (150, 110)
• Vector2 (1, 138)
0,123,
• Vector2 (0, 138)

제가 0과 동일하고, j는 찾은 3. 같을 때이 시험은 제 1 루프에서 실패로 라인 (115,14)의 외적 (204,63)이고 (204,63) ~ (199,68)까지의 행은 0입니다. 그러면 동일한 행의 내적도 0이므로 j와 k는 같은 색인을 공유합니다. 반면

이 테스트 세트를 제공 할 때 : 나는 http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp에있는 C++ 알고리즘을 통해 읽은하지만 난 너무 밀도가있어 http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29

: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

내 코드가 성공적으로 OBB를 반환 그것을 완전히 따르라.또한 위의 종이에 설명 된 다른 것과는 매우 다른 것으로 보입니다.

아무도 내가 건너 뛸 단계를 알고 있거나 내 코드에서 두 개의 선분으로 된 내적 및 교차 제품을 찾는 데 오류가 있는지 알고 있습니까? 누구든지 C#에서이 코드를 성공적으로 구현했으며 예제가 있습니까?

Answer 1

DOTPR은 일반적인 벡터 내적이라고 가정하고, crossprduct입니다. dotproduct가 정상 수를 반환하면 crossproduct는 주어진 두 벡터에 수직 인 벡터를 반환합니다. DOTPR (i, j)는 정점 i에서 i + 1로, j에서 j + 1까지 벡터의 dotproduct를 반환하므로 실제로 종이에 정의됩니다. CROSSPR과 동일하지만 제품 간 차이가 있습니다.

Answer 2

데이터 구조로서의 점과 벡터는 본질적으로 같은 것입니다. 둘 다 두 개의 수레로 구성됩니다 (3 차원에서 작업하는 경우 세 개). 그래서, 모서리의 내적을 취할 때, 모서리가 정의하는 벡터의 내적을 취하는 것을 의미한다고 가정합니다. 당신이 제공 한 코드는 정확히 이것을합니다.

귀하의 구현이 CrossProduct 인 것으로 보입니다 (Wolfram MathWorld 참조). 그러나, PolygonCross 및 PolygonDot에 나는 세그먼트를 표준화해서는 안됩니다 생각합니다. 반환 값의 크기는 PolygonDot 및 PolygonCross에 영향을줍니다. 불필요한 호출을 Vector2.Normalize으로 제거하면 코드 속도를 높이고 부동 소수점 값의 노이즈 양을 줄일 수 있습니다. 그러나 정규화는 결과를 0과 비교하기 때문에 붙여 넣은 코드의 정확성과 관련이 없습니다.

참조 용지는 다각형 정점이 반 시계 방향 (페이지의 첫 번째 단락은 "주석 시작"다음에 있음)으로 나열되어 있지만 예제는 polygon이 시계 방향으로 정의되어 있습니다. 따라서 PolygonCross(polygon, 0, 1)이 음수이고 j 및 k과 같은 값을 얻게됩니다.