는 3D 큐브 포인트의 선택을 접는 나는 다음과 같은 3D 큐브 선택 문제에 대한 효과적인 알고리즘을 찾기 위해 노력하고

Question

:

포인트의 2 차원 배열을 상상해 및 전화 (크기 X의 크기는 평방 할 수 있습니다) 그것 쪽.

계산을 쉽게하기 위해 max를 size-1로 선언 할 수 있습니다. 왼쪽 아래에 0,0, 오른쪽 상단에 최대를 유지하면서 6면의 큐브를 만듭니다. 최대 y를 하나의 큐브가있는면을 추적하고 Z를 사용하여 은 바로

이제

public class Point3D { 
    public int x,y,z; 

    public Point3D(){} 
    public Point3D(int X, int Y, int Z) { 
     x = X; 
     y = Y; 
     z = Z; 
    } 
} 

Point3D[,,] CreateCube(int size) 
{ 
    Point3D[,,] Cube = new Point3D[6, size, size]; 
    for(int z=0;z<6;z++) 
    {   
     for(int y=0;y<size;y++) 
     { 
      for(int x=0;x<size;x++) 
      { 
       Cube[z,y,x] = new Point3D(x,y,z); 
      } 
     } 
    } 
    return Cube; 
} 

임의의 한 지점을 선택, 우리가 세 가지 임의의 숫자를 사용할 수있는 X 같은 것을 :

Point3D point = new Point(
Random(0,size), // 0 and max 
Random(0,size), // 0 and max 
Random(0,6)); // 0 and 5 

플러스를 선택하려면 주어진 방향이 현재면 내부에 맞는지 감지 할 수 있습니다. 그렇지 않으면 우리는 측면에 위치한 큐브가 중심점을 만지는 것을 발견합니다. 지금은 임의의 지점에서 (미리 정의 된 임의의 모양과 같은) 임의의 모양을 선택하는 방법을 찾고 싶습니다

private T GetUpFrom<T>(T[,,] dataSet, Point3D point) where T : class { 
    if(point.y < max) 
     return dataSet[point.z, point.y + 1, point.x]; 
    else { 
     switch(point.z) { 
      case 0: return dataSet[1, point.x, max];  // x+ 
      case 1: return dataSet[5, max, max - point.x];// y+ 
      case 2: return dataSet[1, 0, point.x];  // z+ 
      case 3: return dataSet[1, max - point.x, 0]; // x- 
      case 4: return dataSet[2, max, point.x];  // y- 
      case 5: return dataSet[1, max, max - point.x];// z- 
     } 
    } 
    return null; 
} 

: 같은과 4 개 기능을 사용

. 그러나 Square 또는 jagged Circle로 조정하면 해결됩니다.

실제 표면적은 구부러져 있고 구석에 접혀져 있습니다. 괜찮 으면서 보완 할 필요가 없습니다 (모서리가 스티커의 중심과 일치하면 입방체의 모서리에 스티커를 붙이는 것을 상상하십시오). 모서리에 붙이고 접히려면 스티커를 제거해야합니다.) 다시 이것은 원하는 효과입니다.

중복 선택이 허용되지 않으므로 두 번 선택되는 큐브는 어떻게 든 필터링해야합니다 (또는 중복이 발생하지 않는 방식으로 계산 됨). HashSet 또는 List를 사용하고 항목이 고유한지 확인하기 위해 도우미 함수를 사용하는 것처럼 단순 할 수 있습니다 (선택 항목은 항상 최대 1000 큐브보다 낮습니다).

큐브 측면이 포함 된 클래스에서이 함수의 대리자는 다음과 같습니다. 대리자 T [] SelectShape (Point3D point, int size);

현재 큐브의 각면을 검사하여 선택 부분이 그면에 있는지 확인하려고합니다.

선택 영역의 어느 부분이 선택된 Point3D와 같은면에 있는지 계산하는 것은 위치 만 변환 할 필요가 없으므로 사소한 것입니다. 다음으로 5 개의 번역이 뒤 따르고 다른 5면을 검사하여 선택한 영역의 일부가 그면에 있는지 확인합니다.

저는 이런 문제를 해결하는 데 녹슬어지고 있습니다. 누군가이 문제에 대해 더 나은 해결책을 가지고 있는지 궁금합니다.

우리는 6 개면의 큐브를 사용하며 각각의 측면은 16 × 16 점 인 (16)의 크기를 사용 추가의 설명을 요청 @arghbleargh

. 3 차원 배열로 저장 됨 : 배열이 시작될 수 있도록 side, y, x에 대해 z를 사용했습니다 : new Point3D [z, y, x], 기본적으로 직렬화 가능한 지그재그 배열에 대해 거의 동일하게 작동합니다 그래서 좋을 것입니다.) [z] [y] [x] 그러나 각 부분 배열의 개별 초기화가 필요합니다.

크기가 5x5 인 정사각형을 선택한 점을 중심으로 선택합시다. 5x5 제곱근 빼기를 찾아 문제의 축에 2를 더하려면 x-2에서 x + 2로, y-2에서 y + 2까지를 추가하십시오.

무작위 측 selectubg 우리가 선택한 포인트 Z = 0 (는 x + 큐브의 측면), Y는 X = 6.

모두 6-2

및 + 2 6 내에 물론이고, 6 =이며 측면의 16 x 16 배열의 한계 및 선택하기 쉽습니다.

그러나 선택 점을 x = 0 및 y = 6으로 변경하면 조금 더 어려워집니다. x - 2는 우리가 선택한면의 왼쪽면을 찾아야합니다. 운 좋게도 우리는 측면 0 또는 x +를 선택했습니다. 왜냐하면 우리가 상단 또는 하단면에 있지 않고 큐브의 상단 또는 하단면으로 가지 않는 한, 모든 축은 x + = right, y + = up입니다. 왼쪽의 좌표를 얻으려면 max (size - 1) - x의 뺄셈이 필요합니다. 이 부분의 하위 섹션은 x = 13-15, y = 4-8입니다. 크기를 16으로, 최대 = 15, x = 0-2 = -2, 최대 - 원래면에서 선택할 수있는 부분은 전체 선택을 제공합니다.

선택을 0,6으로 변경하면 모든 축을 쉽게 정렬 할 수 있다는 안전성을 숨길 수 없으므로 더 복잡해집니다. 일부 회전이 필요할 수 있습니다. 가능한 번역은 4 개뿐이므로 여전히 관리가 가능합니다.

0,0으로 이동하면 문제가 실제로 나타나기 시작합니다. 이제 왼쪽과 아래 모두가 다른면을 둘러 쌀 필요가 있습니다. 더욱이, 세분화 된 부분조차도 영역이 바깥으로 떨어지게됩니다. 이 상처에 유일한 연고는 우리가 선택의 중첩 부분에 관심이 없다는 것입니다. 가능하면 가능하면 건너 뛰거나 나중에 결과에서 필터링 할 수 있습니다.

'수직 축'에서 아래로 이동 했으므로 정확한 좌표를 회전하고 일치시켜 점이 모서리 주위를 올바르게 둘러 쌀 수 있어야합니다.

각면의 축이 입방체로 접혀 있기 때문에 일부 축은 뒤집거나 회전하여 올바른 점을 선택해야 할 수 있습니다.

영역 안에있는 큐브의 모든 점을 선택하는 더 좋은 해결책이 있으면 질문이 남아 있습니다. 아마도 각면에 번역 행렬을주고 세계 공간에서 좌표를 테스트 할 수 있을까요?

Answer 1

구현하기위한 노력이 거의 필요없는 아주 좋은 솔루션을 찾았습니다.

크기가 n + 2 인 할로우 큐브 용 저장소를 만듭니다. 여기서 n은 데이터에 포함 된 큐브의 크기입니다. 이것은 만족합니다 : 측면은 접촉하고 있지만 특정 점을 겹치거나 공유하지는 않습니다.

이렇게하면 데카르트 좌표를 사용하는 조회 배열을 만들어 계산과 번역을 단순화합니다. 선택한 점의 좌표를 취하는 단일 변환 함수를 사용하여 '세계 위치'를 얻습니다.

이 함수를 사용하여 각 점을 데카르트 룩업 배열에 저장할 수 있습니다.

점을 선택하면 동일한 기능을 사용하거나 저장된 데이터를 사용하고 빼기 (AA 또는 최소 위치 얻기) 및 추가 (BB 또는 최대 위치 가져 오기)가 가능합니다.

그러면 AA.xyz 좌표와 BB.xyz 좌표 사이의 각 항목을 조회 할 수 있습니다. 각 null 항목을 건너 뛰어야합니다.

z가 0 또는 size-1이 아니므로 가운데에 '빈 큐브'의 Null 참조를 저장할 필요가없는 경우 null을 반환하는 배열 유형을 사용하여 필요한 경우 최적화합니다.

지금 큐브 차원 큐브를 선택할 수있는 다른 형상이 단순하고, 3 차원의 포인트 주어진 차원 형상을 정의하고 널 선택에 추가하지 않을 경우 룩업 어레이 형상으로 각 부분을 테스트한다. 각 위치는 한 번만 선택되므로 한 번만 선택됩니다.

큐브의 내부 및 외부 빈에 대한 테스트로 인한 약간의 계산 오버 헤드가 있지만 배열 액세스가 너무 빠르기 때문에이 솔루션이 현재 프로젝트에 적합합니다.