빠른 Ray 교차를 위한 Line Segment 컨테이너?(2D)
https://stackoverflow.com/questions/732687
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
광선이 있습니다. 광선에 닿는 가장 가까운 선분을 찾아야 합니다.선분을 먼저 정렬하면 O(log n) 시간 안에 이 작업을 수행할 수 있을 것 같은데 어떻게 정렬해야 하는지 기억이 나지 않습니다.어떤 종류의 트리가 가장 잘 작동할 것 같은데, 시작점과 끝점을 기준으로 트리를 어떻게 정렬합니까?또한 가능하다면 이 데이터 구조에 빠르게 삽입하고 싶습니다.
하나의 광선과 하나의 선 세그먼트에 대한 코드는 많지만 하나의 광선과 여러 선 세그먼트에 대한 코드가 필요합니다.구글에 무슨 용어를 검색해야 할지 모르겠습니다.
적절한 기사에 대한 링크가 있으면 좋습니다. C++ 코드가 더 좋습니다.감사해요!:)
추신:선분은 실제로 CCW 순서로 정렬된 자체 교차하지 않는 다각형의 가장자리입니다.하지만 다른 방식으로 정렬하면 약간의 이점이 있을 수 있다고 생각합니다.
이것은 모두 2D입니다.
다시 생각해보면, 나는 이것이 완전히 확실하지 않습니다 ~이다 가능한.일종의 공간 분할이 도움이 될 수 있지만 그렇지 않으면 임의의 광선과 비교할 수 있도록 선을 정렬하는 방법을 생각할 수 없습니다.
해결책
다각형 (Min-Max X, Y 좌표)의 경계 상자를 가져 와서 상자 안에 그리드를 만들 수 있습니다. 그런 다음 각 셀에 대해 세포를 가로 지르는 모든 라인을 기억하십시오.
다음과 같은 Intesction을 찾으십시오.
- 광선이 먼저 쳤는지 알아보십시오 (O (1))
- 사용 그리드 트래버스 알고리즘 그리드를 통해 광선을 "그리기"합니다. 비어 있지 않은 셀에 닿으면 모든 선을 확인하고 교차로가 셀 내부에 있는지 확인하고 가장 가까운 교차로를 선택하십시오. 모든 교차로가 셀 외부에 있으면 계속합니다 (O (그리드 길이)).
그리드 계층을 만들 수도 있습니다 (즉. 쿼드 트리 - 당신이 요구 한 나무)와 같은 알고리즘을 사용하여 걸어갑니다. 이것은 3D의 Raytracing에서 이루어집니다 그리고 시간 복잡성은 O (sqrt (n))입니다.
또는 Raytracer에서 수행 한 접근 방식을 사용하십시오.
- 빌드 a 쿼드 트리 라인을 포함하는 (기사에서 Quadtree를 구축 할 수 있습니다)-4 개의 하위 노드 (하위 구조)에 너무 많은 객체를 포함하는 경우 노드 (= 영역) 분할됩니다.
전부 모으다 잎 노드 광선에 맞은 쿼드 트리의 :
루트에 대한 Ray-Rectangle 교차 (단단하지 않음)를 계산하십시오. 뿌리가 광선에 맞으면 아이들을 재귀 적으로 진행하십시오.
이것에 대한 멋진 점은 트리 노드가 ~ 아니다 히트, 당신은 전체 하위 트리 (잠재적으로 큰 직사각형 영역)를 건너 뛰었습니다.
결국, 이것은 그리드를 가로 지르는 것과 동일합니다 - 당신은 광선의 경로에서 가장 작은 셀을 수집 한 다음 교차로를 위해 모든 물체를 테스트합니다. 당신은 그들 모두를 테스트하고 가장 가까운 교차로를 선택하면됩니다 (따라서 Ray의 경로에서 모든 줄을 탐색합니다).
이것은 O (sqrt (n))입니다.
그리드 Traversal에서 교차로를 찾으면 검색을 중지 할 수 있습니다. Quadtree Traversal로이를 달성하려면 어린이들을 올바른 순서로 깎아야합니다. 4 개의 직장 교차로를 거리별로 정렬하거나 4 셀 그리드를 영리하게 통과합니다 (우리는 순회로 돌아갑니다).
이것은 단지 다른 접근법이며, 비교적으로 구현하기가 어렵고 잘 작동합니다 (실제 데이터에서 테스트했습니다 - O (sqrt (n)). 다시 말하지만, 당신은 최소한 몇 줄의 줄이있는 경우에만이 접근법의 혜택을 누릴 수 있습니다. 다각형에 10 개의 가장자리가 10 개의 가장자리가있을 때 모든 것을 테스트하는 것과 비교할 때 이점이 거의 없을 것입니다.
다른 팁
정렬은 O (n log n) 조작이 최상의 작업임을 명심하십시오. 각각 개별적으로 확인하는 것이 좋습니다.
당신이 그 중 하나라도 맞을 것이라고 어떻게 확신합니까?선이라면 그럴 가능성이 없습니다.
실제로 다각형인 경우(예:평면) 테스트하려는 경우, 이런 종류의 작업을 수행하는 일반적인 방법은 먼저 평면과 교차한 다음 내부/외부 다각형에 대해 해당 점(2D 좌표)을 테스트하는 것입니다.
어쩌면 내가 당신이 실제로하고있는 일을 오해했을 수도 있습니다.
일반적으로 복잡한 수치의 교차점을 가속화하는 것은 공간 분할을 통해 수행됩니다(테스트 비용이 많이 드는 경우 메일박스와 같은 기술).
[업데이트:원래 의도를 잘못 읽었습니다.] (2d) 공간 분할을 계속 사용할 수 있지만 오버헤드가 그만한 가치가 없을 수 있습니다.개별 테스트는 저렴합니다. 폴리가 복잡하지 않다면 그냥 걸어보는 것이 더 저렴할 수 있습니다.설명으로는 말하기 어렵습니다.
설명을 요청하십시오. 이것이 맞습니까?
- 동적 라인 세그먼트 세트가 있습니다 엘.
- 쿼리 : 주어진 어느 포인트 (x, y) 및 및 어느 이 시점부터 광선의 방향, 당신은 가장 가까운 선을 결정하고 싶습니다. 엘 (만약에 어떠한) ?
그래서 포인트 (x, y)가 수정되지 않습니까? (어떤 지점과 방향 일 수 있습니까?)
