Método básico # 1: Pitágoras.
Pros: fácil de implementar.
Contra: No tiene en cuenta los sentidos de las calles.
Hace algún tiempo me tocó resolver un problema logístico y la solución usando un modelo matemático que no incluía sentido de las vías era distancias radiales.
Una forma muy básica de conocer la cercanía es usar el radio, dado que las cordenadas se expresan en un duo ( x,y ) puedes realizar algo así como:
Este el flujograma en pseudo código.
Definiciones:
Ubicación del mensajero se define como el par (x,y).
Cliente(n) es la definición de cada instancia del objeto cliente.
Ubicación inicial del n-simo cliente se define como el par (xn0,yn0).
Ubicación destino del n-simo cliente se define como el par (xn1,yn1).
En un array vas a calcular la distancia de todos los clientes:
Paso 1. Calcular la distancia de todos los clientes.
Var Distancias = []
Var i = 0
ForEach var cliente in clientes
Distancias[i] = ( (x - xn0)^2 + (y - yn0)^2 )^(1/2)
i = i + 1
Next
En este Punto Distancias contiene el listado de distancias radiales a cualquier ubicación, es un criterio poco inteligente, pero matemáticamente válido.
var cliente = BuscarmenorDistancia( Distancias[i] )
Este método busca la menor distancia y guarda el item. lo más óptimo es hacerlo en el primer recorrido, pero esto solo es una ilustración.
Finalmente se debe determinar si existe un criterio o peso que determine si el mensajero puede tomar el servicio, en este caso hay mensajeros que pueden recorrer hast x kilometors o X pasajeros o X tomeladas de peso; por ejemplo:
if ( CriterioDeDistancia(vendedor , distancia_del_pedido ) ) then
else
end if
Método 2: Cordenadas Hexagonales
TOMADO DE: http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon1.html
LOS CRÉDITOS SON PARA:
http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon1.html
Author: Paul J. Gyugyi
Referencias:
https://www.redblobgames.com/grids/hexagons/#pixel-to-hex
usage: J = floor(x);
int floor(x)
{ if x >= 0
then return int(x);
else return int(x - 1 + 1E-10);
endif;
};
Where I added the 1E-10 to make float(-3.0) = -3. If you make
this number too small, you won't have enough digits of precision
to make it matter.
III.2 (x,y) to <H,E,X> routines
usage: H = get_H(_xcoord, _ycoord)
int get_H(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( 2.0 * y);
}
int get_E(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( sqrt(3.0) * _xcoord - _ycoord);
}
int get_X(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( sqrt(3.0) * _xcoord + _ycoord);
}
III.3 (x,y) to hexnumber, using above routines
usage: hexnum = getHex( _xcoord, _ycoord);
where hexnum is a 4 digit decimal number, such as 0101 or 2013,
corresponding to the hex map numbering.
int getHex(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
int t,n,ox,oy,h,e,x;
h = get_H(_xcoord, _ycoord);
e = get_E(_xcoord, _ycoord);
x = get_X(_xcoord, _ycoord);
/* t will be the E value of the <base> triangle */
t := e + h - x + ((((x-2*h) mod 3)+3) mod 3);
/* <hex> = <base> + n*<0,3,3> + get_H()*<1,1,2> */
n := floor( (x - 2*h - ((((x-2*h) mod 3)+3) mod 3))/3.0 );
if (t > 0) then
ox = 2 + 2 * n + h;
oy = 1 + floor( ((float)(h-1))/2.0);
else
ox = 1 + 2 * n + h;
oy = 1 + floor( ((float)(h))/2.0 );
endif;
^( 100 * ox + oy);
}
IV. Getting (x,y) from hexnumber
This routine is much easier, since we only need to return the
well-defined center point of the hex.
usage: x = HexToX(hexnumber); y = HexToY(hexnumber);
float HexToX(h)
int h;
{ int tx;
tx = (int) (h/100);
return ( 1/(2*sqrt(3)) + (tx-1)*(sqrt(3)/2));
};
float HexToY(h)
int h;
{ int ty;
int tx;
tx = (int) (h/100);
ty = h mod 100;
return ( ty - 0.5*(tx mod 2);
}
V. Hex counting for range:
This counts the true distance in hexes between two hexnumbers.
usage: range = getRange( h1, h2);
for example, getRange( 0101, 0602) equals 5
See below for getAngle() and nextHex() routines.
/* counts the hexes from here to target. */
int getRange(thisHex, targetHex)
int thisHex, targetHex;
{ int dist, theta; /* theta is an angle in degrees */
int tempHex;
float x,y;
dist=0;
tempHex = thisHex;
while (tempHex <> targetHex)
{
/* limit theta to multiples of 60 degrees */
th:=asInt(getAngle(tempHex, targetHex))/60 * 60 +30;
tempHex = nextHex(tempHex, theta);;
dist=dist+1;
};
return dist;
}
/* returns angle from thisHex to targetHex.
* getAngle(0102,0201) returns +30 deg.
* getAngle(0102,0101) returns +90 deg.
* getAngle(0102,0202) returns +330 deg.
*/
int getAngle(thisHex, targetHex)
int thisHex, targetHex;
{
float t,dx,dy;
dx:= HexToX(targetHex)-HexToX(thisHex);
dy:= HexToY(thisHex)-HexToY(targetHex);
/* flipped because board is upside down. I guess I should change
the code to use the down-is-positive, but then my angles would be
wrong. */
if (dx=0)
{
if dy>=0
{
return 90;
} else {
return 270;
};
} else {
t=radToDeg(arcTan(dy/dx));
if t >= 0
{
if dx>0
then return (int)(t+0.5); /* there are better methods */
/* of rounding, but this */
/* works fine. */
else return (int)(t+0.5+180);
endif;
} else {
if dx>0
{ return (int)(t+360+0.5);
} else {
return (int)(180+t+0.5);
};
};
};
}
/* Returns neighboring hex at the given angle */
Def nextHex(thisHex, theta)
int thisHex;
float(theta);
{
float nx,ny;
nx = HexToX(thisHex) + cos(degToRad(theta));
ny = HexToY(thisHex) - sin(degToRad(theta));
return getHex(nx,ny);
};