Mini-Concurso de programacion

[AKENAFAB]

Se ve muy interesante 

Aunque se me cierra *   

   No creo tener las bases para entrarle


Un saludo!

Por aca los veo!

[RedPic]

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. type tpunto = record x,y:double end;
2. type tpoligono = array of tpunto;
3.  
4. function PointInPoly( p : tpunto; const v : tpoligono ): boolean;
5. var
6.   p0,p1:tpunto;
7.   i: integer;
8.   UpSide:boolean;
9. begin
10.   result:= false;
11.  
12.   p1 := v[High(v)];
13.   UpSide := ( p.y < p1.y );
14.   for i := 0 to High(v) do begin
15.     p0 := p1;
16.     p1 := v[i];
17.     if (UpSide xor (p.y < p1.y)) then
18.     begin
19.       if (p.x < (p0.x - p1.x) * (p.y - p1.y) / (p0.y - p1.y) + p1.x) then result := not result;
20.       UpSide := not UpSide;
21.     end;
22.   end;
23. end;

[migsantiago]

jeje eso parece VHDL

Redpic, vas a tener que migrarlo a C si quieres ganarte la postal 

[jgpeiro06]

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. }

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....

[BrunoF]

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:




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.

[jgpeiro06]

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...

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.

[Nocturno]

Ahora que ya hay ganador, os dejo unos interesantes links que encontré sobre la resolución del problema:
- Estrategias de resolución
- Distintos algoritmos en C

¡Felicidades Bruno!

[jgpeiro06]

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. }

[BrunoF]

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!!! (aunque no las he encontrado)

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.

[migsantiago]

No se vale, ustedes ya hasta programan en 3D y nosotros apenas si podemos encender leds. 

Exijo una extensión del tiempo para propuestas de novatos. 

[jgpeiro06]

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.

[migsantiago]

Me gusta la idea. 

[jeremylf]

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
- Distintos algoritmos en C

... 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.

[MerLiNz]

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

[BrunoF]

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? 

Saludos.