KD 트리를 사용하여 점을 저장하고 다른 점에 가까운 점을 빠르게 반복 할 수 있음을 알고 있습니다. 라인과 비슷한 것이 있는지 궁금합니다.빠른 회선 질의를위한 데이터 구조?
(데이터 구조에 저장 될) 에있는 라인 L 세트와 다른 "쿼리 라인"q가 있으면 L의 모든 라인을 신속하게 반복 할 수 있기를 바란다. q "에 충분하다. 제가 사용할 계획 거리는 두 점 u와 v 사이의 최소 유클리드 거리입니다. 여기서 u는 첫 번째 선의 일부 점이고 v는 두 번째 선의 일부 점입니다. 그 거리를 계산하는 것은 문제가되지 않습니다 (십자가 관련 트릭이 있습니다).
아마 너희들은 ...TIA, 들 좋은 아이디어가 어디서 등 논문, 설명을 찾아하는 것을 알고있다.
디스크 기반 데이터베이스 시스템에서 공간 인덱싱에 사용되는 또 다른 옵션은 R-Tree입니다. KD-Tree보다 구현이 조금 더 복잡하지만 일반적으로 더 빠르다고 여겨지며 선과 다각형을 인덱싱하는 데 문제가 없습니다.
+1. 또 다른 장점을 말하면 다음과 같습니다. 노드의 경계 상자가 겹칠 수 있으므로 이러한 데이터 구조에는 "분할 요소"(중복)가 필요하지 않습니다. – sellibitze
개체 분리가 필요없는 다른 데이터 구조 제안을 위해 허용되었습니다. – sellibitze
KD 트리를 사용할 수도 있습니다.
포인트가 아닌 프리미티브에서 작동하는 KD 트리를 만드는 것이 가능합니다. 많은 광선 추적기는 삼각형 히트 테스트를 훨씬 빨리 수행하기 위해이 작업을 수행합니다. 내가 본 가장 좋은 설명은이 ray tracing tutorial입니다.
100 % 정확하지는 않지만 잠재적으로 더 빠를 수있는 해결책은 라인 세그먼트 당 포인트 목록을 유지하고이를 표준 포인트 기반 KD 트리에 삽입하는 것입니다. 가장 가까운 점을 찾은 다음 선분으로 태그를 지정하고 가장 가까운 점을 얻으십시오. 그것은 조잡하지만 다른 옵션에 비해 종종 매우 빠릅니다. "속임수"는 세그먼트를 따라 더 빠르게 (더 빠르게) 세그먼트를 더 많은 포인트 (더 느리지 만 더 정확하게)로 분할하는 사이에 큰 공간을 유지하는 올바른 균형을 찾는 것입니다.
+1 의견을 보내 주셔서 감사합니다. 나는 당신의 링크를 확인하고 그것에 대해 생각해야 할 것입니다. – sellibitze
각 잎에 점을 저장하는 대신 선분을 저장하고 그 선분을 나눌 수있었습니다. 어느 쪽이든 나는 어떻게 든 중복으로 라인을 저장하게 될 것이다. 아마도 다른 데이터 구조가 더 적절합니다 (느슨한 octree, R-Tree, ...) – sellibitze
이 거리는 선이 평행하지 않은 경우 항상 0입니다. 아니면 라인 * 세그먼트 *에 대해 이야기하고 있습니까? – Thomas
사실 상관 없습니다. 그것이 도움이된다면, 나는 그것을 선분으로 만들 수있다. 그러나 무한 길이의 선들도 좋습니다. 나는 결과가 바뀔 것이라고 기대하지 않는다. 나는 현재 두 점으로 내 행렬을 매개 변수화하고 점 u/v가 그 선분에있을 것으로 기대한다. – sellibitze
험, 3D에서 두 개의 선은 서로 다른 계획에있을 수 있기 때문에 서로 평행하지 않고 교차 할 수 없습니다. –