SoloCodigo

CLR: .Net / Mono / Boo / Otros CLR => C# => Mensaje iniciado por: sergiohj en Jueves 25 de Febrero de 2010, 11:14

Título: Camino entre dos coordenadas
Publicado por: sergiohj en Jueves 25 de Febrero de 2010, 11:14

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.

Título: Re: Camino entre dos coordenadas
Publicado por: eltruhanero en Viernes 26 de Febrero de 2010, 02:15

a ver algunas preguntas...

si queres ir de ( x=0 y=0 ) a ( x=1 y=1 ) podes realizar ese movimiento de una en diagonal, o tenes que moverte primero ( x=0, y=1 ) y desp ( x=1, y=1)??

Se entiende mi pregunta? o sea puedo hacer movimientos en diagonal?

Si no puedo hacer movimientos en diagonal => el largo del camino x=0y=0 yendo por el camino que "mejor se aproxima a uno diagonal" es el mismo que ir por un camino L

O sea

........_
...._ |
_.|

recorres 3 "_" y un "|" que es lo mismo que


.......|
.......|
_ _ _ |

saludos y cualquier cosa re-planteate.
saludos, daniel.

Título: Re: Camino entre dos coordenadas
Publicado por: droezva en Viernes 26 de Febrero de 2010, 07:50

Hola, pues bueno aqui te dejo la solución que encontre, la verdad no soy muy bueno en las cuestiones de matematicas y trigonometria pero es lo que mas o menos se, y por otra parte pues en C# no he programado realmente mucho nada mas lo que he leido.
Pero lo he implementedo en java espero te sirva y de todos modos tambien lo escribi en C#(no es seguro que funcione ya que no tengo como compilarlo  :D)
Supongo que necesitas algo asi :
las / es la linea recta que une los dos puntos y los * son los puntos(x,y) que vas a calcular a distancias en incremento de 2.
Y
|.............. *(10,6)
|............/
|........../*(x1,y1) distancia 4                
|.. 8.54 /
|......../*(x1,y1) distancia 2
|......./
| ..... *(2,3)
|
--------------------------------------- X

Código: Java

1.  
2. import java.text.DecimalFormat;
3.  
4. public class Main {
5.     public static void main(String[] args) {
6.         DecimalFormat formato = new DecimalFormat("####.##"); // Formato de salida de dos decimales
7.         double x1, x2, y1, y2, hipo, nuevaX, nuevaY, tan, nuevaDistancia ;
8.         final double DISTANCIA_INC = 2;
9.         int j = 1;
10.         x1 = 2; y1 = 3;  //Coordenadas del 1er punto
11.         x2 = 10; y2 = 6;  //Coordenadas del 2do punto
12.         hipo =  Math.sqrt(Math.pow(x2-x1,2)+Math.pow(y2-y1,2));  //Calculo la distancia entre los dos puntos = hipotenusa
13.         tan = Math.atan((y2-y1)/(x2-x1)); // Radianes del Angulo Opuesto
14.  
15.         System.out.println("Punto Inicial-> x: " + x1 + " , y: " + y1);
16.         System.out.println("Punto Final-> x: " + x2 + ", y: " + y2 );
17.         System.out.println("Distancia entro los Puntos: " + hipo );
18.         System.out.println("Coordenas de (X,Y) de los puntos intermedios");
19.         System.out.println("por la recta de los dos puntos desplanzandose cada " + DISTANCIA_INC + " unidades");
20.         System.out.println("");
21.         // La nuevaDistancia se ira incrementando en 2 unidades, simulando la construcción de un triangulo con una
22.         // hipotenusa de 2, 4, 6 hasta < a la distancia entre los dos puntos.
23.         for(nuevaDistancia = 0; nuevaDistancia < hipo; nuevaDistancia+=DISTANCIA_INC)
24.         {
25.                 nuevaY = Math.sin(tan) * nuevaDistancia + y1; // Calculo de la Y a la nuevaDistancia
26.                 nuevaX = Math.cos(tan) * nuevaDistancia + x1; // Calculo de la X a la nuevaDistancia
27.                 // Asi obtenemos la nueva cordenada que pasa por la recta entre los dos punto
28.                 System.out.println("(" + j++ + ")"+" Distancia: " + nuevaDistancia + " | X: " + formato.format(nuevaX) + " | Y: " + formato.format(nuevaY));
29.         }
30.         //El ultimo punto lo mostramos directo
31.         System.out.println("(f) Distancia: " + hipo + " | X: " + x2 + " | Y: " +  y2);
32.     }
33. }
34.  
35.  

Salida del programa de JAVA:

Código: Text

1.  
2. Punto Inicial-> x: 2.0 , y: 3.0
3. Punto Final-> x: 10.0, y: 6.0
4. Distancia entro los Puntos: 8.54400374531753
5. Coordenas de (X,Y) de los puntos intermedios
6. por la recta de los dos puntos desplanzandose cada 2.0 unidades
7.  
8. (1) Distancia: 0.0 | X: 2 | Y: 3
9. (2) Distancia: 2.0 | X: 3.87 | Y: 3.7
10. (3) Distancia: 4.0 | X: 5.75 | Y: 4.4
11. (4) Distancia: 6.0 | X: 7.62 | Y: 5.11
12. (5) Distancia: 8.0 | X: 9.49 | Y: 5.81
13. (f) Distancia: 8.54400374531753 | X: 10.0 | Y: 6.0
14.  
15.  

y en C# tal vez tenga errores es que no tengo para probarlo!!

Código: C#

1.  
2.  class calcular
3. {
4.     public static main()
5.     {
6.         float x1, x2, y1, y2, hipo, nuevaX, nuevaY, tan, nuevaDistancia ;
7.         const float DISTANCIA_INC = 2;
8.            
9.         x1 = 2; y1 = 3;
10.         x2 = 10; y2 = 6;
11.         hipo = Math.Sqrt(Math.Pow(x2-x1,2)+Math.Pow(y2-y1,2));
12.  
13.         tan = Math.atan((y2-y1)/(x2-x1));
14.        
15.         Console.WriteLine("Punto Inicial-> x: {0}, y: {1}", x1, y1);
16.         Console.WriteLine("Punto Final-> x: {0}, y: {1}", x2, y2);
17.  
18.         Console.WriteLine("Coordenas de (X,Y) de los puntos intermedios");
19.         Console.WriteLine("por la recta de los dos puntos desplanzandose cada {0} unidades", DISTANCIA_INC);
20.        
21.         Console.WriteLine("");
22.         Console.WriteLine("Distancia: 0 | X: {0} | Y: {1}", x1, y1);
23.         for(nuevaDistancia = 0; nuevaDistancia < hipo; nuevaDistancia+=DISTANCIA_INC)
24.         {
25.             nuevaY = Math.sen(tan) * nuevaDistancia + y1;
26.             nuevaX = Math.cos(tan) * nuevaDistancia + x1;
27.             Console.WriteLine("Distancia: {0} | X: {1} | Y: {2}", i, nuevaX, nuevaY);
28.         }
29.         Console.WriteLine("Distancia: {0} | X: {1} | Y: {2}", hipo, x2, y2);
30.     }
31. }
32.  
33.  

Pero Bueno Espero que te  ayude y sirva para resolver el problema; en C# no lo he compilado no tengo con que, lo hice en Bloc de nota guiandome del que hice en JAVA con lo que he leido en C#.

Título: Re: Camino entre dos coordenadas
Publicado por: sergiohj en Viernes 26 de Febrero de 2010, 09:43

Hola,

muchas gracias a todos por la respuesta. El tema está en que no tengo posiciones decimales por lo que al final he utilizado el algoritmo de Bresenham puesto que tiene la ventaja de que opera con número enteros.

Os dejo el código para el que le sirva:


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;      

        }

    }