SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: sergiohj en Jueves 25 de Febrero de 2010, 11:18
-
Hola,
estoy desarrollando una aplicación que necesita calcular el camino que debería de recorrerse entre dos puntos y saber los puntos por los que voy pasando. Por ejemplo, imaginar que me encuentro en la posicion x=2 e Y=3 y mi objetivo es x=10 e y=6. Yo sé calcular la distancia entre estos dos puntos que sería de 8,54 unidades. Pues bien, mi problema viene al calcular el camino a seguir puesto que yo sólo puedo moverme 2 metros de mi posición cada vez. Por lo tanto, se que necesito 5 movimientos para llegar pero no sé como calcular los puntos intermedios por los que paso de la recta que une ambos puntos, que es el camino más corto. ¿Alguna idea o sugerencia para calcular dicho camino en coordenadas que se debe seguir para llegar al destino?
Gracias y un saludo.
-
Hay varios algoritmos que lo resuelve...
El algoritmo de Bresenham tiene la ventaja de que opera con número enteros.
http://en.wikipedia.org/wiki/Bresenham% ... _algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm" onclick="window.open(this.href);return false;) (en inglés)
-
Muchas gracias,
ya lo tengo más o menos desarrollado aunque tengo que hacer pruebas puesto que he tenido que hacer cambios al algoritmo:
class Program
{
static void Main(string[] args)
{
int xOrigen,yOrigen,xDestino,yDestino,metros;
xOrigen=80;
yOrigen =10;
xDestino=34;
yDestino =23;
metros=5;
while ((xOrigen != xDestino)||(yOrigen!=yDestino))
{
Console.WriteLine("X: " + xOrigen + "Y: " + yOrigen);
SiguientePosicion(xOrigen,yOrigen,xDestino,yDestino, metros, out xOrigen, out yOrigen);
}
Console.ReadLine();
}
static void SiguientePosicion(int x0, int y0, int x1, int y1, int metros, out int x, out int y)
{
int deltax = x1 - x0;
int deltay = Math.Abs(y1 - y0);
int error = deltax / 2;
int ystep, xstep,xdirection;
y = y0;
if (x0 < x1)
{
xdirection = 1;
}
else
{
xdirection = -1;
}
x = x0;
ystep = 0;
xstep = 0;
error = error - deltay;
if (error < 0)
{
if (y < y1)
{
if (Math.Abs(x - x1) > metros)
{
if (Math.Abs(y - y1) < metros / 2)
{
ystep = Math.Abs(y - y1);
}
else
{
ystep = metros / 2;
}
}
else
{
if (Math.Abs(y - y1) < metros)
{
ystep = Math.Abs(y - y1);
}
else
{
ystep = metros -(Math.Abs(x-x1));
}
}
}
else if (y > y1)
{
if (Math.Abs(x - x1) > metros)
{
if (Math.Abs(y - y1) < metros / 2)
{
ystep = -1*Math.Abs(y - y1);
}
else
{
ystep = -1*metros / 2;
}
}
else
{
if (Math.Abs(y - y1) < metros)
{
ystep = -1*Math.Abs(y - y1);
}
else
{
ystep = -1*metros - (Math.Abs(x - x1));
}
}
}
else
{
ystep = 0;
}
y = y + ystep;
if (Math.Abs(x - x1) < metros - Math.Abs(ystep))
{
xstep = Math.Abs(x - x1) * xdirection;
}
else
{
xstep = ((metros - Math.Abs(ystep)) * xdirection);
}
x = x+xstep;
error = error + deltax;
}
else
{
if (Math.Abs(x - x1) < metros - Math.Abs(ystep))
{
xstep = Math.Abs(x - x1) * xdirection;
}
else
{
xstep = ((metros - Math.Abs(ystep)) * xdirection);
}
x = x + xstep;
}
}
static void swap(out int x1, out int y1, int x2, int y2)
{
x1=y2;
y1=x2;
}
}
Un saludo.
-
En otro momento reviso tu algoritmo....
...y de paso te pondré las incrementos para cada octante...