2011-09-18 2 views
3

이 질문은 실제 코드보다는 알고리즘 및 함수의 올바른 사용에 관한 것입니다.거리를 결정하는 효율적인 방법이 있습니까?

내 코드에서 맵을 사용하여 상자를 시뮬레이션합니다. maps 요소는 vector<int>을 키로 사용하고 set<shared_ptr<foo> >을 값으로 사용합니다.

나는 모든 상자를 통해 이동하는 중첩 루프를하고 있어요 :

mit1 = boxes.begin(); //mit1 is an appropriate iterator 
int edge = 10;//represnd periodic boundary conditions 
while (mit1 != boxes.end()){ 
    vector<t> = mit1->first; 
    mit2 = mit1++; 
    while (mit2 != boxes.end()){ 
    vector<int> u = (mit2++)->first; 
    bool good = true; 
    for (int i = 0; i < 3 && good; i++){ 
     u[i] = (int)fabs(u[i] - t[i]); 
     good = u[i] == 0 || u[i] == 1 || u[i] == edge; 
    } 
    if (!good) continue; 
    } 
} 

내 관심사는 전체 중첩 루프뿐만 아니라 for 루프입니다. 인접한 모든 상자를 계산하는 기능이 더 효율적이라고 생각하십니까? for 루프 테스트를 수행하는 더 좋은 방법을 알고 있습니까?

+0

확실히 더 좋은 방법이 있습니다! – Arunmu

+0

무엇을 계산하려고합니까? 그리고 당신은 mit2와 u를 혼동하지 않았습니까? (다른 말로하면 두 번째 동안 무한 루프가 없음)? – Ofir

+0

고마워, 나는 루프를 바꿨으므로 지금은 괜찮을 것이다. 두 상자가 하나의 엔진에서 나오는 모든 경우를 제거하여 상자 내의 입자가 상호 작용할 가능성이 없다. 상자 크기는이 거리에 고정되어 있지만 상자 거리 계산이 남아 있습니다. – Yotam

답변

4

모든 충돌 감지와 동일한 조언 : 공간 거리에 따라 루프의 후보를 사전 필터링 할 수있는 일부 알고리즘 또는 데이터 구조를 사용하고 O (n)에서이 사전 필터링을 수행 할 수 있습니다. 쿼드 트리가 마음에 들거나 거친 입체지도.

편집 : 전체적인 생각을 조금 더 명확하게하기 위해 다음 알고리즘을 고려하십시오. 3D 공간에 N 개의 입자가 있고 어떤 입자가 서로 거리 D보다 더 가까운 지 알고 싶습니다. 각 bin은 목표 공간의 3 차 부피를 나타내는 3D 배열을 만들고 각 부피는 적어도 크기 D 여야합니다. 주어진 입자 X에 D보다 가까운 모든 입자를 찾으려면 배열 셀 X가 현재있는 Ax와 Ax와 모든 주변 셀의 모든 입자를 선택합니다. 충돌에 대해서는이 작은 하위 집합 만 확인하면됩니다.

M 배열 셀을 사용할 때 전체 거리 검사의 평균 사례 계산 복잡성은 O (N^2) 대신 O (N * N/M)가되지만 O) 공간.

대상 공간에 제한이없는 경우 쿼드 트리 (2D) 또는 옥텟 트리 (3D)를 사용하십시오.

+0

상자가있는 이유는이 때문입니다. 각 상자에는 입자가 들어 있고 상자에는 필터가 있습니다. 그러나, 나는 아직도 이해하기 쉽고 효율적인 방법을 찾기를 원합니다 ... – Yotam

+0

편집을 읽는 중 ... 이것은 제가하고있는 것과 정확히 같습니다. 유일한 차이점은 볼륨이 hance를 변경한다는 것입니다. 단순히 모든 쌍을 적는 테이블을 만들 수는 없습니다. 또한, 볼륨의 대부분은 비어 있으며 모든 상자를 통과하는 것이 효율적이지 않을 것입니다 ... – Yotam

+0

a) 쿼드/oct-trees는 이러한 빈 볼륨에 매우 좋습니다. b) 26 개의 빈 상자를 확인하는 것은 모든 개체 간의 거리를 비교하는 것과 비교할 때 매우 저렴합니다. c) 다시 볼륨을 변경하면 동일한 효과에 대해 oct-tree를 사용하십시오. – thiton

0

는 ... 프로그램이 무엇을하고 있는지에

를 따라 다릅니다하지만 할 때 상자의 이동 거리를 계산하는 것이 가능하다. 그러면 모든 상자가 움직이는 것은 아니지만 일부 상자가 최적화됩니다.

1

이것은 일반적인 충돌/사고사 문제의 단순화 된 버전입니다. 많은 문제가 많은 수의 다각형면으로 묘사 된 여러 개체가있을 때 특히 문제가됩니다. 이 문제에 대한 모든 해결책에 맞는 크기가 하나도 없습니다. 이 문제를 해결하는 데 도움이되는 많은 경험적 방법이 있습니다. 그중 몇 가지 :

  • 경계 상자와 경계 상자를 사용하십시오. 한 쌍의 구체 사이의 거리는 한 쌍의 상자 사이의 거리보다 훨씬 쉽게 계산할 수 있으며 한 쌍의 경계 구체 사이의 거리는 한 쌍의 경계 상자 사이의 거리보다 크지 않습니다. 이렇게하면 많은 계산을 상당히 빨리 배제 할 수 있습니다.

  • 개체의 계층 구조를 사용하십시오. 오브젝트 A, B, C 및 D가 항상 서로 가깝다면 A, B, C 및 D를 포함하는 메타 오브젝트를 작성하는 것이 유용 할 수 있습니다.이 메타 오브젝트를 후보로 간주 할 수없는 경우 단지 후보자를 후보자로 간주하지 않는 것이지요.

  • 개체가 느리게 움직이는 경우 다음 단계에서 가장 가까운 이웃이 현재 단계에서 가장 가까운 이웃이됩니다.첫 번째 추측으로 시작한 다음 근처의 다른 물체를 검색 한 다음 해외로 더 이동하십시오. 결국 (전형적으로 더 빠르다는 것보다) 당신은 나머지 모든 객체를 배제 할 것입니다.

관련 문제