내부에 몇 개의 점이있는 2D 평면 (정사각형)이 있다고 가정 해보십시오.토폴로지, 스케일링
가능한 한 고르게 비행기를 채우는 방법으로 모든 점을 이동하는 방법은 어떻게 되나 모든 점은 이웃을 유지합니까?
다른 말로 표현하자면 점들이 가능한 한 멀리 떨어져 있기를 원하지만 그 지역 (토폴로지)은 보존되어야하며 사각형 안에 있어야합니다.
즉, 풍부한 점으로 채워진 영역에서 종류를 확대하고 빈 영역을 축소하려고합니다.
PS : 고차원 공간에 대한 일반적인 해결책이 있습니까? 직접적인 해결책이 있는가 아니면 반복적 인 해결책 만 있는가?
좋은 제안은 Lloyd's algorithm입니다. 그러나, 당신이 요구하는 "이웃 보존"속성은 명확하지 않습니다. 무엇을 요구하는지하면 다음과 같은 경우
그러나 : 그래프 V가의 포인트 을 구성 (V, E)
을 감안할 [0,1]^2, E가 세그먼트는, 없이 두 개의 세그먼트 ' 내부 교차 평면 특성을 보존, 가능한 한 균등하게 포인트를 이동 (즉. 우리는 평면 그래프 가지고)
다음 로이드의 알고리즘은 할 것 .
옆 : 일반화는 공간 점이 무엇인가에 대한 용어가 아니지만 점에 대해 요구하는 밀도 (예 : R^n에 대해 Gaussian measure를 원할 수 있습니다).
다음은 가능한 전략에 대한 개요입니다.
점의 원래 세트 P에 사각형의 경계 (최소로는 정사각형의 꼭지점)에서 몇 개의 점을 추가하십시오. 점은 경계에서 균등하게 샘플링되어야하며, 원래 n 점이 있으면 경계에서 샘플링 된 추가 점이 적어도 √ 개 있어야합니다. 이 증분 된 집합을 Q라고 부릅니다.
다음 Q의 Delaunay Triangulation을 수행합니다. 다음 단계에서이 삼각형의 가장자리를 사용합니다.
least squares minimization 이제 가장자리 길이의 제곱의 합을 최소화하는 P (Q-P의 점을 고정 된 상태로 유지)의 점 위치를 찾으려면 least squares minimization을 수행하십시오.
이 최소화 문제는 행렬 표현식을 풀면 해결할 수 있으므로 '직접적인 해결책'입니다.
최소 제곱 문제의 해는 에지의 길이를 동일하게하는 경향이 있습니다. 따라서 작은 모서리가 커지고 커다란 모서리가 작아집니다. 이렇게하면 토폴로지를 보존하면서 포인트를보다 균등하게 분배 할 수 있습니다.
이것은 더 높은 차원으로 쉽게 일반화됩니다.