엄청난 양의 점 데이터 (2D로 표시) (매초 수천 개)가 있습니다. 이지도에는 몇 개의 고정 된 다각형 (수십에서 수백 가지)이 있습니다.어떤 폴리곤에 점이 있는지 확인합니다.
폴리곤이 놓여있는 각 포인트 (폴리곤이 교차 할 수 있음)에 대해 실시간으로 (다소 강력한 랩톱에서 몇 밀리 초의 순서로) 결정하고 싶습니다. 나는 ray casting algorithm을 사용할 것이라고 생각했습니다.
그럼에도 불구하고 모든 폴리곤을 스캔하지 않으려면 데이터를 사전 처리하는 방법이 필요합니다. 따라서 트리 접근법 (PM quadtree 또는 Rtree?)을 사용하는 것이 좋습니다. 다른 관련 방법이 있습니까? 권장되는 좋은 PM Quadtree 구현이 있습니까 (C (++), Java 또는 Python과 같은 언어에서 선호).
저는 Java로 여러 다차원 인덱스의 라이브러리를 개발했습니다.이 라이브러리는 here입니다. 여기에는 R * Tree, STR-Tree, 4 quadtrees (점 2 개, 직사각형 2 개) 및 비평 트리 (좌표를 삽입하여 공간 데이터로 사용할 수 있음)가 포함됩니다. 나는 또한 PH-Tree을 개발했다.
모든 직사각형/포인트 기반 트리가 있으므로 경계 상자를 계산하는 등의 방법으로 다각형을 사각형으로 변환해야합니다. 반환 된 모든 경계 상자의 경우 폴리곤이 실제로 점과 교차하는 경우 수동으로 계산해야합니다. 직사각형이 너무 길지 않으면 효율적입니다.
보통 PH-Tree는 가장 효율적인 트리이며, 점이 100 개의 직사각형 이하 (더 좋게는 10 이하)로 교차하는 경우 빠른 건물 시간과 매우 빠른 쿼리 시간을가집니다. STR/R * -trees는 큰 겹침 크기 (1000+)에서 더 좋습니다. quadtree는 약간 신뢰할 수 없으며 수백만 개의 요소를 삽입 할 때 숫자 정밀도에 문제가 있습니다.
1 백만 개의 직사각형이있는 3D 트리를 가정하고 쿼리 당 평균 한 개의 결과가 있다고 가정하면 PH-Tree는 내 데스크톱 (i7 4xxx)의 쿼리 당 약 3 마이크로 초, 즉 밀리 초당 300 개의 쿼리를 필요로합니다.