Obteniendo el punto más cercano en la cuadrícula al punto

Question

Tengo un ceñidor unidimensional. su espacio es un punto flotante. También tengo un punto con coordenadas de coma flotante. Necesito encontrar su distancia al punto de cuadrícula más cercano.
Por ejemplo:

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

El resultado sería -0.02 desde el punto más cercano está detrás de él.
Sin embargo si era

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

El resultado será 0.06. Como puedes ver está en coma flotante y puede ser negativo.
He intentado lo siguiente:

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

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

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

Funciona, pero estoy seguro de que hay una manera sin bucles

Answer 1

Primero vamos a calcular los puntos más cercanos a la izquierda y derecha de la siguiente manera:

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

A continuación, la distancia es sencillo:

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

Tenga en cuenta que, no pudimos encontrar la más cercana puntos alternativamente por techo:

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

Answer 2

Usted debe a la vuelta el número con esto:

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; 

Dado que dice que el espaciado no es (lineal), almacenaría en caché las sumas:

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. 

Después, realice una búsqueda binaria para encontrar el punto a la izquierda:

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

A continuación, busque el resultado de allí:

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; 
} 

[EDIT] No me siento tonta. Dijiste que el espacio no era constante. Lo interpreté como no lineal. Pero entonces su código de muestra es lineal, simplemente no es una constante de tiempo de compilación. Mi error. Dejaré esta respuesta como una solución más general, aunque su pregunta (lineal) se puede resolver mucho más rápido.

Answer 4

Este es mi primer intento de blush, tenga en cuenta que esto no se ha probado en absoluto.

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

Mucho, mucho más generalmente, para espacios arbitrarios, dimensiones y medidas de distancia (métricas), la estructura que está buscando sería un diagrama de Voronoi.