이 알고리즘의 이름은 다음과 같습니다.점을 비교하고 보간합니까?

StackOverflow https://stackoverflow.com/questions/1318221

  •  19-09-2019
  •  | 
  •  

문제

제 질문이 좀 이상할 수도 있겠네요.나는 알고리즘을 "개발"했는데 비슷한 알고리즘이 이미 있는지는 모르겠습니다.

그 상황:트랙 포인트(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 순서 공간 채우기 곡선.나는 이 기술을 사용하여 쿼드트리, 에 대한 데이터 구조 적응형 메시 개선 제가 한 번 작업한 코드는 그리드를 통과하고 입자 사이의 거리를 결정하기 위해 설명하는 것과 매우 유사한 알고리즘을 사용했습니다.

유사성은 즉시 명백하지 않을 수도 있습니다.구간 위치에만 관심이 있으므로 이 단계에서는 구간의 모든 지점을 동등한 것으로 효과적으로 처리합니다.이는 분리된 점만 있는 공간을 선택하는 것과 같습니다. 점을 그리드에 효과적으로 '맞추는' 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top