0

Estoy trabajando en una app de deliveries, y quiero agrupar a los clientes en zonas geográficas, ya que debo de mostrar en la app del repartidor solo los pedidos cercanos.

Lo que se esta haciendo actualmente es recorrer todos los clientes en la base de dato, calcular la distancia con respecto al repartidor según sus coordenadas geográficas.

Se que existen algoritmos que hacen tal cosa, se que Uber divide el mapa en hexágonos. pero no he conseguido el nombre del algoritmo o de algún otro que haga algo similar.

1 respuesta 1

0

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);
};
5
  • Muchas gracias por responder. Pero en cierta forma es lo que ya se hace y el problema es que tiene un costo computacional muy elevado. Lo que necesito es dividir el globo terráqueo en zonas con un radio conocido. y asignar en la base de datos tanto de los clientes como la de los repartidores el identificador de la zona junto con las coordenadas geográficas. Esto con la intención de limitar la cantidad de registros al cual se tendrá que recorrer con la intención de hacer el calculo de la distancia. Commented el 14 jul. 2020 a las 3:28
  • La triangulación por hexágonos deseas que sea radial? es decir, los hexagonos son una grilla estática cuyos limites son estáticos y el cálculo de la ubicación no es función del mensajero --donde el mensajero es el centro de su propio universo- sino donde las grillas determinan determinan los centros de los univeros. esoy mal? estoy desempolvando. es cierto el costo más elevado porque debes recalcular radios. Commented el 14 jul. 2020 a las 13:17
  • Está inglés espero que no sea un problema. www-cs-students.stanford.edu/~amitp/Articles/Hexagon1.html Commented el 14 jul. 2020 a las 13:18
  • La idea es usar 6 triángulos equilateros y "triangular". Commented el 14 jul. 2020 a las 13:19
  • Debes tener un Singleton de todas las grillas: Verificar en que celda estás ( con angulación sin(x) o cos(x) ) y luego estimar moviento por hexágonos si vas a salir de la celda. Commented el 14 jul. 2020 a las 13:28

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.