C++에서 2D 간격 검색을 구현하는 가장 좋은 방법은 무엇입니까?

Question

간격의 2D 그리드가 있다고 가정합니다. x 축을 따라 간격을 설정하고 y 축을 따라 간격을 설정합니다. 이제 x 축과 y 축에서 새 객체가 두 개가 속하는 간격을 결정해야합니다. 새로운 물체가 숫자에, 하나는 x 좌표이고 다른 하나는 y 좌표라고 가정 해 봅시다. 객체가 들어 맞는 x와 y의 간격을 결정하여 저장된 데이터를 검색하고 싶습니다.

나는 std::map<IntervalX, IntervalY, DataToStore> map 또는 std::multimap<IntervalX, IntervalY, DataToStore> map 유사한 것을 생각했다. 이를 구현하는 방법에 대한 제안 사항이 있으므로 간격 쌍에 저장된 데이터를 검색하는 것이 매우 효율적이며 빠르며 O(n²)이 아닙니다.

편집 : 간격은 두 개의 부동 소수점 값으로 결정됩니다. 예 : x 축을 따라있는 간격 [0.5, 3.0]. 따라서 0.5가 포함되고 3.0은이 간격에 포함되지 않지만 양의 x 방향으로 다음 간격에 포함됩니다.

간격 해체와 중복되지 않고 중첩됩니다. 간격의 조합은 선의 일부분입니다. 저는 평면을 사각형 세트로 타일링했고 점이 속하는 사각형 영역을 알고 싶습니다.

예를 들어, x 축 방향의 간격은 간격 크기가 0.5이고 y 방향으로 0에서 10까지입니다. -axis는 간격 크기가 1.0 인 2에서 15로 시작합니다. 간격이 떨어지는 점 P (x = 0.7, y = 3.0)? x 축에서 간격 2이고 y 축에서 간격 2입니다. 이제 해당 간격 쌍에 대해 저장된 데이터를 검색해야합니다.

필자는 각 축을 따라 약 10000 개의 간격을 가지며 2 초마다 (약 또는 그 이하) 약 500 개를 검색해야하므로 개체 간격의 결정이 빨라야합니다.

Answer 1

지금 우리가 알고있는 그것은 타일면입니다 : 간단한 솔루션은 두 개의 정렬 된 배열 될 것이다 - X 축 간격으로 하나, Y 축 간격 하나. 그런 다음 std::lower_bound을 사용하여 두 번 검색합니다. 각 검색에 대해 예상 복잡도는 log n입니다. 성능을 테스트 한 결과 병목 현상이 나타난다면 다시 테스트해야합니다.이 코드는 매우 간단하고 이미 테스트 된 std::sort 및 std::lower_bound에 많이 의존 할 것입니다. 당신이 일괄들 (500)을 가지고있는 경우

그리고 ... 매 2 초 ... 너무으로 정렬 (2 회 : 한 번 X에 다음 Y에)를 줄이기 위해 각 항목의 하한을 사용하여 정렬 된 순서로 검색 다음 항목에 대해 검색된 항목 수 ... 실제로는 성능 문제가 있다고 판단한 후에 만 ​​시도해야하는 최적화에 대해 이야기하고 있습니다.

비행기의 각 직사각형 영역과 관련된 데이터는 다음과 같습니다. std::lower_bound에서 얻은 x- 및 y- 인덱스로 인덱싱 된 해당 데이터에 대한 포인터의 2 차원 배열을 만듭니다. 2 차원 배열에 대한 액세스의 복잡성이 예상됩니다.

Answer 2

간격이 겹치지 않으면 (각 축마다 하나의 간격으로 점이 매핑되어 있음을 알리기 때문에), 정렬 된 순서로 저장합니다. max (Interval_n) < 분 (Interval_n + 1) 효율적인 2 진 검색 룩업을 가능하게합니다. 그들이 겹치는 경우

, 당신은 분을 정렬 할 수 있지만 이것은 단지 당신에게 조금 도움이됩니다.