이 알고리즘의 이름은 다음과 같습니다.점을 비교하고 보간합니까?
문제
제 질문이 좀 이상할 수도 있겠네요.나는 알고리즘을 "개발"했는데 비슷한 알고리즘이 이미 있는지는 모르겠습니다.
그 상황:트랙 포인트(2D)로 정의된 트랙이 있습니다.예를 들어 트랙 포인트는 회전을 나타냅니다.트랙 포인트 사이에는 직선만 있습니다.이제 이 2D 공간에 일련의 좌표가 주어졌습니다.첫 번째 트랙 포인트에서 새 좌표까지의 거리와 처음 두 트랙 포인트의 간격에 대한 거리를 계산합니다.측정된 좌표까지의 거리가 첫 번째 트랙 포인트에서 두 번째 트랙 포인트까지의 거리보다 짧은 경우 이 포인트가 이 간격 사이에 있다고 가정합니다.그런 다음 이에 대해 선형 보간을 수행합니다.더 크면 다음 간격으로 확인하겠습니다.
따라서 기본적으로 간격 거리를 취하고 거기에 맞추려고 노력합니다.이 트랙을 따라 움직이는 물체를 추적하려고 합니다.
이 말이 누군가에게 친숙하게 들리나요?누군가 유사한 기존 알고리즘에 대한 제안을 생각해 낼 수 있습니까?
편집하다: 지금까지 설명한 내용을 통해 위치가 트랙 포인트와 여러 번 연관되지 않는다는 점을 명확히 하고 싶습니다.Jonathan이 만든 훌륭한 ASCII 그림을 생각해 보십시오.
X 위치는 Segment 1과 2 내에 있는 것으로 확인됩니다(S12).이제 다음 위치는 Y입니다. 이는 S12에 있을 만큼 충분히 가까운 것으로 간주되지 않습니다.S23으로 이동하여 제대로 들어왔는지 확인하겠습니다.
이 값이 포함되어 있으면 S12에서 다른 값을 확인하지 않을 것입니다. 이미 다음 세그먼트에서 값을 찾았기 때문입니다.알고리즘은 "뒤를 돌아보지 않는다".
하지만 여기서부터 올바른 세그먼트를 찾지 못하면 첫 번째 세그먼트에서는 멀리 떨어져 있지만 어쨌든 다른 세그먼트에서는 여전히 더 멀리 떨어져 있기 때문에 값을 삭제하고 다음 위치를 찾습니다. 다시 S12로 돌아왔습니다.
루프는 여전히 문제로 남아 있습니다.S23에 대해 Y를 얻은 다음 2~3개 위치를 건너뛰는 경우(너무 멀기 때문에) 경로를 잃을 수도 있습니다.S56에 이미 있을 위치를 S34에서 결정할 수 있습니다.
어쩌면 어떤 세그먼트에 있어야 하는지 알 수 있는 평균 속도를 생각해 낼 수 있을 것입니다.
세그먼트가 클수록 올바른 결정을 내릴 가능성이 더 커지는 것 같습니다.
해결책
귀하가 설명한 알고리즘에 대해 제가 우려하는 점은 그것이 '탐욕적'이며 '잘못된' 트랙 세그먼트(또는 적어도 해당 지점에 가장 가깝지 않은 트랙 세그먼트)를 선택할 수 있다는 것입니다.
ASCII 아트를 한계까지 밀어붙일 시간입니다.다음 경로(숫자는 트랙 포인트 목록의 순서를 나타냄)와 좌표 X(및 이후에는 Y)를 고려하십시오.
1-------------2
|
| Y
X |
5-----+-----6
| |
| |
4-----3
귀하의 설명을 어떻게 해석해야 합니까?
[C] 첫 번째 트랙 포인트에서 새 좌표까지의 거리와 처음 두 트랙 포인트의 간격에 대한 거리를 계산합니다.측정된 좌표까지의 거리가 첫 번째 트랙 포인트에서 두 번째 트랙 포인트까지의 거리보다 짧은 경우, 이 포인트가 이 간격 사이에 있다고 가정합니다.[...] [i] 더 크면 [...] 다음 간격으로 확인하세요.
첫 번째 문장의 의미는 다음과 같습니다.
- TP1(트랙 포인트 1)에서 TP2까지의 거리를 계산하여 D12라고 부릅니다.
- TP1에서 X(D1X라고 함)까지의 거리와 TP2에서 X(D2X라고 함)까지의 거리를 계산합니다.
까다로운 부분은 조건문의 해석입니다.
내 생각에 D1X 또는 D2X가 D12보다 작으면 X는 트랙 세그먼트 TP1에서 TP2(세그먼트 S12라고 함)에 있는(또는 가장 가까운) 것으로 간주됩니다.
다이어그램에서 X의 위치를 보면 D1X와 D2X가 모두 D12보다 작다는 것이 어느 정도 분명하므로 알고리즘에 대한 나의 해석은 X가 S12와 연관된 것으로 해석하지만 X는 확실히 S23 또는 S56에 더 가깝습니다. S12에 해당합니다(단, 고려하지도 않고 폐기됨).
귀하의 알고리즘에 대해 제가 오해한 것이 있습니까?
조금 생각해 보면 다음과 같습니다.내가 당신의 알고리즘을 해석한 것은 점 X가 TP1을 중심으로 한 반경 D12의 원 또는 TP2를 중심으로 한 반경 D12의 원 안에 있으면 X를 S12와 연관시킨다는 것입니다.그러나 점 Y도 고려한다면 제가 제안하는 알고리즘은 이 점을 S12와 연관시킬 것입니다.
알고리즘을 세련되게 표현하면 MAX(D1Y, D2Y) < D12
, 이면 Y가 S12와 관련된 것으로 간주되지 않습니다.그러나 X는 여전히 S23이나 S56보다는 S12와 관련이 있는 것으로 간주됩니다.
다른 팁
이 알고리즘의 첫 번째 부분은 불연속적인 공간을 통해 이동하는 것을 연상시킵니다.그러한 공간을 표현한 예는 다음과 같습니다. Z 순서 공간 채우기 곡선.나는 이 기술을 사용하여 쿼드트리, 에 대한 데이터 구조 적응형 메시 개선 제가 한 번 작업한 코드는 그리드를 통과하고 입자 사이의 거리를 결정하기 위해 설명하는 것과 매우 유사한 알고리즘을 사용했습니다.
유사성은 즉시 명백하지 않을 수도 있습니다.구간 위치에만 관심이 있으므로 이 단계에서는 구간의 모든 지점을 동등한 것으로 효과적으로 처리합니다.이는 분리된 점만 있는 공간을 선택하는 것과 같습니다. 점을 그리드에 효과적으로 '맞추는' 것입니다.