El vecino más cercano | Nearest neighbor search
Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/15-nearest-neighbor-2d
Supongamos que queremos saber cual es el cajero automático (ATM) más cercano a varias tiendas de maquinaria que visitaremos, pues debemos alquilar un equipo con dinero en efectivo pero no queremos cargar con el por toda la ciudad hasta estar seguros de que el equipo esté disponible, en buenas condiciones y al mejor precio, por lo que una vez que encontremos la opción ideal deberemos disponer del efectivo recorriendo la menor distancia posible.
As a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. En forma de búsqueda de proximidad, es el problema de optimización de encontrar el elemento dentro de la lista que más cercano (o similar) sea con respecto de un punto dado. https://en.wikipedia.org/wiki/Nearest_neighbor_search
Una forma de obtenerlo consiste en calcular de manera lineal la distancia entre el punto dado y cada punto de la lista hasta obtener la distancia menor.
Esta distancia se calcula utilizando el super-poder conocido como Teorema de Pitágoras que en este caso tomará destino.x-origen.x y destino.y-origen.y como catetos.
Ejemplo
Del siguiente mapa calcularemos la distancia entre x y los puntos más cercanos, que son a, b y c para determinar cual es el más cercano.
Distancia x→c
cx = 24
cy = 8
xx = 18
xy = 7
dX = cx - xx = 24 - 18 = **6**
dY = cy - xy = 8 - 7 = **1**
distXC = **sqr((**dX*****dX**)+(**dY*****dY**))
**distXC = **sqr(**36**+**1**)** = **sqr(**37**)** = **6.082**
Distancia x→b
bx = 25
by = 6
xx = 18
xy = 7
dX = bx - xx = 25 - 18 = **7**
dY = by - xy = 6 - 7 = **-1**
distXB = **sqr((**dX*****dX**)+(**dY*****dY**))
**distXB = **sqr(**49+1**)** = **sqr(**50**)** = **7.071**
Distancia x→a
ax = 12
ay = 5
xx = 18
xy = 7
dX = ax - xx = 12 - 18 = **-6**
dY = ay - xy = 5 - 7 = **-2**
distXA = **sqr((**dX*****dX**)+(**dY*****dY**))
**distXA = **sqr(**36**+**4**)** = **sqr(**40**)** = **6.324**
Finalmente, con estos resultados determinamos que el punto más cercano a x es c.
Implementación en Go
Para este programa generaremos dos grupos de elementos en posiciones aleatorias: animales y comida, después buscaremos la comida más cercana a cada animal y trazaremos una línea del animal a la comida.
Puede darse el caso en que la comida esté muy cerca del animal, o incluso que el animal esté directamente sobre la comida, en este caso la línea no será visible del todo.
