2D 보간 알고리즘

Question

채널의 단면 인 두 가지 모양이 있습니다. 두 개의 정의 된 점 사이의 중간 점의 횡단면을 계산하고 싶습니다. 이 상황에서 사용하는 가장 단순한 알고리즘은 무엇입니까?

추신 : 복잡한 자연스러운 이웃과 포아송과 같은 여러 알고리즘을 발견했습니다. 신속하게 구현할 수있는 간단한 솔루션을 찾고 있습니다.

편집 : 그것은 오해의 소지가 될 수 있기 때문에 나는 제목에서 단어 "간단한"를 제거

Answer 1

이 간단하다의 경계를 따라 균등하게 간격으로 N 점을 그릴

1. 각 단면에 횡단면.
2. 횡단면 1의 n 번째 점에서 횡단면 2의 n 번째 점까지 직선을 그립니다.
3. 횡단면 사이의 원하는 거리에서 새 횡단면을 제거하십시오. 여전히

간단한 : 수정없이 기존 단면의

1. 하나를 사용합니다.

이 두 번째 제안은 너무 단순 할 수도 있지만, 아무도 간단하지 않다고 생각합니다. 영업 이익의 코멘트 다음

편집 : (재 코멘트를 너무 많이)

글쎄, 당신은 간단한 방법을 문의 않았다! 나는 당신이하는 것처럼 첫 번째 방법으로 같은 문제가 생겼는지 확신 할 수 없다. 횡단면이 너무 이상하지 않은 경우 (아마도 볼록 다각형 인 경우 가장 좋음) 하나의 횡단면의 왼쪽을 다른면의 오른쪽으로 매핑하는 등의 이상한 작업을 수행하지 않아야합니다 (이로 인해 많은 교차 선)이 방법은 어떤 종류의 합리적인 횡단면을 만들어야합니다. 삼각형과 직사각형을 제안하는 경우 삼각형이 그 꼭대기에있는 꼭지점 하나에 앉아 있다고 가정합니다. 지도는 직사각형의 왼쪽 상단을 가리킨 다음 해당 지점을 결합하는 두 단면의 경계를 따라 같은 방향 (시계 방향 또는 반 시계 방향)으로 진행합니다. 교차 선이 보이지 않고 두 횡단면 사이의 어떤 거리에서도 잘 정의 된 모양을 볼 수 있습니다.

Answer 2

메모 성능 메트릭의 해결 방법에 대한 모호한 점이 있지만 해결 방법의 출력 품질을 정의 할 것입니다. 가장 중요한 점은 양쪽 횡단면 모두에 n 점을 그릴 때 어떤 종류의 서신인지를 결정합니다. 즉, 고성능 마크가 제안한 방식으로 수행하면 점수를 지정하는 순서가 중요 해집니다 .

두 단면을 동시에 회전 (직교)하는 평면을 제안한 다음 한 단면의 평면과 교차하는 점의 집합은 다른 단면의 평면과 교차하는 점의 집합에 일치시켜야합니다. 가설 적으로,이 세트의 포인트 수에는 제한이 없지만 원래 상황에서 통신 문제의 복잡성을 확실히 줄일 수 있습니다.

Answer 3

다음은이 문제에 대한 또 다른 시도입니다. 더 나은 시도라고 생각합니다.두 단면 C_1 감안

, C_2

장소가 비교적 놓인다 방법 말이되도록 (x,y) 좌표 시스템과 글로벌 기준 프레임에 각각 C_i에게. 각 C_i을 위아래 곡선 U_i 및 L_i으로 분할하십시오. 이 아이디어는 곡선 U_1을 U_2과 L_1에서 L_2으로 연속적으로 변형하려고 할 것이라는 아이디어가 될 것입니다. (원하는 경우이 방법을 확장하여 각 C_i을 m 곡선으로 분할 할 수 있습니다.)

이렇게하는 방법은 다음과 같습니다. 각각 T_i = U_i, or L_i 샘플 n 점에 대해, 그리고 interpolating 다항식 P{T_i}(x)을 결정하십시오. 아래에 적지 않게 언급 된 것처럼, 다항식을 보간하는 것은 끝점에서 특히 진동하기 쉽습니다. 보간 다항식 대신에, 대신에 훨씬 더 강건한 최소 제곱 적합 다항식을 사용할 수 있습니다. 그런 다음 변형이 t=0 우리가 U_2에 있습니다에서 (예에서 어떤 지점에서 변형 Q이 t가 정의 0<=t<=1을 통해 정의된다 Q{P{U_1},P{U_2}}(x, t) = (t * a_0 + (1 - t) b_0) + ... + (t * a_n + (1-t) * b_n) * x^n로 P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^n에 다항식 P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n의 변형을 정의하고 t=1에서 우리는 U_1에서와 t 다른 모든에있다 우리는 두 가지의 지속적인 변형이 있습니다.) 정확도는 Q{P{L_1},P{L_2}}(x, t)입니다. 이 두 가지 변형은 어떤 t에서 샘플링 할 수있는 두 횡단면 간의 연속적인 표현을 구성합니다.

사실이 모든 작업은 두 단면의 보간 다항식의 계수를 선형 보간법으로 수행합니다. 횡단면을 분할 할 때, 종단점에서 나누어야하는 구속 조건을 설정해야합니다. 그렇지 않으면 변형에 "구멍"이 생길 수 있습니다.

나는 그것이 분명히 희망적이다.

편집 : 보간 다항식의 발진 문제 해결.