포인트 시퀀스 보간
https://stackoverflow.com/questions/107598
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
공간에 있는 임의의 일련의 점들이 주어지면 어떻게 그 점들 사이에 부드러운 연속 보간을 생성할 수 있습니까?
2D 및 3D 솔루션을 환영합니다.임의의 세분성으로 점 목록을 생성하는 솔루션과 베지어 곡선에 대한 제어점을 생성하는 솔루션도 높이 평가됩니다.
또한 점을 받을 때 곡선의 초기 부분을 근사화하여 그림을 그릴 수 있는 반복 솔루션을 보는 것도 좋을 것입니다.
해결책
그만큼 Catmull-Rom 스플라인 모든 통제 지점을 통과하는 것이 보장됩니다.다른 유형의 스플라인에 대한 중간 제어점을 조정하는 것보다 이것이 더 편리하다고 생각합니다.
이것 Christopher Twigg의 PDF 스플라인의 수학에 대한 간략한 소개가 있습니다.가장 좋은 요약 문장은 다음과 같습니다.
Catmull-Rom 스플라인은 C1 연속성, 로컬 제어 및 보간을 가지지 만 제어점의 볼록한 선체 안에는 안됩니다.
다르게 말하면, 점이 오른쪽으로 급격하게 구부러진 것을 나타내는 경우 스플라인은 오른쪽으로 회전하기 전에 왼쪽으로 뱅크됩니다(해당 문서에 예제 그림이 있습니다).이 경우 예제 행렬의 타우 매개변수를 사용하여 이러한 회전의 견고성을 제어할 수 있습니다.
여기는 다른 예시 다운로드 가능한 DirectX 코드를 사용하세요.
다른 팁
한 가지 방법은 라그랑주 다항식, 이는 주어진 모든 데이터 포인트를 통과하는 다항식을 생성하는 방법입니다.
대학교 1학년 때 저는 이 작업을 2D로 수행하기 위한 작은 도구를 작성했습니다. 이 페이지에서 찾아보세요, 이를 라그랑주 솔버라고 합니다.Wikipedia의 페이지에는 샘플 구현도 있습니다.
작동 방식은 다음과 같습니다.n차 다항식이 있고, p(x), 여기서 n은 보유한 포인트 수입니다.그것은 형태를 가지고 있습니다 a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, 어디 _ 첨자입니다, ^ 힘이다.그런 다음 이것을 일련의 연립 방정식으로 바꿉니다.
p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n
위의 내용을 증강 행렬로 변환하고 계수를 해결합니다. a_0 ... a_n.그런 다음 모든 점을 통과하는 다항식을 갖게 되며 이제 점 사이를 보간할 수 있습니다.
그러나 이는 곡률 등을 조정할 수 있는 방법을 제공하지 않으므로 목적에 적합하지 않을 수 있습니다. 변경할 수 없는 단일 솔루션에 갇히게 됩니다.
당신은 살펴 봐야합니다 B-스플라인.베지어 곡선에 비해 장점은 각 부분이 로컬 점에만 의존한다는 것입니다.따라서 점을 이동해도 멀리 있는 곡선 부분에는 영향을 주지 않습니다. 여기서 "멀리"는 스플라인 매개변수에 의해 결정됩니다.
Langrange 다항식의 문제점은 점을 추가하면 겉보기에 임의적인 곡선 부분에 극단적인 영향을 미칠 수 있다는 것입니다.위에서 설명한 것과 같은 "지역성"은 없습니다.
유닉스를 보셨나요? 운형자 명령?당신이 원하는 것을 강제로 할 수 있습니까?
임의의(그러나 최종) 점 집합 사이를 보간(및 외삽)하기 위한 여러 알고리즘이 있습니다.꼭 확인해 보세요 수치 레시피, 해당 알고리즘의 C++ 구현도 포함됩니다.
불행하게도 라그랑주나 다른 형태의 다항식 보간법은 임의의 점 집합에서는 작동하지 않습니다.예를 들어 한 차원에 있는 세트에서만 작동합니다.엑스
엑스나 <x나+1
임의의 점 집합의 경우, 예를 들어각 점이 (경도, 위도) 쌍인 비행기 비행 경로의 경우 현재 경도, 위도 및 속도를 사용하여 비행기의 여행을 모델링하는 것이 더 나을 것입니다.비행기가 다음 웨이포인트에 얼마나 가까운지에 따라 비행기가 회전할 수 있는 속도(각속도)를 조정하면 부드러운 곡선을 얻을 수 있습니다.
결과 곡선은 수학적으로 중요하지 않으며 베지어 제어점도 제공하지 않습니다.그러나 알고리즘은 경유지 수에 관계없이 계산적으로 간단하며 임의의 세분성으로 보간된 지점 목록을 생성할 수 있습니다.또한 전체 포인트 세트를 미리 제공할 필요가 없으며 필요에 따라 세트 끝에 웨이포인트를 추가하기만 하면 됩니다.
나는 같은 문제를 생각해 내고 며칠 전에 친구들과 함께 구현했습니다.저는 github에서 예제 프로젝트를 공유하고 싶습니다.
https://github.com/johnjohndoe/PathInterpolation
자유롭게 포크해 보세요.
구글 "직교 회귀".
최소 제곱 기법은 적합선과 각 f(x) 사이의 수직 거리를 최소화하려고 시도하는 반면, 직교 회귀는 수직 거리를 최소화합니다.
부록
시끄러운 데이터가 있는 상황에서 존경할 만한 랜삭 알고리즘도 확인해 볼 가치가 있습니다.
3D 그래픽 세계에서는 NURBS가 인기가 있습니다.자세한 내용은 구글링하시면 쉽게 찾아보실 수 있습니다.
