TODOPIC

Microcontroladores PIC => Lenguaje C para microcontroladores PIC => Mensaje iniciado por: jgpeiro06 en 20 de Abril de 2009, 06:45:28

Título: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 20 de Abril de 2009, 06:45:28
Hola a todos!

Se me ha ocurrido plantear un concurso o reto a todos los programadores de todopic.
El concursante debe implementar una función que determine si un punto esta dentro o fuera de un polígono. Se da la función main, 4 polígonos y 5 puntos a testear.
Existen muchas soluciones a este problema, pero el objetivo es que cada uno proponga su algoritmo propio.
Cualquier duda se puede colgar en el hilo, y la solución se debe adjuntar en un archivo con la misma estructura que el original para que otros usuarios lo puedan probar cómodamente.

¿Premio? El ganador recibirá una INCREÍBLE, FANTÁSTICA e INOLVIDABLE postal de www.postales.com ...jeje

El código original:
Código: C
  1. #include        <stdlib.h>
  2. #include        <stdio.h>
  3. #include        <math.h>
  4.  
  5.  
  6. #define FUERA   0
  7. #define DENTRO  1
  8. #define POLIGONOS_TEST_MAX      4
  9. #define PUNTOS_TEST_MAX         5
  10. #define LINEAS_POR_POLIGONO     12
  11.  
  12.  
  13. typedef struct{
  14.         float X;
  15.         float Y;
  16. }Punto;
  17.  
  18. typedef struct{
  19.         Punto P0, P1;
  20. }Linea;
  21.  
  22. typedef struct{
  23.         char nombre[5];
  24.         int size;
  25.         Linea lineas[LINEAS_POR_POLIGONO];
  26. }Poligono;
  27.  
  28. const Poligono poligonos_test[POLIGONOS_TEST_MAX] = {
  29.                         {"Tria", 3, {
  30.                                         {{0,0},{3,7}}, {{3,7},{6,0}}, {{6,0},{0,0}}, {{0,0},{0,0}},
  31.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
  32.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
  33.                                 }
  34.                         },
  35.                         {"Rect", 4, {
  36.                                         {{0,0},{0,7}}, {{0,7},{7,7}}, {{7,7},{7,0}}, {{7,0},{0,0}},
  37.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}},
  38.                                         {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}, {{0,0},{0,0}}
  39.                                 }
  40.                         },
  41.                         {"Letr", 12, {
  42.                                         {{0,0},{0,7}}, {{0,7},{1,7}}, {{1,7},{3,5}}, {{3,5},{5,7}},
  43.                                         {{5,7},{6,7}}, {{6,7},{6,0}}, {{6,0},{5,0}}, {{5,0},{5,5}},
  44.                                         {{5,5},{3,3}}, {{3,3},{1,5}}, {{1,5},{1,0}}, {{1,0},{0,0}}
  45.                                 }
  46.                         },
  47.                         {"Cora", 12, {
  48.                                         {{0,3},{0,5}}, {{0,5},{1,6}}, {{1,6},{2,6}}, {{2,6},{4,4}},
  49.                                         {{4,4},{3,3}}, {{3,3},{2,4}}, {{2,4},{4,6}}, {{4,6},{5,6}},
  50.                                         {{5,6},{6,5}}, {{6,5},{6,3}}, {{6,3},{3,0}}, {{3,0},{0,3}}
  51.                                 }
  52.                         }
  53.         };
  54.  
  55. const Punto puntos_test[PUNTOS_TEST_MAX] = {
  56.                 {0,0}, {3,4}, {2,6}, {3,6}, {4,6}
  57. };
  58.  
  59. int algoritmo( const Poligono plgn, const Punto pnt ){
  60.         int resultado = 0;
  61.  
  62.         //      Implementacion del algoritmo. Resultado = DENTRO/FUERA
  63.  
  64.         return resultado;
  65. }
  66.  
  67. int main(){
  68.  
  69.         int i, j;
  70.  
  71.         printf("www.TODOPIC.com.ar\n");
  72.         printf("Concurso de programacion en C.\n");
  73.         printf("Nombre del concursante: XXXX");
  74.  
  75.         for( i = 0 ; i < POLIGONOS_TEST_MAX ; i++ ){
  76.  
  77.                 printf( "\n\nTest del poligono %s...", poligonos_test[i].nombre );
  78.  
  79.                 for( j = 0 ; j < PUNTOS_TEST_MAX ; j++ ){
  80.  
  81.                         if( DENTRO == algoritmo( poligonos_test[i], puntos_test[j] ) )
  82.                                 printf( "\nEl punto { %2.1f, %2.1f } se encuentra DENTRO", puntos_test[j].X,puntos_test[j].Y );
  83.                         else
  84.                                 printf( "\nEl punto { %2.1f, %2.1f } se encuentra FUERA", puntos_test[j].X,puntos_test[j].Y );
  85.  
  86.                 }
  87.         }
  88.  
  89.         printf("\n\nTest terminado.");
  90.         return 0;
  91. }
  92.  

Las figuras y los puntos a testear.
(http://farm4.static.flickr.com/3535/3459076452_9b7ecfa486.jpg)
Título: Re: Mini-Concurso de programacion
Publicado por: micro_cadaver en 21 de Abril de 2009, 16:22:07
(http://img201.imageshack.us/img201/3769/kiko.jpg)
Título: Re: Mini-Concurso de programacion
Publicado por: x-logan en 21 de Abril de 2009, 20:15:44
Bueno yo me apunto a este miniconcurso, solo tengo unas preguntas/comentarios:
1.- Como vas a determinar quien gana, sera el algoritmo que se tarde menos o el que lo entregue primero o el mejor estructurado o cuales serian los criterios a calificar.
2.- Creo que seria mejor enviar por PM la respuesta y cuando se de por terminado la fecha limite para enviar la respuesta, se evalúan los algoritmos y una vez que se haya determinado un ganador pues ya se cuelgan todos en un post.

Espero tus comentarios.

salu2

Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 22 de Abril de 2009, 04:45:52
Citar
Como vas a determinar quien gana
Gana el primero que implemente un algoritmo que funcione correctamente. Se puede imponer cualquier otro criterio, pero todo depende de cuanta gente participe(por el momento solo tu).
Citar
Creo que seria mejor enviar por PM
No creo que nadie tenga ningún motivo para hacer trampas. Quiero decir, el objetivo del concurso es que la gente se entretenga un poco desarrollando el algoritmo, no ganar la postal de felicitación...Si los concursantes ADJUNTAN la solución en el propio hilo otras personas que no quieran participar pueden consultar los algoritmos.
Título: Re: Mini-Concurso de programacion
Publicado por: Nocturno en 22 de Abril de 2009, 05:43:14
Sí, por favor, publicad los algoritmos a la vista de todos.
Yo no voy a participar porque me resulta imposible sacar tiempo, pero me muerdo las uñas por ver el algoritmo que funcione.
Título: Re: Mini-Concurso de programacion
Publicado por: LoPiTaL en 22 de Abril de 2009, 06:13:51
Yo también me apunto va. Se me ha metido la mosca en la oreja y me pasé toda la noche dándole vueltas... xDD aunque no he llegado a ninguna parte...

Un saludo,
LoPiTaL
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 22 de Abril de 2009, 11:39:56
Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho?  :D
Título: Re: Mini-Concurso de programacion
Publicado por: Nocturno en 22 de Abril de 2009, 12:01:30
Después de ver lo que ha hecho con el reloj Casio mediante FreeRTOS seguro que este algoritmo se lo papea en un rato.
Además, hay muchas versiones del mismo publicadas en Internet, por lo que dudo que se lo hayan puesto como tarea.

Lo divertido realmente es inventarse un método.
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 22 de Abril de 2009, 12:50:03
OOhhh  :mrgreen:

A mi se me ocurre uno pero lo intentaría hasta el fin de semana. ¿Hasta cuándo podemos participar?  8)
Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 22 de Abril de 2009, 14:21:43
Citar
Sí, por favor, publicad los algoritmos a la vista de todos.
Ok. Las posibles soluciones serán enviadas en un archivo adjunto con el formato del main.c original.

Citar
Se me ha metido la mosca en la oreja y me pasé toda la noche dándole vueltas...
Para mi resulto interesante porque es muy fácil determinar que puntos están dentro del polígono echando un simple vistazo. Pero aun siendo tan evidente que puntos están dentro o fuera, uno no sabe nada sobre que ha echo el cerebro para saberlo. Cuando intentas implementar el algoritmo te das cuenta de que es mas complejo de lo que parecía...

Citar
Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho?
Bueno, lo cierto es que no tengo la solución en mano. Me plantearon este reto hace 3 años y estuve unas semanas escribiendo programas hasta que la encontré, pero tengo que reconocer que no se donde estará el código. De todas maneras creo que podría volverlo a implementar.
Desde luego si necesitase este algoritmo lo buscaría en internet antes de inventarme esto como excusa.



Título: Re: Mini-Concurso de programacion
Publicado por: MLO__ en 22 de Abril de 2009, 15:07:47
Sería bueno que jgpeiro publicara el algoritmo que él usó para resolverlo. ¿Qué tal si se lo dejaron de tarea y no lo ha hecho?  :D

Creo que mig estaba chanceando unicamente .... molestando ..... tomando el pelo ...  :D

Esta muy interesante ... pero yo si que soy pesimo para programar, sin embargo estare muy pendiente de las soluciones.
Título: Re: Mini-Concurso de programacion
Publicado por: cerebro en 22 de Abril de 2009, 15:59:19
yo ya tengo una idea que no puede fallar.... aunque me falta tiempo y tengo las neuronas en agua fria, si alguien se me alia le paso un pseudocodigo...
Título: Re: Mini-Concurso de programacion
Publicado por: x-logan en 22 de Abril de 2009, 16:47:08
Gana el primero que implemente un algoritmo que funcione correctamente. Se puede imponer cualquier otro criterio, pero todo depende de cuanta gente participe(por el momento solo tu).

Ok, entonces el primero gana

otras personas que no quieran participar pueden consultar los algoritmos.

claro, habra muchos que no participen y aun asi puedan revisar los algoritmos.

ya lo he estado pensando pero no he tenido tiempo para codificarlo.

salu2
Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 25 de Abril de 2009, 10:44:15
¿como van esos algoritmos?
¿alguien esta intentando resolver el problema?

Si alguno tiene una solución que funciona solo en algunos casos que la publique para darle vida al hilo,¿no?.

Saludos
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 25 de Abril de 2009, 10:45:04
jejeje no te desesperes es un trabajo difícil  :D
Título: Re: Mini-Concurso de programacion
Publicado por: AKENAFAB en 25 de Abril de 2009, 15:13:55

Se ve muy interesante  8)

Aunque se me cierra *   :D

 :(  No creo tener las bases para entrarle


Un saludo!

Por aca los veo!
Título: Re: Mini-Concurso de programacion
Publicado por: RedPic en 25 de Abril de 2009, 18:21:49
Yo lo tenía solucionado en Pascal para una aplicación gráfica que hice hace unos diez años ... voy a ver si logro encontrarlo

Éste es por "barrido", bastante ineficaz pero funciona.
Código: Delphi
  1.  
  2. type tpunto = record x,y:double end;
  3. type tpoligono = array of tpunto;
  4.  
  5. function PointInPoly( p : tpunto; const v : tpoligono ): boolean;
  6. var
  7.   p0,p1:tpunto;
  8.   i: integer;
  9.   UpSide:boolean;
  10. begin
  11.   result:= false;
  12.  
  13.   p1 := v[High(v)];
  14.   UpSide := ( p.y < p1.y );
  15.   for i := 0 to High(v) do begin
  16.     p0 := p1;
  17.     p1 := v[i];
  18.     if (UpSide xor (p.y < p1.y)) then
  19.     begin
  20.       if (p.x < (p0.x - p1.x) * (p.y - p1.y) / (p0.y - p1.y) + p1.x) then result := not result;
  21.       UpSide := not UpSide;
  22.     end;
  23.   end;
  24. end;  
  25.  
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 25 de Abril de 2009, 18:39:47
jeje eso parece VHDL

Redpic, vas a tener que migrarlo a C si quieres ganarte la postal  :D
Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 25 de Abril de 2009, 18:56:37
Código: C
  1. typedef struct{
  2.         double x;
  3.         double y;
  4. }tpunto;
  5.  
  6. typedef struct{
  7.         tpunto array[12];
  8. }tpoligono;
  9.  
  10. int PointInPoly( tpunto p, const tpoligono v ){
  11.  
  12.         tpunto p0, p1,;
  13.         int i;
  14.         int UpSide;
  15.         int result = 0;
  16.  
  17.         p1 = v.array[12];       // High(v)??
  18.         UpSide = ( p.y < p1.y );
  19.  
  20.         for( i = 0 ; i < 12 ; i++ ){    // High(v)??
  21.                 p0 = p1;
  22.                 p1 = v.array[i];
  23.                 if( UpSide ^ ( p.y < p1.y) ){
  24.                         if (p.x < (p0.x - p1.x) * (p.y - p1.y) / (p0.y - p1.y) + p1.x){
  25.                                 result = !result;
  26.                         }
  27.                         UpSide = !UpSide;
  28.  
  29.                 }
  30.         }
  31.         return result;
  32. }
  33.  

En C seria algo así...supongo.
Lo ideal, lo que dice el articulo 6 de el manual oficial de este mini-concurso, es que debes ADJUNTAR tu respuesta en un archivo compatible con el MAIN.C original para que otros usuarios puedan probar el codigo....
Título: Re: Mini-Concurso de programacion
Publicado por: BrunoF en 26 de Abril de 2009, 17:23:00
Hola!

Lo vi anoche al desafío y me pareció interesante. 
Mi algoritmo utiliza una método de solución radial, sumando y restando los ángulos que forma el punto dado con cada vertice.
Si la suma da 2*PI, el punto pertenece;
Si la suma da 0 el punto está fuera del polígono.
Si la suma da cualquier múltiplo de 2*PI(como por ej. 4*PI) significa que el punto TAMPOCO pertenece pero que el polígono lo abraza(como pasa en el caso del punto que se encuentra justo en la panza del corazón).

Adjunto mi solución propuesta.

Captura de los resultados del algoritmo:

(http://img26.imageshack.us/img26/2975/resbrunof.png)


Estaría bueno proponer por ahí un problema en el que sea un poco más fácil y posible usar la lógica y no solo la matemática...
Un saludo.

Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 27 de Abril de 2009, 08:49:08
Bueno, ya tenemos ganador.
Felicidades BrunoF!!!!

Aunque supongo que has implementado un algoritmo que ya conocías, la solución es correcta.
Ya te he enviado la postal a las 2 direcciones que aparecen en tu perfil de todopic. Disfrutalas...

Citar
staría bueno proponer por ahí un problema en el que sea un poco más fácil y posible usar la lógica y no solo la matemática...
Creo que solo se puede usar la lógica para resolver un algoritmo así. Una vez uno tiene una solución planteada que cree que es correcta, usa la programación ("lógica+matemática") para implementarlo.
Si uno(no se si es tu caso) encuentra una descripción detallada del algoritmo puede implementarlo en C sin comprender realmente su funcionamiento, pero te aseguro que la persona que lo invento lo hizo usando la lógica.
Título: Re: Mini-Concurso de programacion
Publicado por: Nocturno en 27 de Abril de 2009, 09:03:19
Ahora que ya hay ganador, os dejo unos interesantes links que encontré sobre la resolución del problema:
- Estrategias de resolución (http://tog.acm.org/editors/erich/ptinpoly/)
- Distintos algoritmos en C (http://www.visibone.com/inpoly/)

¡Felicidades Bruno!
Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 27 de Abril de 2009, 12:04:11
Bueno, aquí va otra solución del problema.
Es el método más sencillo que se me ha ocurrido. Se basa en que para entrar el polígono tenemos que atravesar un numero impar de paredes.

-Trazamos una linea horizontal infinita a la altura del punto.
-Calculamos todos los puntos de corte de las rectas que componen el polígono con la recta trazada.
-Contamos el numero de paredes atravesadas hasta encontrar el punto.
   -Si el número de paredes atravesadas es IMPAR el punto esta DENTRO del polígono.
    -Si el número de paredes atravesadas es PAR el punto esta FUERA del poligono.

No he probado el algoritmo con otros polígonos, pero creo que debe funcionar(aunque sea modificandolo un poco) con cualquier polígono.
Creo que los casos en los que el algoritmo puede fallar son estos:
    El punto esta a la altura de un vertice del polígono.
    El punto esta a la altura de una linea horizontal del polígono.
    El punto esta sobre un lado del polígono.

Código: C
  1. int algoritmo( const Poligono plgn, const Punto pnt ){
  2.         //      Implementacion del algoritmo. Resultado = DENTRO/FUERA
  3.         #define min(a,b)                ((a<b)?a:b)
  4.         #define max(a,b)                ((a>b)?a:b)
  5.         #define TOCA                    ( min(plgn.lineas[i].P0.Y,plgn.lineas[i].P1.Y) <= lineaH.P0.Y && lineaH.P0.Y <= max(plgn.lineas[i].P0.Y,plgn.lineas[i].P1.Y) )
  6.  
  7.         int resultado = 0;
  8.         int i;
  9.         int izq, drch;
  10.         Punto cortes[LINEAS_POR_POLIGONO];
  11.         Linea lineaH;
  12.        
  13.         // Traza una linea horizontal mas larga que el poligono a la altura del punto.
  14.         lineaH.P0.X = pnt.X;
  15.         lineaH.P0.Y = pnt.Y;
  16.         lineaH.P1.X = pnt.X;
  17.         lineaH.P1.Y = pnt.Y;
  18.         for( i = 0 ; i < plgn.size ; i++ ){
  19.                 if( lineaH.P0.X > plgn.lineas[i].P0.X ){
  20.                         lineaH.P0.X     = plgn.lineas[i].P0.X;
  21.                 }
  22.                 if( lineaH.P1.X < plgn.lineas[i].P0.X ){
  23.                         lineaH.P1.X     = plgn.lineas[i].P0.X;
  24.                 }
  25.         }
  26.         lineaH.P0.X--;
  27.         lineaH.P1.X++;
  28.  
  29.         // Comprueba todos los puntos de corte de con la linea trazada
  30.         for( i = 0 ; i < plgn.size ; i++ ){
  31.                 if( TOCA ){
  32.                         float   xa = plgn.lineas[i].P0.X,
  33.                                         ya = plgn.lineas[i].P0.Y,
  34.                                         xb = plgn.lineas[i].P1.X,
  35.                                         yb = plgn.lineas[i].P1.Y;
  36.                        
  37.                         if( 0 != (xb-xa) ){
  38.                                 float m, b;
  39.                                 m = (yb-ya)/(xb-xa);
  40.                                 b = ((ya*xb)-(yb*xa))/(xb-xa);
  41.                                
  42.                                 if( 0 != m ){
  43.                                         cortes[i].X = (lineaH.P0.Y-b)/m;
  44.                                         cortes[i].Y = lineaH.P0.Y;
  45.                                 }else{
  46.                                         // La linea plgn.lineas[i] es horizontal.
  47.                                         cortes[i].X = pnt.X;
  48.                                         cortes[i].Y = lineaH.P0.Y;
  49.                                 }
  50.                         }else{
  51.                                 // La linea plgn.lineas[i] es vertical.
  52.                                 cortes[i].X = plgn.lineas[i].P0.X;
  53.                                 cortes[i].Y = lineaH.P0.Y;
  54.                         }
  55.                 }else{
  56.                         cortes[i].X = pnt.X;
  57.                         cortes[i].Y = pnt.Y+1; // Punto de corte NO valido. No afecta al resultado
  58.                 }
  59.                
  60.                 if( cortes[i].X == plgn.lineas[i].P1.X && cortes[i].Y == plgn.lineas[i].P1.Y ){
  61.                         if( (plgn.lineas[i].P0.Y < lineaH.P0.Y && plgn.lineas[(i+1)%plgn.size].P1.Y > lineaH.P1.Y)
  62.                                 || (plgn.lineas[i].P0.Y > lineaH.P0.Y && plgn.lineas[(i+1)%plgn.size].P1.Y < lineaH.P1.Y) ){
  63.                                 i++;
  64.                                 cortes[i].X = pnt.X;
  65.                                 cortes[i].Y = pnt.Y+1;
  66.                         }
  67.                 }
  68.         }
  69.        
  70.         // Cuenta los puntos de corte a la izq y a la drch del punto
  71.         for( i = 0, izq = 0, drch = 0 ; i < plgn.size ; i++ ){
  72.                 if( cortes[i].Y == pnt.Y ){
  73.                         if( cortes[i].X < pnt.X ){
  74.                                 izq++;
  75.                         }
  76.                         if( cortes[i].X > pnt.X ){
  77.                                 drch++;
  78.                         }
  79.                 }
  80.         }
  81.        
  82.         // Si hay numero impar de cortes a algun lado del punto, este se encuentra dentro.
  83.         if( izq%2 || drch%2 ){
  84.                 resultado = DENTRO;
  85.         }else{
  86.                 resultado = FUERA;
  87.         }
  88.        
  89.  
  90.         return resultado;
  91. }
  92.  

Título: Re: Mini-Concurso de programacion
Publicado por: BrunoF en 27 de Abril de 2009, 13:42:49
Gracias muchachos!!!

Aunque supongo que has implementado un algoritmo que ya conocías, la solución es correcta.

Sí. Este algoritmo es popular por ser uno de los más fiables incluso con polígonos complejos. He trabajado con DirectX y OpenGL y es fundamental saber detectar colisiones y si un punto está dentro de un poligono(solido en 3D) o no. Nunca lo había implementado en C, y el código podría mejorarse mucho para acelerar la velocidad. Lo dejé así para que sea más legible.
 
Ya te he enviado la postal a las 2 direcciones que aparecen en tu perfil de todopic. Disfrutalas...

Muchas gracias!!! :D :D :D(aunque no las he encontrado)

Citar
staría bueno proponer por ahí un problema en el que sea un poco más fácil y posible usar la lógica y no solo la matemática...
Creo que solo se puede usar la lógica para resolver un algoritmo así. Una vez uno tiene una solución planteada que cree que es correcta, usa la programación ("lógica+matemática") para implementarlo.
Si uno(no se si es tu caso) encuentra una descripción detallada del algoritmo puede implementarlo en C sin comprender realmente su funcionamiento, pero te aseguro que la persona que lo invento lo hizo usando la lógica.

Si te fijas verás que las dos soluciones que proponemos son las soluciones más populares y comunes para resolver este problema. Yo quise decir que con un problema de este tipo es muy dificil que alguien cree un algoritmo distintos a los conocidos. Ojalá aparezca alguien que lo haga y me tape la boca. Sería genial verlo.

Un saludo.
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 27 de Abril de 2009, 13:56:31
No se vale, ustedes ya hasta programan en 3D y nosotros apenas si podemos encender leds.  :lol:

Exijo una extensión del tiempo para propuestas de novatos.  :D
Título: Re: Mini-Concurso de programacion
Publicado por: jgpeiro06 en 27 de Abril de 2009, 15:59:49
Citar
o se vale, ustedes ya hasta programan en 3D y nosotros apenas si podemos encender leds.

Ok, Ok, habra un 2 y 3 premio para los que quieran seguir intentandolo, y otro premio al algoritmo más innovador.

Ademas anuncio un nuevo mini-concurso de programación...más interesante, más divertido, más emocionante, más premios...no se lo pierdan.
Proximamente en todopic.
Título: Re: Mini-Concurso de programacion
Publicado por: migsantiago en 27 de Abril de 2009, 16:25:22
Me gusta la idea.  :mrgreen:
Título: Re: Mini-Concurso de programacion
Publicado por: jeremylf en 21 de Octubre de 2011, 21:11:17
Estuve viendo una de las paginas que dio Nocturno:
Ahora que ya hay ganador, os dejo unos interesantes links que encontré sobre la resolución del problema:
- Estrategias de resolución (http://tog.acm.org/editors/erich/ptinpoly/)
- Distintos algoritmos en C (http://www.visibone.com/inpoly/)

... Y en la 2da muestran varias formas de resolverlo. Me centre en la primera forma: inpoly(). Su codigo es este:

Código: [Seleccionar]
/***************************************************************************
 *                                                                         *
 *   INPOLY.C                                                              *
 *                                                                         *
 *   Copyright (c) 1995-1996 Galacticomm, Inc.  Freeware source code.      *
 *                                                                         *
 *   Please feel free to use this source code for any purpose, commercial  *
 *   or otherwise, as long as you don't restrict anyone else's use of      *
 *   this source code.  Please give credit where credit is due.            *
 *                                                                         *
 *   Point-in-polygon algorithm, created especially for World-Wide Web     *
 *   servers to process image maps with mouse-clickable regions.           *
 *                                                                         *
 *   http://www.visibone.com/inpoly/inpoly.c                               *
 *                                                                         *
 *                                       6/19/95 - Bob Stein & Craig Yap   *
 *                                       stein@visibone.com                *
 *                                       craig@cse.fau.edu                 *
 *                                                                         *
 ***************************************************************************/

int                                /*   1=inside, 0=outside                */
inpoly(                            /* is target point inside a 2D polygon? */
unsigned int poly[][2],            /*   polygon points, [0]=x, [1]=y       */
int npoints,                       /*   number of points in polygon        */
unsigned int xt,                   /*   x (horizontal) of target point     */
unsigned int yt)                   /*   y (vertical) of target point       */
{
     unsigned int xnew,ynew;
     unsigned int xold,yold;
     unsigned int x1,y1;
     unsigned int x2,y2;
     int i;
     int inside=0;

     if (npoints < 3) {
          return(0);
     }
     xold=poly[npoints-1][0];
     yold=poly[npoints-1][1];
     for (i=0 ; i < npoints ; i++) {
          xnew=poly[i][0];
          ynew=poly[i][1];
          if (xnew > xold) {
               x1=xold;
               x2=xnew;
               y1=yold;
               y2=ynew;
          }
          else {
               x1=xnew;
               x2=xold;
               y1=ynew;
               y2=yold;
          }
          if ((xnew < xt) == (xt <= xold)         /* edge "open" at left end */
           && ((long)yt-(long)y1)*(long)(x2-x1)
            < ((long)y2-(long)y1)*(long)(xt-x1)) {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}

Estoy intentando hacer esto para que sean float's enves de int's porque mi aplicacion tiene unos cuantos decimales. Queria saber si ustedes saber que hace esta parte de codigo:

Código: [Seleccionar]
if ((xnew < xt) == (xt <= xold)         /* edge "open" at left end */
.
.
.

No me queda muy claro que pregunta ahi.


Gracias.
Título: Re: Mini-Concurso de programacion
Publicado por: MerLiNz en 21 de Octubre de 2011, 21:51:51
En este apartado (Lenguaje C para PICs) deberia haber un concurso de programacion pic, ya que lo anterior aplicado es matematicas, sin embargo de C hay poca cosa, es decir, si alguien sabe las formulas es facil transformarlo a C, pero algo que haya que comerse la cabeza programandolo es distinto a saber matematicas xD.
A ver si haceis uno asi, pero que no sea nada del otro mundo, por ejemplo que un pic haga una cosa, con otra cosa, y con otra cosa... Nose un juego de logica, usando interrupciones, timers... Y el ganador sera el que mas optimice el codigo, ya que hay veces que 200 lineas se pueden transformar en 50 mas eficientes xD
Título: Re: Mini-Concurso de programacion
Publicado por: BrunoF en 22 de Octubre de 2011, 00:12:16
Código: [Seleccionar]
if ((xnew < xt) == (xt <= xold)         /* edge "open" at left end */
.
.
.
No me queda muy claro que pregunta ahi.

Bueno, básicamente esa parte de la condición dara verdadera si ambas condiciones entre paréntesis son Verdaderas o Falsas.
Si hacemos tabla de verdad:
xnew < xt            xt <= xold         resultado condición
     FALSE                 FALSE                    TRUE
     TRUE                  FALSE                    FALSE
     FALSE                 TRUE                     FALSE
     TRUE                  TRUE                      TRUE
       
Bueno, digamos que es una XNOR, no?  :mrgreen:

Saludos.
Título: Re: Mini-Concurso de programacion
Publicado por: Suky en 22 de Octubre de 2011, 10:15:39
En este apartado (Lenguaje C para PICs) deberia haber un concurso de programacion pic, ya que lo anterior aplicado es matematicas, sin embargo de C hay poca cosa, es decir, si alguien sabe las formulas es facil transformarlo a C, pero algo que haya que comerse la cabeza programandolo es distinto a saber matematicas xD.
A ver si haceis uno asi, pero que no sea nada del otro mundo, por ejemplo que un pic haga una cosa, con otra cosa, y con otra cosa... Nose un juego de logica, usando interrupciones, timers... Y el ganador sera el que mas optimice el codigo, ya que hay veces que 200 lineas se pueden transformar en 50 mas eficientes xD

Esperamos el aporte, menos palabras más acción  :mrgreen: Seguramente alguno se prende.
Título: Re: Mini-Concurso de programacion
Publicado por: jeremylf en 22 de Octubre de 2011, 17:09:40
Gracias bruno!
Título: Re: Mini-Concurso de programacion
Publicado por: MerLiNz en 23 de Octubre de 2011, 14:08:54
no no, yo queria que lo hiciese alguien para apuntarme yo  :D
Título: Re: Mini-Concurso de programacion
Publicado por: Suky en 23 de Octubre de 2011, 15:32:31
no no, yo queria que lo hiciese alguien para apuntarme yo  :D

 :D :D Andaaaa!
Título: Re: Mini-Concurso de programacion
Publicado por: MerLiNz en 23 de Octubre de 2011, 17:58:20
Se me ocurre que podria usar esto para que la gente hiciese mi trabajo jajajaj, la gente se come la cabeza, y yo copio-pego xDD

Es broma jeje