점을 그리드에서 가장 가까운 점 얻기

Question

나는 1 차원의 거더를 가지고 있습니다. 그 간격은 부동 소수점입니다. 나는 부동 소수점 좌표와 포인트가 있습니다. 가장 가까운 격자 점까지의 거리를 찾아야합니다. 예를 들어
: 가장 가까운 지점이 뒤에 있기 때문에

  0.12 
      | 
      * 
|---------|---------|---------|---------|---------| 
0  0.1  0.2  0.3  0.4  0.5 

결과는 -0.02 될 것이다.
가

   -0.66 
        | 
        * 
|---------|---------|---------|---------|---------| 
-1  -0.8  -0.6  -0.4  -0.2  0 

이었다 그러나 만약 결과 0.06 것이다. 당신은 부동 소수점에서 볼 수 있듯이 음수 일 수 있습니다.
나는 시도 다음

float spacing = ...; 
float point = ...; 

while(point >= spacing) point -= spacing; 
while(point < 0) point += spacing; 

if(std::abs(point - spacing) < point) point -= spacing; 

그것은 작동하지만 당신은 단지 숫자의 둘레에이 사용한다

Answer 1

우리가 먼저 왼쪽에 가까운 점수를 계산하자 권리로는 다음과 같습니다

if ((point - leftBorder) < (rightBorder - point)) 
    distance = leftBorder - point; 
else 
    distance = rightBorder - point; 

주

것은 우리가 가장 가까운 찾을 수 있다는 :

가

leftBorder = spacing * floor(point/spacing); 
rightBorder = leftBorder + spacing; 

그리고 거리가 간단합니다 천장 단위로 점을 번갈아 표시 :

rightBorder = spacing * ceil(point/spacing); 
leftBorder = rightBorder - spacing; 

Answer 2

루프없는 방법이 확신 :

float spacing = ...; 
float point = ...; 
(point > 0.0) ? floor(point + spacing/2) : ceil(point - spacing/2); 

Answer 3

std::vector<float> spacing = ...; 
float point = ...; 
float result; 

을

간격이 (선형)이 아니므로 합계를 캐쉬합니다.

std::vector<float> sums(1, 0.0); 
float sum=0; 
for(int i=0; i<spacing.size(); ++i) 
    sums.push_back(sum+=spacing[i]); 
//This only needs doing once. 
//sums needs to be in increasing order. 

그런 다음 왼쪽에있는 지점을 찾기 위해 이진 검색을 수행

std::vector<float>::iterator iter; 
iter = std::lower_bound(sums.begin(), sums.end(), point); 

그런 다음 거기에서 결과를 찾을 수 :

이

if (iter+1 == sums.end()) 
    return point-*iter; 
else { 
    float midpoint = (*iter + *(iter+1))/2; 
    if (point < midpoint) 
     result = point - *iter; 
    else 
     result = *(iter+1) - point; 
} 

[편집]을 내가 바보 생각하지 마십시오. 간격은 일정하지 않다고 했지요. 나는 그것을 비선형이라고 해석했다. 그런데 샘플 코드 은 컴파일 시간 상수가 아닌 선형입니다. 내 잘못이야. 나는 당신의 (선형적인) 질문이 훨씬 더 빨리 풀릴지라도이 답을 좀 더 일반적인 해결책으로 남겨 둘 것이다.

Answer 4

첫 번째 홍당무 시도가 있습니다.이 테스트는 전혀 수행되지 않았습니다.

float remainder = fmod(point, spacing); // This is the fractional difference of the spaces 
int num_spaces = point/spacing; // This is the number of "spaces" down you are, rounded down 


// If our fractional part is greater than half of the space length, increase the number of spaces. 
// Not sure what you want to do when the point is equidistant to both grid points 
if(remainder > .5 * spacing) 
{ 
    ++num_spaces; 
} 

float closest_value = num_spaces*spacing; 
float distance = closest_value - point; 

Answer 5

훨씬 더 일반적으로 임의의 간격, 치수 및 거리 측정 (미터법)에 대해 찾고있는 구조는 보로 노이 다이어그램이됩니다.