저는 200 픽셀 x 200 픽셀의 2D 래스터를 가지고 있습니다. 이것을 각 10x10 픽셀의 400 "버킷"으로 세분해야합니다.해시 맵을 사용하여 하위 영역으로 점 나누기
그런 다음 위에서 설명한 구조로 매핑하려는 점 목록 (약 200k)이 있습니다. 따라서 포인트가 10x10 영역으로 떨어지면 양동이에 추가합니다.
이제는 해시 테이블이 훌륭하게 수행 할 수있는 것처럼 보입니다. 이것이 STL을 사용하여 가능했는지 궁금합니다.
stl :: unordered_map을 사용하고 버킷 양을 지정했지만 작동하지 않는 경우 해당 요청을 무시합니다. (동일한 영역에 매핑되는 항목이 너무 많기 때문에 제 경우에는 문제가되지 않습니다. 반대로 그 부분이 중요합니다.)
STL로 이것을 수행 할 수있는 방법이 있습니까?
두 가지 용어가 혼란 스럽다고 생각합니다. 룩업이 너무 많은 쓸모없는 요소를 스캔하지 않도록 요소를 균등하게 분배하는 데 사용되는 내부 구현 세부 정보 인 해시 테이블 의미의 "버킷"이 있습니다. 또한 공간 의미에서 "버킷 (buckets)"이 있는데, 이는 영역으로 공간을 분할하여 요소가 정확히 하나의 버킷에 속하는 것입니다. 일반적으로 공간 버킷 시스템을 직접 제어 할 수 있습니다 (모든 부분이 분리되어 선택됩니다). 그러나 해시 테이블을 사용하면 버킷을 매우 정확하게 제어 할 수 없습니다. 초기 크기를 선택할 수도 있지만, 해시 테이블이 성능을 향상시키기 위해 크기를 늘리는 것이 좋다고 생각하면 거의 확실하게 그렇게 할 것입니다. 그렇지 않은 경우 검색 시간이 상당히 단축됩니다.
공간을 격자로 나눈 다음 점을 격자에 분배하려는 경우 std::unordered_map s의 2D 배열 (원시 배열 또는 일부 격자 선형화 사용)을 만드는 것이 가장 좋습니다. 각각의 공간은 한 공간의 특정 영역에서만 포인트를 보유합니다. 그런 식으로 요소를 찾아보고 싶은 경우 해당 양동이에 대한 점을 보유한지도로 이동 한 다음지도에 값을 조회하도록 요청합니다.이 때지도에서 자체 체내 버킷 팅 시스템과상의하여 포인트를 찾습니다. 필요. 즉, 공간 영역에서 흥미로운 쿼리를 수행 할 수 있도록 점을 분할하려는 경우 점은 해당 영역 전용 버킷에 저장되지만 해시 테이블에 저장되어있는 버킷 내에서 만들 수 있습니다. 그 점을 찾는 것이 더 적은 시간이 걸립니다.
또는 요소를 효율적으로 저장하고 공간 버킷의 모든 지점을 효율적으로 쿼리 할 수있는 quadtree 또는 kd-tree와 같은 공간 데이터 구조를 사용하는 것이 좋습니다.
희망이 도움이됩니다.
때로는 가장 큰 도전은 "필요한 것"을 이해하고 "원하는"것과 혼동하지 않기 위해서입니다. 작은 힌트와 이해에 좋은 직장. :) –
모든 공간 데이터 구조와 마찬가지로 사용할 올바른 구조에 관한 실제 질문은 구조에 대한 의도 된 용도로 귀결됩니다. kd-tree는 log (n) 점 검색 또는 가장 가까운 이웃에 대한 적응 형 저장 장치에서 놀랍습니다. 렌더링 영역에서는 RayTracers에서 많이 사용됩니다. 물리학 분야에서는 때때로 충돌 감지를위한 프 루닝 프리미티브 (pruning primitives)에 사용됩니다. 아래에서 정수식 점에 대해 점에 대한 해시 체계를 만들고 저장소에 해시 테이블을 사용할 수 있지만이 대답에서 언급 한 것처럼 가장 좋은 방법은 아닙니다. – Mranz
당신은 절대적으로 옳습니다. 나는 이것을 너무 피곤하고 조금 늦게 타이핑했다. 오늘 아침에 그것에 대해 생각할 때 나는 내 실수를 깨달았다. :) – KWyckmans
당신이 좋아하는 버킷의 해시 코드를 생성 할 수 있습니다
[상위 4 바이트 인을 X] 당신이 정말 원하는 것은
size_t hash = (p.X/10) << 16 | (p.Y/10);
map[hash].push_back(hash);
'버킷'가 아니라 [하위 4 바이트는 Y입니다] 지도. 당신은지도
typedef pair<int,int> P
typedef set<P> PS
typedef map<P,PS> PSM // say the point at right edgexbottomedge defines the BLOCK you want.
PSM psm(400)
타다의지도 같은 것을 원한다. 그것이 당신이 찾고있는 것입니다 ...
그래서 캔버스를 400 조각으로 나누고 개별적으로 추적하고 싶습니다. 각 블록은 해당 블록 범위 내의 지점을 포함 할 수 있습니다. 맞습니까? –